LeetCode 285: Inorder Successor in BST

Problem Restatement

We are given the root of a binary search tree and a node p inside that tree.

We need to return the inorder successor of p.

In a binary search tree, inorder traversal visits nodes in sorted order.

So the inorder successor of p is the node with the smallest value greater than p.val.

If no such node exists, return None.

The source statement defines the successor as the node with the smallest key greater than p.val, and the return value is a TreeNode, not just the value.

Input and Output

Function shape:

class Solution:
    def inorderSuccessor(self, root: TreeNode, p: TreeNode) -> TreeNode:
        ...

Examples

For:

root = [2, 1, 3]
p = 1

The inorder traversal is:

1, 2, 3

The node after 1 is 2.

So the answer is the node with value:

2

For:

root = [5, 3, 6, 2, 4, None, None, 1]
p = 6

The inorder traversal is:

1, 2, 3, 4, 5, 6

There is no node after 6.

So the answer is:

None

First Thought: Inorder Traversal

A direct solution is to perform inorder traversal and store the nodes in a list.

Because this is a BST, the list will be sorted by node value.

Then we find p in the list and return the next node.

class Solution:
    def inorderSuccessor(self, root: TreeNode, p: TreeNode) -> TreeNode:
        nodes = []

        def inorder(node):
            if node is None:
                return

            inorder(node.left)
            nodes.append(node)
            inorder(node.right)

        inorder(root)

        for i in range(len(nodes)):
            if nodes[i] == p:
                if i + 1 < len(nodes):
                    return nodes[i + 1]
                return None

        return None

This is correct, but it visits every node and stores every node.

Problem With Full Traversal

The BST property gives us more structure.

We do not need the full sorted list.

We only need the smallest node whose value is greater than p.val.

That means we can search the tree like binary search.

At each node:

• If node.val > p.val, this node may be the answer.
• If node.val <= p.val, this node cannot be the answer.

So we can walk down the tree while keeping the best candidate seen so far.

Key Insight

The successor is:

the smallest value greater than p.val

When we stand at a node root:

If:

root.val > p.val

then root is a valid successor candidate.

But there might be a smaller valid node in root.left.

So we save root and move left.

If:

root.val <= p.val

then root and everything in its left subtree are too small.

So we move right.

Algorithm

Initialize:

successor = None

Then walk down the tree.

While root exists:

1. If root.val > p.val, save root as a candidate and go left.
2. Otherwise, go right.

At the end, return successor.

Correctness

The algorithm maintains successor as the best candidate seen so far: a node greater than p.val, with the smallest value among such nodes encountered on the search path.

When root.val > p.val, root is a valid successor candidate. Since a smaller valid successor may exist in the left subtree, the algorithm records root and searches left.

When root.val <= p.val, neither root nor any node in its left subtree can be the successor, because all of them have values at most root.val. The successor must be in the right subtree, so the algorithm searches right.

Every move discards only nodes that cannot improve the current answer. If a better candidate exists, the BST ordering keeps it on the path the algorithm follows.

When the search ends, no unexplored node can be a smaller valid successor than the stored candidate. Therefore successor is exactly the node with the smallest value greater than p.val, or None if no such node exists.

Complexity

Here, h is the height of the tree.

For a balanced tree, h = O(log n).

For a skewed tree, h = O(n).

Implementation

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def inorderSuccessor(self, root: TreeNode, p: TreeNode) -> TreeNode:
        successor = None

        while root:
            if root.val > p.val:
                successor = root
                root = root.left
            else:
                root = root.right

        return successor

Code Explanation

We start with no candidate:

successor = None

Then we search while the current node exists:

while root:

If the current node is greater than p, it can be the successor:

if root.val > p.val:
    successor = root
    root = root.left

We go left because we want a smaller value that is still greater than p.val.

Otherwise:

else:
    root = root.right

The current node is too small, so we need larger values.

Finally:

return successor

If successor was never updated, p has no inorder successor.

Testing

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

def test_inorder_successor():
    s = Solution()

    root = TreeNode(2)
    root.left = TreeNode(1)
    root.right = TreeNode(3)

    assert s.inorderSuccessor(root, root.left).val == 2
    assert s.inorderSuccessor(root, root).val == 3
    assert s.inorderSuccessor(root, root.right) is None

    root2 = TreeNode(5)
    root2.left = TreeNode(3)
    root2.right = TreeNode(6)
    root2.left.left = TreeNode(2)
    root2.left.right = TreeNode(4)
    root2.left.left.left = TreeNode(1)

    assert s.inorderSuccessor(root2, root2.left).val == 4
    assert s.inorderSuccessor(root2, root2.left.right).val == 5
    assert s.inorderSuccessor(root2, root2.right) is None

    print("all tests passed")

test_inorder_successor()

Test meaning: