Inorder Successor in BST

Description

Given the root of a Binary Search Tree (BST) and a reference to a node p within the tree, find the in-order successor of node p.

The in-order successor of a node is the node that appears immediately after it in an in-order traversal of the BST. Since an in-order traversal of a BST visits nodes in ascending order of their values, the in-order successor of p is the node with the smallest value that is strictly greater than p.val.

If no such node exists (i.e., p holds the largest value in the tree), return null.

BST showing inorder traversal order and the successor relationship between nodes 12 and 13

Examples

Example 1

Input: root = [15, 10, 20, 6, 12, 18, 25, null, null, null, 13], p = node with value 12

       15
      /  \
    10    20
   / \   / \
  6  12 18  25
       \
       13

Output: Node with value 13

Explanation: The in-order traversal of this BST produces [6, 10, 12, 13, 15, 18, 20, 25]. Node 12 sits at position 2 (0-indexed) in this sorted sequence. The very next node is 13 at position 3. Since node 12 has a right child (13), the successor is found as the leftmost node in its right subtree — which is node 13 itself.

Example 2

Input: root = [15, 10, 20, 6, 12, 18, 25, null, null, null, 13], p = node with value 13

       15
      /  \
    10    20
   / \   / \
  6  12 18  25
       \
       13

Output: Node with value 15

Explanation: The in-order sequence is [6, 10, 12, 13, 15, 18, 20, 25]. Node 13 has no right child, so its successor is not found in a right subtree. Instead, node 13 lies within the left subtree of the root node 15 — meaning 15 is the nearest ancestor for which the entire path from 13 leads through left children. Therefore, the successor of 13 is 15.

Example 3

Input: root = [15, 10, 20, 6, 12, 18, 25, null, null, null, 13], p = node with value 25

       15
      /  \
    10    20
   / \   / \
  6  12 18  25
       \
       13

Output: null

Explanation: Node 25 is the rightmost node in the BST, meaning it holds the largest value. No node in the tree has a value greater than 25, so the in-order successor does not exist. We return null.

Constraints

1 ≤ Number of nodes in the tree ≤ 10^4
-10^5 ≤ Node.val ≤ 10^5
All node values in the BST are unique
p is guaranteed to exist in the tree

Editorial

Brute Force

Intuition

Think about what an in-order traversal of a BST gives us: it visits every node in ascending order of value. So if we collect all nodes during this traversal into a list, we get a perfectly sorted sequence.

Once we have that sorted list, finding the successor of any node becomes trivial — just locate the node in the list and look at the element right after it. If it exists, that is the successor. If the node is the last element, there is no successor.

This is like arranging a deck of numbered cards in order on a table. To find the card that comes after card number 12, you simply scan until you spot 12, then peek at the next card.

Step-by-Step Explanation

Let's trace through the BST from Example 1 with p = 12:

Step 1: Perform an in-order traversal of the entire BST to collect all node values in sorted order.

Traversal visits nodes in order: 6, 10, 12, 13, 15, 18, 20, 25
Resulting sorted array: [6, 10, 12, 13, 15, 18, 20, 25]

Step 2: Scan the sorted array from left to right to find the target value 12.

Index 0: value is 6 — not our target. Continue.
Index 1: value is 10 — not our target. Continue.
Index 2: value is 12 — found our target node!

Step 3: Check whether a next element exists in the array.

Next index: 2 + 1 = 3, and 3 < 8 (array length), so a next element does exist.

Step 4: The value at index 3 is 13. This is the smallest value greater than 12 in the BST.

Return the node with value 13 as the in-order successor.

Brute Force — Scanning Sorted Array for Successor of 12 — After collecting all BST values via in-order traversal into a sorted array, we scan to find node 12 and return the next element as the successor.

Algorithm

Perform an in-order traversal of the BST, collecting all nodes into a list in sorted order.
Iterate through the list to find node p (by reference).
If p is found at index i and i + 1 is within bounds, return the node at index i + 1.
If p is the last element in the list (no next element), return null.

Code

class Solution {
public:
    TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {
        vector<TreeNode*> nodes;
        inorder(root, nodes);

        for (int i = 0; i < (int)nodes.size(); i++) {
            if (nodes[i] == p && i + 1 < (int)nodes.size()) {
                return nodes[i + 1];
            }
        }
        return nullptr;
    }

    void inorder(TreeNode* node, vector<TreeNode*>& nodes) {
        if (!node) return;
        inorder(node->left, nodes);
        nodes.push_back(node);
        inorder(node->right, nodes);
    }
};

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

        def inorder(node):
            if not node:
                return
            inorder(node.left)
            nodes.append(node)
            inorder(node.right)

        inorder(root)

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

class Solution {
    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        List<TreeNode> nodes = new ArrayList<>();
        inorder(root, nodes);

