Amazon Interview Question
Country: United States
Sorry i had to comment on this solution of yours. As i understand you are storing parent nodes in array while traversing.(BTW nice approach here :) ) Here you are not checking if the found node is left child of parent node. Hence when you find a node and say it is right child. You return it. You have to find the parent say x which is the left child of its parent say y. The output will be rchild of y.
@Yoda, thanks for pointing out the mistake.
Actually, i have taken care of this case in my other solution.
In a hurry, forgot to handle here.
BTW, i have updated the solution.
i'm not sure but i think there maybe some problem for this solution, think the following situation:
.............................10
..................2......................11
......................3
...........................9
......................8
.................1
......................4
...........................5
if i wanna find the successor of 5, it should be 11, however, using the above method, the return should be 3. I don't know whether I'm right, if any mistake, please point out.
@ shiqing881215, You have not drawn the tree correctly. See the position of 1.
I am getting the output as 11 as per the solution after correcting the tree.
@shondik Thx for you correction. I have change the tree to following:
.............................10
..................2......................11
......................3
...........................9
......................8
.................4
......................5
...........................6
However, I run your code, as i expected, it doesn't output 11, instead, it outputs the 9.
Coz in your second for loop, when you go to the node 3, now p is the node 4, node 3 has a right child 9 which is not equal to p, so you will return the 9. And i think that's not right. thx
@ shiqing881215, see my solution again. I have provided the link also where i am getting the correct output as 11.
Thanks for pointing out the mistake.
@ shondik hi, it's very nice to discuss with you, if you don't mind, can we make a friend? my email is username @gmail
public void pre_order_successor(Tree tree,int value,int flag)
{
if(tree == null)
return;
if(tree.element == value)
flag = 1;
if(flag == 1)
{
System.out.print(tree.element);
flag = 0;
return;
}
else
{
pre_order_successor(tree.left,value,flag);
pre_order_successor(tree.right,value,flag);
}
}
call the function with pre_order_successor(root,value,0).... am i right?
The solution works but visits all the nodes in the BST. After printing don't set flag = 0 keep it as it is so that it returns w.o visiting all nodes.
The solution works but visits all the nodes in the BST. After printing don't set flag = 0 keep it as it is so that it returns w.o visiting all nodes.
@paidi: if i don't reset the flag, then every 'tree.element' will be printed after the pre-order successor is found..
struct node *PreOrderSuccessor(struct node *root,struct node *n)
{
if(!root||!n)
return NULL;
if(n->left)
return n->left;
else if(!n->left&&n->right)
return n->right;
else
{
struct node *succ=root;
while(root)
{
if(n->data>root->data)
root=root->right;
else if(n->data<root->data)
{
succ=root;
root=root->left;
}
else
break;
}
return succ->right;
}
}
Time Complexity - O(h)
Space Complexity - O(1)
To find the preorder successor of node u in bst, parent pointer is needed :
if u has left child l the succ(u) = l
else if u has right child r the succ(u) = r
else if u is a left child of its parent then succ(u) is its right sibling
else if u has ancestor v such that v is left child of its parent and has right sibling 'vrs' succ(u) = vrs.
otherwise no successor exists
struct node* pre_succ(struct node* u)
{
if(!u)
return NULL;
if(u->left) // left child exits
return u->left;
if(u->right) // no left child but has right child
return u->right;
while(u!=NULL && u!=u->parent->left) // is a leaf node
{
u = u->parent;
}
if(u->parent)
return u->parent->right; // right sibling of ancestor which is left child of its parent
return NULL; // no sucessor
}
ya..i missed one more condition in while loop
it should have been
while(u && u!=u->parent->left && !u->parent->right)
void presuccess(bst *r,int skey,int suc)
{
if(r!=NULL)
{
if(suc==1)
{
cout<<"\n\t"<<r->nm;
suc=0;
return;
}
if(r->nm==skey )
{
suc=1;
}
presuccess(r->left,skey,suc);
presuccess(r->right,skey,suc);
}
}
struct node* pre_succ(struct node *root,struct node* u)
{
if(!u)
return NULL;
if(u->left)
return u->left;
if(u->right)
return u->right;
struct node* ptr = root;
struct node* succ = NULL;
while(ptr!=NULL)
{
if(ptr->right != NULL)
{
succ = ptr;
succ->visited = true;
}
if(ptr == u)
break;
if(ptr->ele < u->ele)
ptr = ptr->right;
else
ptr = ptr->left
}
if(succ && succ->visited == false)
return succ
}
Well, the solution depends on what information we have.
If parent pointers are given, here is the pseudo code:
1. If the left child exists, return it
2. If the right child exists, return it.
3. If both children do not exist, we must backtrack to parent. Two conditions arise:
If the node is the left child of its parent or the node is the right child of the parent.
If the node is the right child of its parent,move upwards until it becomes the left child.
If the node is the left child, move upwards until its parent doesn't have right child.
PreorderSuccessor(p)
{
if(p->left)
return p->left
if(p->right)
return p->right;
par=p->parent;
while(par && par->right==p)
{
p=par;
par=p->parent;
}
while(par && par->right==NULL)
par=par->parent;
if(par && par->right)
return par->right;
return NULL:
}
A recursive approach:
I don't think in any way, we are benefitted whether the tree is BST or BT.
preorderSuccessor(root,p)
{
static Node* prev;
if(root)
{
if(prev==p)
return root;
prev=root;
preorderSuccessor(root->left,p);
preorderSuccessor(root->right,p);
}
return NULL;
}
Nice. But you have a basic flaw here. if the node p is right child of say q and q in turn is right child of r. Then will your solution work. Actually you first need to find the parent node x which was the left child of its parent y and y has a right child. The output will be right child of y.
I think this will work. I am first checking whether the previous marked node is the node whose successor is to be found.If yes, just return the current node. Now, What will be the relationship between the previous visited node & the current node. The latter is the successor of the former.
Can you cite an example[a tree] where it fails?
Here is the logic
1. If there is a left subchild to the given node it is the successor. Terminate
else
2. If there is a rightsubchild to the given node it is the successor. Terminate
else
3. If the node's parent has a unmarked right subchild . It is the successor. Terminate
else
4. Repeat step 3 navigating through parent going up. Mark the parent as marked as we go up.
5. If you are at root of tree with no unmarked right subchild then there is no successor.
Node* pre_order_successor(Node* p)
{
if(NULL == p) return NULL;
if(NULL != p->left) return p->left;
if(NULL != p->right) return p->right;
while(NULL != p->parent)
{
if (p->parent->left == p && NULL != p->parent->right)
return p->parent->right;
p = p->parent;
}
return NULL;
}
int preOrderSucc(TreeNode node) {
if (node.leftChild != null)
return node.leftChild.val;
if (node.rightChild != null)
return node.rightChild.val;
// if node is right child of its parent
// go up till parent becomes left child.
// If that does not happen, return -1
if (node == node.parent.rightChild) {
while ((node.parent != null) && (node == node.parent.rightChild)) {
node = node.parent;
}
}
if (node == null)
return -1;
// if we are here, that means node is now left child of its parent
// if node is left child of its parent
TreeNode temp = node.parent;
while (temp != null) {
if (temp.rightChild != null)
return temp.rightChild.val;
temp = temp.parent;
}
return -1;
}
This code finds preorder successor of the node p in a bst with root t .
bintree *preorder_succ(bintree *t,bintree *p)
{
if(p->left)
return p->left;
if(p->right)
return p->right;
bintree *temp,*prev;
temp=t;prev=NULL;
while(temp!=p)
{
if(p->value < temp->value)
{
prev=temp;
temp=temp->left;
}
else
temp=temp->right;
}
if(!prev || !prev->right)
return NULL;
return prev->right;
}
Why don't we use BFS like to make each node into a queue by pre-order, and we de-queue one by one, if we find the value in the queue, then the next de-queue value will be pre-order successor.
TreeNode* preorder(TreeNode* root, int key)
{
TreeNode* succ=NULL;
while(root)
{
if(key==root->val)
{
if(root->left) return root->left;
else if (root->right) return root->right;
else return succ;
}
else if(key<root-val)
{
if(root->right) succ=root->right;
root=root->left;
}
else root=root->right;
}
return succ;
}
A non-recursive approach which makes use of BST.
Assuming parent pointers are not given.
The space complexity is O(log N)
Time complexity is O(log N)
LOGIC:
1. If the left child r right child exists, return it.
2. Store all the ancestors of the nodes to be found in an array in top down manner.
3. Start searching for the successor among ancestors in bottom up manner. If the right child of the ancestor exists & its right child is the node whose successor is to be found, we will continue following the path upwards.
I have updated my solution along with the link where i have tried it. Its giving correct output for every input.
- Aashish July 07, 2012See complete code here: ideone.com/18tLJ