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

Difficulty: Easy, Asked-in: Amazon, Microsoft, Ola.

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

Write a program to find the in-order predecessor of a given node x in a binary search tree (BST). An in-order predecessor of node x is the node that will be visited just before node x in the in-order traversal.

Problem note: If node x is visited first (leftmost node in BST), then the predecessor of node x is NULL. In other words, the in-order predecessor of the node with the minimum value does not exist in the BST.

Inorder predecessor of a node in BST example

Iterative solution using parent pointer

Solution idea

If the left subtree of node x is present, the in-order predecessor of node x is a node with the maximum value in its left subtree. If the left subtree of node x doesn't exist, then there are two cases:

If node x is the right child of its parent, then the in-order predecessor will be its parent node.
If node x is the left child of its parent, the in-order predecessor will be one of the ancestors. To find such an ancestor, we traverse up the tree towards the root until we encounter a node y that is the right child of its parent. If such a node y is present, then the in-order predecessor of x is the parent of node y.

The critical question is: How can we move up in the BST? To implement this, we include a parent pointer in the BST node structure, which points to the parent of the given node.

Solution steps

If (x->left != NULL), we find the maximum node in the left subtree and return it as the predecessor, i.e., return bstMaximum(x->left).
Otherwise, if(x->parent != NULL && x->parent->right == x), we return x->parent as the predecessor.
Otherwise, we need to find the first ancestor of node x which is the right child of its parent. If such a node is present, then the in-order predecessor is its parent. To find this:
We start by initializing a pointer curr with node x and a pointer p to the parent of node x.
We now run a loop as long as p is not NULL and curr is the left child of its parent (p->left == curr).
Within the loop, we continue moving up by updating curr to p and p to its parent (p = p->parent).
At the end of the loop, curr will be the first ancestor of node x which is the right child of its parent, and p will be its parent. So, we return pointer p as the predecessor.

Solution code C++

BSTNode* bstMaximum(BSTNode* root) 
{
    while (root->right != NULL)
        root = root->right;
    return root;
}

BSTNode* inorderPredecessor(BSTNode* x) 
{
    if (x == NULL)
        return NULL;

    if (x->left != NULL)
        return bstMaximum(x->left);
    
    else if(x->parent != NULL && x->parent->right == x)
        return x->parent;
    
    else
    {
        BSTNode* p = x->parent;
        BSTNode* curr = x;

        while (p != NULL && p->left == curr) 
        {
            curr = p;
            p = p->parent;
        }

        return p;
    }    
}

Solution code Python

def bstMaximum(root):
    while root.right is not None:
        root = root.right
    return root

def inorderPredecessor(x):
    if x is None:
        return None

    if x.left is not None:
        return bstMaximum(x.left)

    elif x.parent is not None and x.parent.right == x:
        return x.parent

    else:
        p = x.parent
        curr = x

        while p is not None and p.left == curr:
            curr = p
            p = p.parent

        return p

Time and space complexity analysis

If the left child of node x is present, then the maximum value in the left subtree will be the predecessor. In the worst case, node x will be the root node and the node with minimum value in the left subtree is the deepest leaf node. Here we need to traverse the complete height of the tree. So the time complexity in the worst case = O(h).

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

Overall, the time complexity will be O(h), which depends on the height of the tree. Since we are storing an extra parent pointer inside each node, the space complexity = O(n).

Iterative solution without using parent pointer

Storing a parent pointer inside the BST node helps us easily traverse up the tree, but it requires O(n) extra space. Now, the critical question is: Can we solve this problem without using a parent pointer? Let’s think!

The idea is: We maintain a pred pointer to track the predecessor 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 left. There is no need to update the pred pointer because the current node root will not be the candidate for the predecessor. The idea is simple: the value of the pred->key will always be less than the x->key.
If x->key > root->key, we update the pred pointer to the current node root and move to the right subtree (pred = root and root = root->right). We update the pred pointer because the current node root will be the candidate for the predecessor. Think!
If x->key == root->key, we have found the node. So we check if the left subtree of node x exists. If it does, we update the pred pointer to the maximum node in the left subtree (pred = bstMaximum(x->left)) and break from the loop.

By the end of this loop, we return the pred pointer.

Solution code C++

BSTNode* bstMaximum(BSTNode* root) 
{
    while (root->right != NULL)
        root = root->right;
    return root;
}

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

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

    return pred;
}

Solution code Python

def bstMaximum(root):
    while root.right is not None:
        root = root.right
    return root

def inorderPredecessor(root, x):
    if root is None:
        return None

    pred = None
    while root is not None:
        if x.key < root.key:
            root = root.left
        elif x.key > root.key:
            pred = root
            root = root.right
        else:
            if root.left is not None:
                pred = bstMaximum(root.left)
            break
    
    return pred

Time and space complexity analysis

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

Recursive solution without using parent pointer

In the above solution, we iteratively move down the tree to search for node x and update the predecessor. The critical question is: Can we think of implementing it using recursion?

