Inorder Successor of a Node in Binary Search Tree (BST)

Difficulty: Easy, Asked-in: Facebook, Google, Amazon, Microsoft.

Key takeaway: An excellent problem to learn problem-solving using both iterative and recursive approaches in the binary search tree.

Let’s understand the problem

Given a node x and the root of a binary search tree, write a program to find the in-order successor of node x.

• The in-order successor of node x is a node that will be visited just after node x during in-order traversal. In other words, the in-order successor of a node x is the node with the smallest key greater than x->key.
• If node x is visited last during the in-order traversal, then its in-order successor will be NULL. In other words, such a node will be the node with the largest key in the BST.

Iterative implementation using parent pointer

To find the in-order successor, we need to find the node with the smallest key just greater than the x->key. So there will two cases:

Case 1: When the right subtree of x is not empty

In this case, the in-order successor of node x is the node with the minimum key in its right subtree, i.e., the leftmost node in the right subtree of node x.

if (x->right != NULL) 
    return bstMinimum(x->right)

Case 2: When the right subtree of x is empty

In this case, the in-order successor is the lowest ancestor of x whose left child is also an ancestor of x. To find such an ancestor, we move up in the tree from node x until we encounter a node that is the left child of its parent. If any such node is found, then the parent of that node is the in-order successor. Otherwise, an in-order successor does not exist for the node (if x is the node with the largest key).

Here, we need to move upward towards the ancestors of the node. So, the implementation will be easier if we define a BST node structure that has a pointer to its parent as well.

BSTNode prev = x->parent
while (x != NULL && x == prev->right) 
{
    x = prev
    prev = prev->parent
}
return prev

Solution code C++

struct BSTNode 
{
    int key;
    BSTNode* left;
    BSTNode* right;
    BSTNode* parent;
    BSTNode(int k) 
    {
        key = k;
        left = NULL;
        right = NULL;
        parent = NULL;
    }
};

BSTNode* bstMinimum(BSTNode* root) 
{
    BSTNode* curr = root;
    while (curr->left != NULL)
        curr = curr->left;
    return curr;
}

BSTNode* bstInorderSuccessor(BSTNode* root, BSTNode* x) 
{
    if (x->right != NULL)
        return bstMinimum(x->right);

    BSTNode* prev = x->parent;
    while (x != NULL && x == prev->right) 
    {
        x = prev;
        prev = prev->parent;
    }
    return prev;
}

Solution code Python

class BSTNode:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None
        self.parent = None

def bst_minimum(root):
    curr = root
    while curr.left is not None:
        curr = curr.left
    return curr

def bst_inorder_successor(root, x):
    if x.right is not None:
        return bst_minimum(x.right)

    prev = x.parent
    while x is not None and x == prev.right:
        x = prev
        prev = prev.parent
    return prev

Time and space complexity analysis

If the right child of node x is present, then the minimum value in the right subtree will be the successor. In the worst case, node x will be the root node, and we need to traverse the entire height of the tree down to one of the deepest leaf nodes. So, the time complexity in the worst case is O(h).

If the right child of x is not present, then we traverse upward to find the successor. In the worst case, x will be one of the deepest leaf nodes, and the root node will be the successor. Here, we need to traverse the entire height of the tree. So, the time complexity in the worst case is O(h).

Overall, the time complexity is O(h), which depends on the height of the tree. Since we store an extra parent pointer inside each node, the space complexity is O(n).

Iterative solution without using parent pointer

In this approach, the implementation of the first case remains the same. When the right subtree of x is not empty, the in-order successor of node x is the node with the minimum key in its right subtree.

For case 2, when the right subtree of x is empty, we move down from the root to node x and update the in-order successor. The idea is simple: We maintain a succ pointer to track the successor and move down from the root to node x by comparing the root->key with the x->key.

• If x->key > root->key, we move right. There is no need to update the succ pointer because the current node root will not be the candidate for the successor. The idea is simple: the value of succ->key will always be greater than x->key.
• If x->key < root->key, we update the succ pointer to the current node root and move to the left subtree (succ = root and root = root->left). We update the succ pointer because the current node root will be the candidate for the successor. Think!
• If x->key == root->key, it means we have found the given node x, and we break out of the loop.

