public TreeNode removeA(int x) { if (this == externalnode ) return externalnode;
ID: 3817455 • Letter: P
Question
public TreeNode removeA(int x) {
if (this == externalnode ) return externalnode; // Item not found; do nothing
if (x < this.getData()) {
this.setLeft(this.getLeft().removeA(x));
} else if (x > this.getData()) {
this.setRight(this.getRight().removeA(x));
// Below here means "this" is the node to be removed
} else if (this.getLeft() == externalnode) {
return this.getRight();
} else if (this.getRight() == externalnode ) {
return this.getLeft();
} else {
// TreeNode for the removed data gets recycled by
// setting its value to the maximum value in the left subtree.
// Therefore, we delete the TreeNode containing the maximum value in the left subtree.
this.setData(this.getLeft().deleteMax(this).getData());
}
return this;
}
Any way to write this non-recursively?
Explanation / Answer
void remove(Node *root)
{
// Base Case
if (root == NULL)
return;
// Create an empty queue for level order traversal
queue<Node *> q;
// Do level order traversal starting from root
q.push(root);
while (!q.empty())
{
Node *node = q.front();
q.pop();
if (node->left != NULL)
q.push(node->left);
if (node->right != NULL)
q.push(node->right);
free(node);
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.