Amazon Interview Question Software Engineer / Developers
Country: India
Interview Type: Written Test
and if we do not have a parent node, then:
node *wanted; // the node whose successor we wish to find
node *find_rec(node *t, bool& found) {
if(t == 0) {
found = false;
return 0;
}
if(t == wanted) { // found the 'wanted' node
found = true; // in the traversal
return 0;
}
node *x = find_recurs(t->left, found);
if(found) {
if(x != 0)
return x; // the successor already found: just pass it by
return t; // this is a successor
}
return find_rec(t->right, found);
}
node *inorder_succ() {
if(wanted->right) {
... // proceed as in the above soln
return t;
}
bool found = false; // otherwise start the search from the root
return find_rec(root, found);
}
I think it's better to follow the inorder travel recursive as:
Inorder(root)
{
if (!root) return;
Inorder(root->left);
visit(root);
Inorder(root->right);
}
So rewrite your code as:
node *wanted; // the node whose successor we wish to find
find_rec(node *root, bool& found, node *successor) {
if(root == 0) {
found = false;
return 0;
}
find_recurs(root->left, found, successor);
if(found) {
successor = root; // this is a successor
//reset found to finish the recursive
found = false;
return;
}
if(root->data == wanted) { // found the 'wanted' node
found = true; // in the traversal
}
find_rec(root->right, found, successor);
}
Do the nodes have references to their parent nodes? If so, the next node is either the leftmost child of the right subtree, or the first ancestor node of which the node is in the left subtree of if the node does not have a right child. If not, and the node has no right child, just do an in-order traversal of the tree until you find the node, and output the next node.
Assuming you do have a reference to the parent:
- Anonymous October 18, 2011public Node findNext(Node s) { Node result; if (s.rightChild != null) { result = s.rightChild; while (result.leftChild != null) result = result.leftChild; return result; } else { result = s.parent; Node next = s; while (result != null && result.rightChild != null && result.rightChild == next) { next = result; result = result.parent; } return result; }