## Amazon Interview Question

• 0

Find preorder successor in BST.

Country: United States

Comment hidden because of low score. Click to expand.
10
of 10 vote

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.

``````preorderSuccessor(root,p)
{
if(!root || !p)
return NULL;
if(p->left)
return p->left;
if(p->right)
return p-right;
top=-1;
while(root->data!=p->data)
{
arr[++top]=root;
if(p->data<root->data)
root=root->left;
else
root=root->right;
}
for(i=top;i>=0;i--)
{
if(arr[i]->right)
{
if(p!=arr[i]->right)
return arr[i]->right;
}
p=arr[i];
}
return NULL;
}``````

I have updated my solution along with the link where i have tried it. Its giving correct output for every input.

See complete code here: ideone.com/18tLJ

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

@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.

Comment hidden because of low score. Click to expand.
0

Like

Comment hidden because of low score. Click to expand.
0

i think it's a right solution

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

@ 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.

Comment hidden because of low score. Click to expand.
0

@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

Comment hidden because of low score. Click to expand.
0

@ 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.

Comment hidden because of low score. Click to expand.
0

@ 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

Comment hidden because of low score. Click to expand.
0

@shondik - this code dont works for below tree

.....15
..........20
...............25
...................28
.......................30

And if i need to know the preorder successor of 28...

Comment hidden because of low score. Click to expand.
2
of 2 vote

``````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?

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

@paidi: if i don't reset the flag, then every 'tree.element' will be printed after the pre-order successor is found..

Comment hidden because of low score. Click to expand.
0

Logic is correct, but it won't print the successor. After setting flag =1, immediately you are checking the flag. So, it will print given value only. To avoid visiting all nodes in BST, use one more boolean variable and set it appropriately when printing the successor.

Comment hidden because of low score. Click to expand.
1
of 1 vote

``````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)

Comment hidden because of low score. Click to expand.
0
of 0 vote

This comment has been deleted.

Comment hidden because of low score. Click to expand.
0

Here everything is typed in English. Maybe you should learn English first.

Comment hidden because of low score. Click to expand.
0

we need like button on this site :)

Comment hidden because of low score. Click to expand.
0
of 2 vote

I hate this binary tree,Damn!! @

Comment hidden because of low score. Click to expand.
0

Comment hidden because of low score. Click to expand.
0

Comment hidden because of low score. Click to expand.
0

+1 @naga

Comment hidden because of low score. Click to expand.
0
of 0 vote

To find the preorder successor of a node, locate that node in the tree.. then check if the left of the node is null. If it is not null then print it. Else if, check if the right of node is null. If it is not null then print it. Else print the right of the root.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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
}``````

Comment hidden because of low score. Click to expand.
0

Not working always. e.g. 100,20,10,300
find preorder successor of 10.

Comment hidden because of low score. Click to expand.
0

ya..i missed one more condition in while loop
it should have been
while(u && u!=u->parent->left && !u->parent->right)

Comment hidden because of low score. Click to expand.
0

I think this condition works instead of lot of checks in While loop.
while(u && !u->right)
{
u = u->parent;
}
if(u)
{
return u->right;
}
else
{
return NULL;
}

Let me know if you find any flaw.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
}
}

Comment hidden because of low score. Click to expand.
0

what is "u" in this function which is passed as argument??

Comment hidden because of low score. Click to expand.
0
of 0 vote

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
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

pre_succ(node *root,int value)
{

Comment hidden because of low score. Click to expand.
0
of 0 vote

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:

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}``````

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

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?

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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;
}``````

Comment hidden because of low score. Click to expand.
0

perfect

Comment hidden because of low score. Click to expand.
0
of 0 vote

without parent pointer

``````find(r, u){
cand = null;
while(r !=null && r != u){
if(u < r){
if(r.right != null)
cand = r.right;
r = r.left;
}
else{
r = r.right;
}
}

if(r==u){
if (r.left!= null)
return r.left;
else if(r.right !=null)
return r.right;
else return cand;
}
return null;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;``````

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0

If you do that than you need to traverse the whole BST

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````tree_node *sucessor = NULL;
tree_node * preOrder_sucessor(tree_node * node, int p) {

if (node->data == p)
if(sucessor != NULL) return sucessor;
else return node;
else sucessor = node;

if (node->left != NULL)
preOrder_sucessor(node->left, p);
else preOrder_sucessor(node->right, p);
}``````

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book walking you through every aspect of getting a job at a top tech company, while focuses on software engineering interviews.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.