Friday, March 14, 2014

Find inorder successor in BST

A frequently asked question is: Find the next in order successor in a BST.

Algorithm would be:

If (node has a rightChild){
find min in right subtree i.e. go right and keep going left
till you encounter a NULL
}
else if (node is a leftChild of its parent){
parent is the in order successor
}
else{
node is the right Child.
while(parent != NULL){
1. Keep going up the parents till you find a node that is
the left child of its parent. That parent is the in order successor
or 2. Keep going up till you find a node >= current node
}
if no successor found this means that the node was the rightmost
one and has no successor
}

As an example:
Tree:
                      30
          20                       42
    10           27       37             45
 2     15   22               39     44    50

Third case(node is rt child) needs elaboration:
E.g. Say node is 27, keep going up till you find a node >= 27 i.e. 30, this is the ans
E.g. Node is 15, go up till you find a node that is left child, node is 10, its parent i.e 20
        is the required ans
                   













No comments:

Post a Comment