Solution idea

The idea is to recursively move down to search for node x in the BST and keep updating the predecessor. When we find the node x and the left subtree of node x is present, we return the node with the maximum value in the left subtree of x. If the left subtree of node x doesn't exist, then the in-order predecessor is one of its ancestors, which has already been updated while searching.

If root->key == x->key, we check if node x has a left subtree. If it does, we return the maximum node in the left subtree as the predecessor, i.e., return bstMaximum(root->left).
If root->key > x->key, we recursively call the same function on the left subtree to continue searching for the predecessor in the left subtree, i.e., inorderPredecessor(root->left, pred, x). There is no need to update the pred pointer because pred->key will always be less than the x->key.
If root->key < x->key, we update the pred pointer to the current node root and recursively call the same function on the right subtree, i.e., inorderPredecessor(root->right, pred, x).
Finally, we return the pred pointer.

Solution code C++

BSTNode* bstMaximum(BSTNode* root) 
{
    while (root->right != NULL)
        root = root->right;
    return root;
}

BSTNode* inorderPredecessor(BSTNode* root, BSTNode* pred, BSTNode* x) 
{
    if (root == NULL)
        return NULL;

    if (root->key == x->key) 
    {
        if (x->left != NULL)
            return bstMaximum(x->left);
    } 
    else if (root->key > x->key)
        return inorderPredecessor(root->left, pred, x);
    else 
    {
        pred = root;
        return inorderPredecessor(root->right, pred, x);
    }

    return pred;
}

Solution code Python

def bstMaximum(root):
    while root.right:
        root = root.right
    return root

def inorderPredecessor(root, pred, x):
    if root is None:
        return None

    if root.key == x.key:
        if x.left:
            return bstMaximum(x.left)
    elif root.key > x.key:
        return inorderPredecessor(root.left, pred, x)
    else:
        pred = root
        return inorderPredecessor(root.right, pred, x)

    return pred

Time and space complexity analysis

At each step of recursion, we are going one level down. So in the worst case, we will be traversing the complete height of the tree. So time complexity = O(h).

Space complexity will depend on the size of the call stack, which will be equal to the height of the recursion tree. So space complexity = O(h).

Using inorder traversal of the binary search tree

Solution idea

As we know, the in-order predecessor of node x is the node that will be visited just before node x in the in-order traversal. The critical question is: Can we solve it using an in-order traversal? Here's an idea!

We traverse the BST in an in-order manner and keep track of the previous node visited. When we find the target node, the previous node represents its in-order predecessor. To ensure that the changes to the previous node are propagated correctly across the recursive calls, we use a pointer prev and pass it as a reference during the recursive call.

Solution code C++

BSTNode* inorder(BSTNode* root, BSTNode* x, BSTNode*& prev) 
{
    if (root == NULL)
        return NULL;

    BSTNode* leftResult = inorder(root->left, x, prev);
    if (leftResult != NULL)
        return leftResult;

    if (x->key == root->key)
        return prev;

    prev = root;

    return inorder(root->right, x, prev);
}

BSTNode* inorderPredecessor(BSTNode* root, BSTNode* x) 
{
    if (root == NULL || x == NULL)
        return NULL;

    BSTNode* prev = NULL;
    return inorder(root, x, prev);
}

Solution code Python

def inorder(root, x, prev):
    if root is None:
        return None

    leftResult = inorder(root.left, x, prev)
    if leftResult is not None:
        return leftResult

    if x.key == root.key:
        return prev

    prev[0] = root

    return inorder(root.right, x, prev)

def inorderPredecessor(root, x):
    if root is None or x is None:
        return None

    prev = [None]
    return inorder(root, x, prev)

Time and space complexity analysis

In the worst case, we will traverse each node only once using an in-order traversal. So, the time complexity will be O(n) in the worst case. Inside the code, we use constant extra space, but recursion will utilize a call stack with a size equal to the height of the tree. So, the space complexity is O(h).

Critical idea to think!

How can we solve this problem using iterative in-order traversal?
How can we modify the above code to find both the in-order successor and predecessor together?
In the first approach using a parent pointer, is there a need to handle this condition: if (x->parent != NULL && x->parent->right == x)?
In the second and third approaches, why do we update the pred pointer when we move to the right subtree?
Which method is better in terms of time and space complexity?
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?
Can we consider implementing the above code in a different manner?

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

Let’s understand the problem

Iterative solution using parent pointer

Solution idea

Solution steps

Solution code C++

Solution code Python

Time and space complexity analysis

Iterative solution without using parent pointer

Solution code C++

Solution code Python

Time and space complexity analysis

Recursive solution without using parent pointer

Solution idea

Solution code C++

Solution code Python

Time and space complexity analysis

Using inorder traversal of the binary search tree

Solution idea

Solution code C++

Solution code Python

Time and space complexity analysis

Critical idea to think!

Suggested coding questions to practice

More from EnjoyAlgorithms

Self-paced Courses and Blogs