Successor and Predecessor–BST

“Successor and predecessor is something that we see only in a BST. We have seen in a binary tree there is ancestor node, parent node, child node, sibling node. But in a BST, successor node might be necessary to take the nth smallest item in a tree”

Introduction

    Say, you have a BST,

                      15

              6               19

         3               17        20

    2        4

You need to find the 5th smallest element in this or you need to find the next element to 4 which is ”6”.  Assume that all the elements are distinct. How would you find that?

Simple approach:

• Do a in-order traversal
• Store the whole tree in an array while traversal
• Search for the “4” in the whole array
• The index found +1 will give the successor element

The above approach works well but has the following problems:

• We use O(n) extra space
• If the elements are not identical, we need some more logic to jump across same elements

Concept

   The above problems are get solved with the concept of successor and predecessor. Successor in a BST for any element is defined by two concepts:

• If the element has a right node, then the min element in the right sub tree (which is the left most element) will be successor.
• If the element doesn’t have a right node, then check whether it has a parent node and also verify whether this element is the right node for its parent.

Example:

• Successor node for: 15 is 17 (left-most)
• Successor node for: 4 is 6 (parent of “4” is “3” and move up by parent until “4” is not the right node for the parent. which yields as “6”)

The above properties of a successor in a BST can be used to design a algorithm to find the successor for the given element.

   The second property is nothing but finding the least ancestor of the given node which we will use in future.

Code

int find_successor(BST* root)

{

    if(root == NULL) return NULL;

    // min of right subtree

    if(root->right != NULL) return min(root->right);

    // ancestor of node without right subtree

    BST* ancestor = root->parent;

    while(ancestor != NULL && ancestor->right == root)

    {

        root = ancestor;

        ancestor = ancestor->parent;

    }

    return ancestor->data;

}