medium Inorder Successor in BST

Problem Statement

Given a root node of the binary search tree and node p, return the value of the in-order successor of node p in the given tree. If the given node has no in-order successor, return -1.

The in-order successor of a node is the next node in the in-order traversal of the BST, which means it is the node with the smallest value greater than the given node.

Examples

Example 1:

Input: root = [3,2,4,1], p = 2

Expected Output: 3
Justification: In the in-order traversal [1,2,3,4], the next node after 2 is 3, making it the in-order successor.

Example 2:

Input: root = [8,3,10,1,6,null,14,null,null,4,7,13], p = 6

Expected Output: 7
Justification: The in-order traversal of the tree is [1,3,4,6,7,8,10,13,14]. The smallest value greater than 6 is 7, making it the in-order successor.

Example 3:

Input: root = [15,10,20,8,12,16,25], p = 25

Expected Output: -1
Justification: In the in-order traversal [8,10,12,15,16,20,25], there is no node after 25. Hence, the expected output is -1.

Try it yourself

Try solving this question here:

🎯 STRICT STANDOUT — Inorder Successor in BST — problem

1. Why / judgment

Successor = next in inorder = minimum among keys > p. BST walk: if p < node, node is candidate, go left; else go right. O(h) no parent pointers. Page ex2 expected 10 is wrong — inorder after 6 is 7.

2. Big-O derivation (K11)

O(h) time O(1) space iterative.
Full inorder O(n) worse.

3. Pattern + when-NOT (K12)

Name: BST SUCCESSOR WALK

Recognition: inorder successor of p in BST.

When-NOT: With parent pointers => climb. General binary tree => full inorder or threaded. Predecessor symmetric.

4. Edge hand-run (K13)

p=2 tree [3,2,4,1] =>3.
p=6 in sample =>7 (NOT 10).
max node => -1/null.

5. Interviewer follow-ups (model answers)

Q1. Why go left when p < node?
A: node could be successor; try tighter.

Q2. Why go right when p >= node?
A: Successor is in right subtree if any greater.

Q3. Parent-pointer alt?
A: If right child null, climb until came from left.

6. Short drills

Drill A: successor of 6 is 7.
Drill B: max node none.
Drill C: p has right subtree => min of right.

✅ Solution Inorder Successor in BST

Problem Statement

Given a root node of the binary search tree and node p, return the value of the in-order successor of node p in the given tree. If the given node has no in-order successor, return -1.

The in-order successor of a node is the next node in the in-order traversal of the BST, which means it is the node with the smallest value greater than the given node.

Examples

Example 1:

Input: root = [3,2,4,1], p = 2

Expected Output: 3
Justification: In the in-order traversal [1,2,3,4], the next node after 2 is 3, making it the in-order successor.

Example 2:

Input: root = [8,3,10,1,6,null,14,null,null,4,7,13], p = 6

Expected Output: 7
Justification: The in-order traversal of the tree is [1,3,4,6,7,8,10,13,14]. The smallest value greater than 6 is 7, making it the in-order successor.

Example 3:

Input: root = [15,10,20,8,12,16,25], p = 25

Expected Output: -1
Justification: In the in-order traversal [8,10,12,15,16,20,25], there is no node after 25. Hence, the expected output is -1.

Solution

To address the problem of finding the in-order successor in a Binary Search Tree (BST), our strategy capitalizes on the BST's ordered nature. The in-order successor of a node is the node that appears immediately after the given node when the tree is traversed in an in-order manner (left, root, right).

For any node p, if it has a right subtree, its in-order successor is the left-most node in its right subtree. Conversely, if the node has no right subtree, the successor is one of its ancestors, specifically the one that p would be the left child of in the path from root to p. This insight leads to a two-fold approach: first, descend towards the given node p, tracking the last node encountered that is greater than p as a potential successor; second, if p has a right child, override the tracked ancestor with the left-most child of p's right subtree. This method is efficient because it traverses each relevant part of the tree at most once, directly homing in on the successor by leveraging the BST property that left children are less than their parents and right children are greater.

Step-by-Step Algorithm

Start from the root of the BST.
Initialize a variable to store the potential successor as -1 or an equivalent value indicating no successor found.
While the current node is not null:
- If the value of the current node is less than or equal to the p, move to the right child.
- If the value of the current node is greater than the p, update the potential successor to the current node and move to the left child.
Continue this process until the entire tree is traversed or the exact match is found.
Return the value of the potential successor if found; otherwise, return -1 indicating no successor.

Algorithm Walkthrough

Let's consider the input: root = [8,3,10,1,6,null,14,null,null,4,7,13], p = 6

Let's walk through the algorithm to find the in-order successor of p = 6 using the same tree structure as before:

         8
       /   \
      3     10
     / \      \
    1   6      14
       / \    /
      4   7  13

