Inorder successor in Binary tree

7Comments
Tinu Dahiya @tinudahiya
31 Jan 2016 01:58 am

http://www.geeksforgeeks.org/inorder-successor-in-binary-search-tree/

check the example, you get more clarification about this question.

meet @meet
31 Jan 2016 01:23 pm

still confuse how ans is option D

Sougatamoy Biswas @sougatamoy
31 Jan 2016 02:28 pm

Y is the In-order Successor of node X . So, in In-order traversal y will be after x. Now, x has only left child.If X is the parent of y then  y should be in left side. Then  in In-order traversal (left-Root-right) x will be after y. But, for In-order Successor of node X, y will be after x. So, y can be parent of x and x can be left child. So, option (B) is correct.

Arvind Rawat @arvind.rawat
1 Jun 2016 11:34 am

But y is the parent of x does not necessarily gaurantee that x is left child of y. So i think, the answer should be D.

Hradesh @hradeshpatel
1 Jun 2016 11:32 pm

according to this question language: x is left child of y.

inorder (Left-root-right)- so that y comes after x.

option B is correct

Arvind Rawat @arvind.rawat
2 Jun 2016 11:30 am

Okay now i got the question, it is given that Y is the inorder-successor of X, which can only be possible if either of the following condition exists:

1). Y is right child of X.
2). Y is parent of X and X does not have right child.

Here condition 1 is in violation of the question, so condition 2 must hold. According to condition 2, X does not have right child is satisfied by the question, so the only thing that is remaining is Y is parent of X. Hence option B is correct.

saipriyadarshini @bandisaipriyada
3 Dec 2017 07:36 pm

In order to be inorder successor binary tree  should be right child and we are going to pick the least one in the right child

Pages