DIR Return Create A Forum - Home
---------------------------------------------------------
techsuns
HTML https://techsuns.createaforum.com
---------------------------------------------------------
*****************************************************
DIR Return to: Trees
*****************************************************
#Post#: 118--------------------------------------------------
Find the successor in the binary search tree
By: kranthipls Date: November 18, 2012, 11:51 pm
---------------------------------------------------------
Given a binary search tree and a node x find the successor of
the node x in the binary search tree.
i.e the node that is just greater than x in the tree.
Assume that there is a link from child to parent
Please think of the possible cases.
#Post#: 134--------------------------------------------------
Re: Find the successor in the binary search tree
By: satya Date: November 19, 2012, 12:46 am
---------------------------------------------------------
After going to node x, since we have to find the next node which
is just greater than x. we will go to the right child (say y)of
node x. Now if this node y does not have a left subtree y
itself is the answer. otherwise we have to traverse till the
leaf node of the left subtree of node y which will give the
answer.......... is it right mr.kranthiveer???? :) :) :)
#Post#: 135--------------------------------------------------
Re: Find the successor in the binary search tree
By: kranthipls Date: November 19, 2012, 12:51 am
---------------------------------------------------------
Partly right. That is why I told take all cases into
consideration. What if it does not have a right child??????????
#Post#: 136--------------------------------------------------
Re: Find the successor in the binary search tree
By: satya Date: November 19, 2012, 2:45 am
---------------------------------------------------------
Then the parent of x must be the successive node
right........... ;D
#Post#: 142--------------------------------------------------
Re: Find the successor in the binary search tree
By: kranthipls Date: November 19, 2012, 3:35 am
---------------------------------------------------------
Come on yaar. Think all possible cases. In a binary search tree
can't the parent need be smaller than the child node????????
#Post#: 169--------------------------------------------------
Re: Find the successor in the binary search tree
By: dinesh Date: November 19, 2012, 11:58 pm
---------------------------------------------------------
The required node is the inorder successor....
*****************************************************