Find the Inorder Successor in a Binary Search Tree - Algorithm & Code Examples

Problem Statement❯

Given a binary search tree (BST) and a node p in it, find the inorder successor of that node. The inorder successor of a node is the node with the smallest key greater than p.val.

Note: It is guaranteed that the given node p exists in the tree. However, the successor might or might not exist.

Examples❯

Input Tree	Target Node (p)	Inorder Successor	Description
[20, 10, 30, 5, 15, 25, 35]	15	20	Inorder successor of 15 is 20, the lowest ancestor for which 15 is in left subtree.
[20, 10, 30, 5, 15, 25, 35]	10	15	Successor is leftmost node in 10's right subtree: 15.
[20, 10, 30, 5, 15, 25, 35]	30	35	30 has a right child, and its leftmost node is 35 — the inorder successor.
[20, 10, 30, 5, 15, 25, 35]	35	null	35 is the rightmost node; it has no inorder successor.
[20, 10, null, 5, 15]	5	10	5 has no right child. Successor is the lowest ancestor for which 5 lies in the left subtree — 10.
[8, 3, 10, 1, 6, null, 14, null, null, 4, 7, 13]	6	7	6 has right child 7 → it's the inorder successor.

Solution❯

Case 1: Target node has a right child

If the target node p has a right child, then the inorder successor is the leftmost node in the right subtree. This is because, in an in-order traversal, we visit the left subtree, then the node, and then the right subtree. So, the smallest value in the right subtree will be the next one in sequence.

Example: In the tree [2, 4, 6, 8], if p = 4 and 4 has a right child 6, and 6 in turn has a left child 5, then the successor is 5 (the leftmost in the right subtree).

Case 2: Target node does not have a right child

If the target node p does not have a right child, then we have to look upward in the tree. The inorder successor is one of the ancestors — the first one whose value is greater than p.val. This works because once we go left from such an ancestor to reach p, that ancestor will be the next node visited in the in-order traversal.

We traverse from the root, and whenever p.val < current.val, we store the current node as a potential successor and move to the left child, narrowing down to a closer successor. If p.val >= current.val, we move right. Finally, the stored successor (if any) is our answer.

Case 3: Target node is the largest in the tree

When p is the rightmost node in the BST, there is no successor because no node has a value greater than p. In such a case, the answer is null.

This is common when the tree is skewed to the right or when the value of p is the maximum.

Case 4: Tree is empty or `p` is `null`

In this case, there is no node to compare or traverse. So, we simply return null. This is a boundary case, but important for robustness of your solution.

Case 5: Tree has only one node

If the tree contains only one node and that node is p, there’s no possibility for an inorder successor. The result is null.

This case helps us understand that successor depends on the tree structure, not just the node value.

Algorithm Steps❯

Given a binary search tree (BST) and a target node p.
If p.right exists, the inorder successor is the leftmost node in the right subtree.
If p.right does not exist, initialize successor = null and traverse the tree starting from the root:
While traversing, if p.val < current.val, update successor to the current node and move to current.left; otherwise, move to current.right.
After the traversal, the recorded successor is the inorder successor of p.

Code

Python

Java

JavaScript

C++

Kotlin

Swift

Php

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

def inorderSuccessor(root, p):
    if p.right:
        curr = p.right
        while curr.left:
            curr = curr.left
        return curr
    successor = None
    while root:
        if p.val < root.val:
            successor = root
            root = root.left
        else:
            root = root.right
    return successor

# Example usage:
if __name__ == '__main__':
    # Construct BST:
    #         5
    #        / \
    #       3   7
    #      / \   \
    #     2   4   8
    root = TreeNode(5, TreeNode(3, TreeNode(2), TreeNode(4)), TreeNode(7, None, TreeNode(8)))
    p = root.left  # Node with value 3
    successor = inorderSuccessor(root, p)
    print(successor.val if successor else None)

⬅ Previous TopicFind the Maximum Value in a Binary Search Tree

Next Topic ⮕Find the Inorder Predecessor in a Binary Search Tree

Comments

Loading comments...