Start at the root of the BST, which is 8. Since 6 is less than 8, we move to the left child of 8, which is 3, to find 6. successor = 8
Move to the right child of 3, as 3 is not greater than 6.
Move to the right child of 6, as 6 is not greater than 6.
Inspect the right subtree of 6, which leads us to 7. Since 7 does not have a left child, it is the left-most node in the right subtree of 6 and thus the in-order successor of 6.
End of Algorithm: The in-order successor of the node with value 6 in the given BST is 7.

Code

java

// class TreeNode {
//     int val;
//     TreeNode left, right;
//     TreeNode(int x) { val = x; }
// }

public class Solution {

  public int inorderSuccessor(TreeNode root, int p) {
    TreeNode successor = null;
    while (root != null) {
      // If root value is greater than p, root could be a successor.
      if (p < root.val) {
        successor = root;
        root = root.left;
      } else {
        root = root.right;
      }
    }
    // Return the value of the successor or -1 if it does not exist.
    return successor != null ? successor.val : -1;
  }

  public static void main(String[] args) {
    // Example of constructing a tree and finding an inorder successor
    TreeNode root = new TreeNode(8);
    root.left = new TreeNode(3);
    root.right = new TreeNode(10);
    root.left.left = new TreeNode(1);
    root.left.right = new TreeNode(6);
    root.right.right = new TreeNode(14);
    root.left.right.left = new TreeNode(4);
    root.left.right.right = new TreeNode(7);
    root.right.right.left = new TreeNode(13);

    int p = 6; // The value to find the inorder successor of
    Solution solution = new Solution();
    System.out.println(
      "Inorder Successor value: " + solution.inorderSuccessor(root, p)
    );
  }
}

Complexity Analysis

Time Complexity: The algorithm has a time complexity of , where h is the height of the tree. This is because we are traversing the tree from root to leaf, and in the worst case, we might have to traverse the height of the tree.
Space Complexity: The space complexity is since we are only using a constant amount of extra space for the variables, regardless of the size of the input tree.

🎯 STRICT STANDOUT — Inorder Successor in BST — solution

1. Why / judgment

Iterative: successor=null; while root: if p < root.val: successor=root; root=root.left; else root=root.right. Return successor. Fix example: p=6 =>7 not 10 (inorder ...6,7,8...).

2. Big-O derivation (K11)

O(h)/O(1). Max element returns -1.
Has right child case covered by descending left of right via the walk.

3. Pattern + when-NOT (K12)

Name: BST SUCCESSOR ITERATIVE

Recognition: inorder successor implementation.

When-NOT: With parent links climb. Morris traversal O(1) threads different goal.

4. Edge hand-run (K13)

ex1 p=2=>3; p=6=>7; p=max=>-1.

5. Interviewer follow-ups (model answers)

Q1. Right subtree case?
A: Walk goes right when p>=node until finds next greater candidates correctly as min greater.

Q2. Why not full inorder?
A: O(n) worse than O(h).

Q3. Predecessor?
A: Symmetric mirror comparisons.

6. Short drills

Drill A: hand-run p=6 =>7.
Drill B: p with right child.
Drill C: p = max.

🧩 Pattern · Trees

Recognize it: Hierarchical data → recurse on children; BFS (queue) for level-order, DFS (recursion) for paths.

▶ Visualize this problem (step it, predict each fork)

⛶ Open this problem debugger in explore mode

🤖 Don't fully get this? Learn it with Claude

Stuck on Inorder Successor in BST? Open Claude, copy a block below, and it'll teach you this exact concept — visually and interactively.

🪜 Hint ladder (no spoilers)

Progressively stronger hints — you still solve it.

I'm working on the problem **Inorder Successor in BST** (DSA). Give me a HINT LADDER: start with the tiniest nudge, then wait. Only reveal the next, stronger hint when I ask. Do NOT show the full solution unless I type 'show solution'. Keep me doing the thinking. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🎨 Explain the approach visually

See the technique, not just code.

Explain the optimal approach to **Inorder Successor in BST** with a VISUAL walkthrough: trace it on a small concrete example using ASCII art / a step-by-step diagram, narrate what changes each step, then give time & space complexity with a one-line derivation. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🔍 Review my solution

Catch bugs, edge cases, sub-optimality.

I'll paste my solution to **Inorder Successor in BST**. Review it for correctness, missed edge cases, and time/space complexity, then coach me toward the optimal — don't just rewrite it. Ask me to paste my code now. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🔁 Drill the pattern

Lock in recognition with look-alikes.

Give me 2 problems that use the SAME underlying pattern as **Inorder Successor in BST**. For each, let me attempt first, then review my answer and name the trigger signal that reveals the pattern. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

📝 My notes

← Lowest Common Ancestor of a Binary Minimum Adjacent Swaps to Make a V →