LeetCode 285 - Inorder Successor in BST

This problem asks us to find the in-order successor of a given node p inside a Binary Search Tree, abbreviated as BST. An in-order traversal of a BST visits nodes in sorted order: 1. Traverse the left subtree 2. Visit the current node 3.

leetcodemediumtreedepth-first-searchbinary-search-treebinary-tree

LeetCode Problem 285

Difficulty: 🟡 Medium
Topics: Tree, Depth-First Search, Binary Search Tree, Binary Tree

Solution

Problem Understanding

This problem asks us to find the in-order successor of a given node p inside a Binary Search Tree, abbreviated as BST.

An in-order traversal of a BST visits nodes in sorted order:

  1. Traverse the left subtree
  2. Visit the current node
  3. Traverse the right subtree

Because BSTs maintain the ordering property:

  • Every node in the left subtree is smaller than the current node
  • Every node in the right subtree is larger than the current node

the in-order traversal naturally produces values in ascending order.

The in-order successor of a node p is the node that appears immediately after p in this sorted traversal order. More specifically, it is the node with the smallest value strictly greater than p.val.

The input consists of:

  • root, the root node of a BST
  • p, a node that exists somewhere inside the tree

The output should be:

  • The TreeNode representing the successor
  • None or nil if no successor exists

The constraints tell us that the tree can contain up to 10^4 nodes. This is large enough that we should avoid unnecessarily expensive operations if a more efficient BST-based solution exists.

The problem also guarantees:

  • All node values are unique
  • p always exists in the tree

These guarantees simplify the logic because we never need to handle duplicates or missing target nodes.

Several edge cases are important:

  • p may be the largest node in the BST, in which case no successor exists
  • p may have a right subtree, which changes how the successor is found
  • p may not have a right subtree, requiring us to search among ancestors
  • The tree may contain only one node

A naive implementation can easily fail when handling nodes without right children or when incorrectly tracking ancestor candidates.

Approaches

Brute Force Approach

The brute-force solution performs a complete in-order traversal of the BST and stores all visited nodes in a list.

Since in-order traversal of a BST produces nodes in sorted order, we can scan through the resulting list and locate node p. The next node in the list, if it exists, is the in-order successor.

This approach is straightforward and easy to reason about because it directly simulates the definition of in-order successor.

The algorithm works as follows:

  1. Perform an in-order DFS traversal
  2. Store nodes in an array
  3. Find the index of p
  4. Return the next node if one exists

Although correct, this solution is inefficient because it traverses the entire tree even when the answer could be determined much earlier using BST properties.

Optimal Approach

The key observation is that BST ordering allows us to search intelligently instead of traversing the entire tree.

There are two important cases:

  1. If p has a right subtree, then the successor is the leftmost node in p.right
  2. If p does not have a right subtree, then the successor is one of its ancestors

While traversing from the root toward p, whenever we move left from a node, that node becomes a potential successor because it is larger than p. We keep track of the smallest such candidate.

This allows us to find the successor in O(h) time, where h is the tree height.

Approach Time Complexity Space Complexity Notes
Brute Force O(n) O(n) Full in-order traversal and array storage
Optimal O(h) O(1) Uses BST properties to search efficiently

Here, h is the height of the tree. In a balanced BST, this becomes O(log n).

Algorithm Walkthrough

Optimal BST Search Algorithm

  1. Initialize a variable called successor as None.

This variable stores the best candidate successor found so far. At any point during traversal, it represents the smallest node greater than p.val. 2. Start traversing from the root.

We move through the BST similarly to standard BST search logic. 3. Compare p.val with the current node's value.

If p.val is smaller than the current node's value, then the current node could be the successor because it is greater than p. 4. Update successor and move left.

Since we want the smallest value greater than p.val, we store the current node as a candidate and continue searching the left subtree for a potentially smaller valid successor. 5. Otherwise, move right.

If p.val is greater than or equal to the current node's value, then the successor cannot be in the left subtree or the current node itself. We move right to search for larger values. 6. Continue until traversal ends.

Once the traversal reaches None, the stored successor is the correct answer.

Why it works

The algorithm maintains an invariant:

  • successor always stores the smallest node encountered so far whose value is greater than p.val

Whenever we move left from a node, that node becomes a valid candidate because it is larger than p. Moving left searches for an even smaller valid candidate.

Whenever we move right, the current node cannot be the successor because its value is too small.

Because BST ordering guarantees structured value relationships, this process eventually finds the smallest node greater than p.val, which is exactly the in-order successor definition.

Python Solution

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

from typing import Optional

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

        successor = None
        current = root

        while current:
            if p.val < current.val:
                successor = current
                current = current.left
            else:
                current = current.right

        return successor

The implementation starts by initializing successor to None. This handles the case where no valid successor exists.

The variable current traverses the BST from the root downward.