At the end of this loop, we return the succ pointer, which will hold the successor of the node x.

Solution code C++

BSTNode* bstMinimum(BSTNode* root) 
{
    BSTNode* curr = root;
    while (curr->left != NULL)
        curr = curr->left;
    return curr;
}

BSTNode* bstInorderSuccessor(BSTNode* root, BSTNode* x) 
{
    if (x->right != NULL)
        return bstMinimum(x->right);

    BSTNode* succ = NULL;
    BSTNode* curr = root;
    while (curr != NULL) 
    {
        if (x->key < curr->key) 
        {
            succ = curr;
            curr = curr->left;
        } 
        else if (x->key > curr->key)
            curr = curr->right;
        else
            break;
    }
    return succ;
}

Solution code Python

def bst_minimum(root):
    curr = root
    while curr.left is not None:
        curr = curr.left
    return curr


def bst_inorder_successor(root, x):
    if x.right is not None:
        return bst_minimum(x.right)

    succ = None
    curr = root
    while curr is not None:
        if x.key < curr.key:
            succ = curr
            curr = curr.left
        elif x.key > curr.key:
            curr = curr.right
        else:
            break
    return succ

Time and space complexity analysis

During the search process, we traverse the entire height of the tree in the worst case. So, the time complexity will be O(h). Since there is no parent pointer and we use a constant amount of extra space, the space complexity is O(1).

Recursive solution without using parent pointer

The idea is to search for the given node in the tree and update the successor to the current node before visiting its left subtree. If the node is found in the BST, we return the node with the minimum key in its right subtree. If the right subtree of the node doesn't exist, then the in-order successor is one of its ancestors, which has already been updated while searching for the given key.

Solution steps

1. If root->key == x->key, we check if node x has the right subtree. If it does, we return the minimum node in the right subtree as the successor, i.e., return bstMinimum(root->right).
2. If root->key > x->key, we update the succ pointer to the current node root and recursively call the same function on the left subtree, i.e., inorderSuccessor(root->left, succ, x).
3. If root->key < x->key, we recursively call the same function on the right subtree to continue searching for the successor in the right subtree, i.e., inorderSuccessor(root->right, succ, x).
4. Finally, we return the succ pointer.

Solution code C++

BSTNode* bstMinimum(BSTNode* root) 
{
    while (root->left != NULL)
        root = root->left;
    return root;
}

BSTNode* inorderSuccessor(BSTNode* root, BSTNode* succ, BSTNode* x) 
{
    if (root == NULL)
        return succ;

    if (x->key == root->key) 
    {
        if (x->right != nullptr)
            return bstMinimum(x->right);
    } 
    else if (x->key < root->key) 
    {
        succ = root;
        return inorderSuccessor(root->left, succ, x);
    } 
    else
        return inorderSuccessor(root->right, succ, x);

    return succ;
}

Solution code Python

def bst_minimum(root):
    while root.left is not None:
        root = root.left
    return root


def inorder_successor(root, succ, x):
    if root is None:
        return succ

    if x.key == root.key:
        if x.right is not None:
            return bst_minimum(x.right)
    elif x.key < root.key:
        succ = root
        return inorder_successor(root.left, succ, x)
    else:
        return inorder_successor(root.right, succ, x)

    return succ

Time and space complexity analysis

At each step of recursion, we descend one level down. So, in the worst case, we traverse the entire height of the tree. Time complexity = O(h).

The space complexity depends on the size of the call stack, which is equivalent to the height of the recursion tree. So, the space complexity is O(h).

Critical idea to think!

• How can we solve this problem using an in-order traversal?
• How can we modify the above code to find both in-order predecessor and successor together?
• How can we solve this problem by storing the in-order traversal of the BST in an array?
• The time complexity of all the above approaches is O(h). What would be the worst and best-case scenarios?

Suggested coding questions to practice

• Replace each node in the binary tree with the sum of its inorder predecessor and successor
• Populate inorder successor for all nodes
• Find the in-order predecessor of a node in BST
• The in-order successor of a node in a binary tree
• The lowest common ancestor of a binary search tree
• Validate binary search tree
• Convert sorted array to binary search tree

If you have any queries or feedback, please write us at contact@enjoyalgorithms.com. Enjoy learning, Enjoy algorithms!