        for (int i = 0; i < nodes.size(); i++) {
            if (nodes.get(i) == p && i + 1 < nodes.size()) {
                return nodes.get(i + 1);
            }
        }
        return null;
    }

    private void inorder(TreeNode node, List<TreeNode> nodes) {
        if (node == null) return;
        inorder(node.left, nodes);
        nodes.add(node);
        inorder(node.right, nodes);
    }
}

Complexity Analysis

Time Complexity: O(n)

The in-order traversal visits every node in the tree exactly once, taking O(n) time. After that, scanning the array to find p takes up to O(n) in the worst case. Combined, the total time is O(n).

Space Complexity: O(n)

We store all n nodes in an auxiliary list. Additionally, the recursive in-order traversal uses O(h) space on the call stack, where h is the tree height. Since the list dominates, the overall space complexity is O(n).

Why This Approach Is Not Efficient

The brute force performs an in-order traversal of the entire BST, visiting all n nodes and storing them in an array. This takes O(n) time and O(n) space regardless of where node p is located in the tree.

Consider a BST with 10,000 nodes where p is the root. The brute force still visits every single node and allocates an array of 10,000 elements — even though the answer might be found by examining just a handful of nodes along one path.

The fundamental waste is that we ignore the BST's ordering property. In a BST:

If a node's value is greater than p.val, the successor could be this node or something smaller in its left subtree — but nothing in its right subtree matters.
If a node's value is less than or equal to p.val, the successor cannot be this node or anything in its left subtree — we must look right.

By leveraging these decisions at each node, we can follow a single root-to-leaf path, visiting at most O(h) nodes where h is the tree height. For a balanced BST, this is O(log n) — exponentially better than O(n).

Optimal Approach - BST Property Search

Intuition

Instead of collecting every node and then searching, we can think of this as a guided treasure hunt through the tree. Starting at the root, at every node we ask one simple question: is this node's value greater than p's value?

If yes, this node is a valid successor candidate — its value is strictly greater than p.val. But there might be an even smaller valid successor hiding in the left subtree (where values are smaller). So we save this candidate and explore left.

If no (the node's value is less than or equal to p.val), this node cannot be the successor. Everything in its left subtree is even smaller, so no help there either. We must explore the right subtree to find larger values.

This is like a game of "warmer/colder". Each decision narrows our search space by half (in a balanced tree), and we keep refining our best candidate until we run out of nodes to check. The last candidate saved is guaranteed to be the smallest value greater than p.val — exactly the in-order successor.

The beauty of this approach is that we never need to visit more nodes than the height of the tree, and we use no extra storage beyond a single pointer.

Step-by-Step Explanation

Let's trace through the same BST from Example 1 with p = 12:

Step 1: Begin at the root, node 15. Initialize successor = null.

Is 15 > 12? Yes.
Node 15 is a valid successor candidate. Save successor = 15.
There might be a smaller valid successor in the left subtree. Move left to node 10.

Step 2: At node 10.

Is 10 > 12? No (10 ≤ 12).
Node 10 is too small to be a successor. Everything in its left subtree is even smaller.
Move right to node 12.

Step 3: At node 12.

Is 12 > 12? No (12 equals p.val — we need strictly greater).
This is the target node itself. It cannot be its own successor.
Move right to node 13.

Step 4: At node 13.

Is 13 > 12? Yes!
Update successor from 15 to 13. Node 13 is a better (smaller) candidate than 15.
Try to find something even smaller by moving left.

Step 5: Left child of 13 is null. No further nodes to explore. Search terminates.

Step 6: Return successor = 13. We refined our candidate from 15 → 13 during the traversal, visiting only 4 out of 8 nodes.

BST Property Search — Finding Successor of Node 12 — Watch how we traverse from the root, narrowing down the successor candidate at each step using BST ordering. Every time we find a node greater than p, we save it and search left for something even smaller.

Algorithm

Initialize successor = null.
Start at the root and loop while the current node is not null:
- If current.val > p.val: this node is a potential successor. Save it and move left (to find a possibly smaller valid successor).
- If current.val ≤ p.val: this node cannot be the successor. Move right (to find larger values).
When the loop ends (current is null), return successor.

Code

class Solution {
public:
    TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {
        TreeNode* successor = nullptr;

        while (root != nullptr) {
            if (root->val > p->val) {
                successor = root;
                root = root->left;
            } else {
                root = root->right;
            }
        }

        return successor;
    }
};

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

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

        return successor

class Solution {
    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        TreeNode successor = null;

        while (root != null) {
            if (root.val > p.val) {
                successor = root;
                root = root.left;
            } else {
                root = root.right;
            }
        }

        return successor;
    }
}

Complexity Analysis

Time Complexity: O(h), where h is the height of the BST

We follow a single path from the root toward a leaf, making one comparison per node. In the worst case we visit h nodes (the full height of the tree). For a balanced BST, h = O(log n), so the time is O(log n). For a completely skewed tree, h = O(n).

Space Complexity: O(1)

We use only a single pointer variable (successor) to track our best candidate. The iterative traversal requires no recursion stack or auxiliary data structures, so space usage is constant regardless of tree size.