Whenever p.val < current.val, the current node becomes a candidate successor because it is larger than p. However, there may still be a smaller valid successor in the left subtree, so the algorithm stores the candidate and moves left.

When p.val >= current.val, the current node cannot be the successor. The algorithm therefore moves right to search for larger values.

The loop continues until the traversal reaches a null pointer. At that point, the best candidate stored in successor is returned.

This implementation avoids recursion and auxiliary data structures, resulting in constant extra space usage.

Go Solution

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func inorderSuccessor(root *TreeNode, p *TreeNode) *TreeNode {
    var successor *TreeNode
    current := root

    for current != nil {
        if p.Val < current.Val {
            successor = current
            current = current.Left
        } else {
            current = current.Right
        }
    }

    return successor
}

The Go implementation mirrors the Python logic closely.

Instead of None, Go uses nil pointers. The variable successor is initialized as a nil pointer and updated whenever a better candidate is found.

Because Go uses explicit pointer types, all tree navigation occurs through *TreeNode references.

No special integer overflow handling is required because node values are well within Go's integer range.

Worked Examples

Example 1

Input:

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

Tree structure:

    2
   / \
  1   3

We want the smallest value greater than 1.

Step Current Node Successor Action
1 2 None 1 < 2, update successor to 2, move left
2 1 2 1 >= 1, move right
3 None 2 Traversal ends

Final answer:

2

Example 2

Input:

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

Tree structure:

        5
       / \
      3   6
     / \
    2   4
   /
  1

We want the smallest value greater than 6.

Step Current Node Successor Action
1 5 None 6 >= 5, move right
2 6 None 6 >= 6, move right
3 None None Traversal ends

No valid successor exists.

Final answer:

null

Complexity Analysis

Measure Complexity Explanation
Time O(h) Traverses only one root-to-leaf path
Space O(1) Uses only a few pointer variables

The algorithm follows a single traversal path through the BST. In a balanced tree, the height h is O(log n). In the worst case of a completely skewed tree, the height becomes O(n).

The solution uses constant auxiliary space because it stores only a few references regardless of tree size.

Test Cases

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

solution = Solution()

# Test 1: Basic example with successor
root1 = TreeNode(2)
root1.left = TreeNode(1)
root1.right = TreeNode(3)

assert solution.inorderSuccessor(root1, root1.left).val == 2  # successor exists

# Test 2: Largest node has no successor
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 solution.inorderSuccessor(root2, root2.right) is None  # no successor

# Test 3: Node with right subtree
root3 = TreeNode(20)
root3.left = TreeNode(10)
root3.right = TreeNode(30)
root3.left.right = TreeNode(15)

assert solution.inorderSuccessor(root3, root3.left).val == 15  # left child successor

# Test 4: Single node tree
root4 = TreeNode(1)

assert solution.inorderSuccessor(root4, root4) is None  # only node

# Test 5: Successor is ancestor
root5 = TreeNode(5)
root5.left = TreeNode(3)
root5.right = TreeNode(7)
root5.left.left = TreeNode(2)
root5.left.right = TreeNode(4)

assert solution.inorderSuccessor(root5, root5.left.right).val == 5  # ancestor successor

# Test 6: Skewed tree
root6 = TreeNode(1)
root6.right = TreeNode(2)
root6.right.right = TreeNode(3)

assert solution.inorderSuccessor(root6, root6.right).val == 3  # skewed right tree

# Test 7: Deep left traversal
root7 = TreeNode(50)
root7.left = TreeNode(30)
root7.left.left = TreeNode(20)
root7.left.right = TreeNode(40)
root7.left.right.right = TreeNode(45)

assert solution.inorderSuccessor(root7, root7.left.right).val == 45  # deeper subtree successor
Test Why
[2,1,3], p=1 Standard successor lookup
p=6 in second example Verifies handling when no successor exists
Node with right subtree Ensures subtree logic works correctly
Single node tree Smallest possible input
Successor is ancestor Verifies ancestor tracking
Right-skewed tree Tests worst-case height
Deep left traversal Tests repeated candidate updates

Edge Cases

One important edge case occurs when p is the maximum value in the BST. In this situation, no node has a larger value, so the correct answer is None. A buggy implementation might accidentally return the last ancestor visited. This implementation avoids that issue because successor is updated only when a node larger than p is encountered.

Another important case is when p has a right subtree. The successor should then be the leftmost node in that subtree. The iterative BST search naturally handles this because traversal continues into the right subtree and keeps updating smaller valid candidates while moving left.

A third important edge case is a highly skewed tree. For example, a tree shaped like a linked list can expose recursion depth problems in recursive implementations. This solution uses iterative traversal, so it avoids recursion stack growth entirely.

A fourth edge case occurs when the successor is an ancestor rather than a descendant. For example, if p = 4 in the tree [5,3,7,2,4], the successor is 5. The algorithm correctly handles this by remembering candidate ancestors whenever traversal moves left.