Question: Given a Node of a binary tree, find it's InOrder Successor.
Answer:
BST * BST_successor(BST * node)
{
// If right-sub-tree exists, return the min of
//right-sub-tree, or say the leftest node.
if(node -> right)
return BST_min(node -> right);
// else, keep moving upwards, as long as the
// node is the right child of its parent
BST * p = node -> parent;
while(p && p -> right == node)
{
node = p;
p = node -> parent;
}
return p;
}
Subscribe - To get an automatic feed of all future posts subscribe here, or to receive them via email go here and enter your email address in the box. You can also like us on facebook and follow me on Twitter @akashag1001.
Isn't it that we move upward until the current node left child? Whenever we found that we are at right sub-tree we are sure that the node is larger than all those in left sub-tree we climbed up. So, we return this node. It looks like the code to be,
BST * pSucc = node -> parent;
while(pSucc && pSucc->left == node)
{
node = pSucc;
pSucc = node -> parent;
}
return pSucc;