Find the Inorder Predecessor in a Binary Search Tree

Problem Statement❯

Given a Binary Search Tree (BST) and a target node, find the inorder predecessor of the given node. The inorder predecessor of a node is the previous node in the in-order traversal of the BST. If no predecessor exists (i.e., the node is the first in in-order traversal), return null or equivalent.

Examples❯

Input BST	Target Node (p)	Inorder Predecessor	Description
[20, 10, 30, 5, 15, 25, 35]	15	10	10 is the rightmost node in the left subtree of 15 (which has no left child), so the predecessor is its ancestor 10.
[20, 10, 30, 5, 15, 25, 35]	25	20	25 has no left child, and its predecessor is the last ancestor smaller than 25, which is 20.
[20, 10, 30, 5, 15, 25, 35]	10	5	10 has a left child 5, which is its predecessor as it’s the rightmost in the left subtree.
[20, 10, 30, 5, 15, 25, 35]	5	null	5 is the smallest node and has no left subtree or smaller ancestor, so it has no inorder predecessor.
[50, 30, 70, 20, 40, 60, 80]	60	50	60 has no left child; the last smaller ancestor is 50, making it the predecessor.

Solution❯

Case 1: The Node Has a Left Subtree

If the target node has a left child, then its inorder predecessor is the rightmost node in that left subtree. This is because in an in-order traversal (Left → Root → Right), the predecessor will be the largest node in the left subtree.

For example, if the node is 6 and its left subtree is rooted at 4, and 4 has a right child 5, then the inorder predecessor is 5.

Case 2: The Node Does Not Have a Left Subtree

If the node does not have a left child, we need to look upward in the tree. The inorder predecessor will be one of its ancestors — the first ancestor where the target node lies in the right subtree of that ancestor. This is because the last node visited before the current node in in-order traversal must be from an ancestor that leads to this node via its right branch.

For instance, if the node is 3 and there is no left subtree, and the path from root to 3 was 1 → 2 → 3, then the predecessor is 2.

Case 3: The Node is the Leftmost Node

If the node is the smallest in the BST (i.e., the leftmost node in the entire tree), then it has no inorder predecessor. There’s no other node that comes before it in in-order traversal, so we return null.

Example: In the BST [1, 2, 3], for target node 1, the result is null.

Case 4: Tree is Empty

If the BST is empty, then there's no node to search and obviously no predecessor. In this case, we return null right away without further processing.

Case 5: Tree Has Only One Node

If the BST has only a single node, and that node is the target node, then it cannot have any predecessor. Thus, the answer is null.

Example: Tree = [5], target = 5 → output = null.

Algorithm Steps❯

If the target node has a left subtree, the inorder predecessor is the rightmost node in that left subtree. Traverse to the left child and then keep moving to the right child until no more right children exist.
If the target node does not have a left subtree, traverse up using the parent pointers until you find an ancestor of which the target node is in the right subtree. That ancestor is the inorder predecessor.
If no such ancestor exists, then the target node has no inorder predecessor.

Code

Python

Java

JavaScript

C++

Kotlin

Swift

Php

class TreeNode:
    def __init__(self, val=0, left=None, right=None, parent=None):
        self.val = val
        self.left = left
        self.right = right
        self.parent = parent

def inorderPredecessor(node):
    if node.left:
        pred = node.left
        while pred.right:
            pred = pred.right
        return pred
    curr = node
    while curr.parent and curr == curr.parent.left:
        curr = curr.parent
    return curr.parent

# Example usage:
if __name__ == '__main__':
    # Construct BST:
    #         20
    #        /  \
    #      10    30
    #        
    #         15
    root = TreeNode(20)
    root.left = TreeNode(10, parent=root)
    root.right = TreeNode(30, parent=root)
    root.left.right = TreeNode(15, parent=root.left)
    node = root.left.right
    pred = inorderPredecessor(node)
    if pred:
        print(f'Inorder predecessor of {node.val} is {pred.val}')
    else:
        print('No inorder predecessor found')

⬅ Previous TopicFind the Inorder Successor in a Binary Search Tree

Next Topic ⮕Check if a Binary Tree is a Binary Search Tree