L49. Inorder Successor/Predecessor in BST | 3 Methods

An Inorder Successor of a target node in a Binary Search Tree (BST) is the node that comes immediately after the target node in an Inorder Traversal (Left, Root, Right). Because a BST maintains a strict ordering property where every node on the left is smaller and every node on the right is larger, its inorder traversal naturally yields a sorted (ascending) array of values. Understanding how to efficiently find this successor without flattening the entire tree is a fundamental pattern in tree-based Data Structures and Algorithms.

1. Why Do We Need This? (Problem Statement & Context)

In database indexing and dynamic memory management implemented via Binary Search Trees, range queries and ordered iterations are frequent operations.

• The Core Problem: Given the root of a BST and a specific node or value (let's call it p), find the node whose value is the smallest among all values strictly greater than p.
• Edge Case / Boundary Condition: If the given value is the maximum element in the entire BST (e.g., 10 in a tree ranging from 1 to 10), there is no larger element. In this scenario, the algorithm must safely return null.

2. Core Mental Model & Inorder Property

To understand how successors work, consider the standard inorder traversal of a sample BST:

• If our target node value is 8, looking at the sorted sequence, the value immediately following 8 is 9. Therefore, 9 is the inorder successor.
• If our target node value is 10, nothing follows it in the sequence, meaning the successor is null.

Real-Life Analogy: Imagine looking up a name in a physical, alphabetical telephone directory. If you are standing at the name "Smith," you don't need to read every single name from the top of page one to find who comes next. You can use alphabetical ordering to skip huge blocks of irrelevant names and immediately hone in on the next entry. A BST successor search operates on this exact elimination principle.

3. Naive vs. Better Approach (Brute Force to Optimized Traversals)

Let's examine how solutions evolve from naive brute-force implementations to optimal space-time strategies.

4. Step-by-Step Evolution: The Optimal Successor Algorithm

Instead of visiting every node, we can use the BST search property to make intelligent decisions at every step.

Step-by-Key-Step Logic:

1. Initialize a successor pointer to null.
2. Start traversal at the root node.
3. Compare the current node's value with target value p:
   • Case A (root.val <= p): The current node is too small or equal to our target. Since all values to the left and the current node itself are $\le p$, they cannot be our successor. We must discard the left subtree and move strictly to the right.
   • Case B (root.val > p): The current node is strictly greater than p. This makes it a potential candidate for our successor! We store this node in our successor variable. However, could there be an even closer (smaller) value that is still greater than p further down? To check, we move to the left subtree.
4. Repeat this descent until our pointer hits null.

5. Walkthroughs with Concrete Examples

Example 1: Finding Successor of 8

Let's trace how our optimal algorithm finds the successor of 8:

           (5)
          /   \
        (3)     (7)
       /   \       \
     (2)   (4)     (9)
                   /  \
                 (8)  (10)

1. Start at Root (5): 5 <= 8 is true. 5 is too small. Store nothing, move right to 7.
2. At Node (7): 7 <= 8 is true. 7 is too small. Store nothing, move right to 9.
3. At Node (9): 9 <= 8 is false (9 > 8). This means 9 is a valid candidate!
   • Set successor = 9.
   • Since we want a potentially tighter (smaller) valid value, move left to 8.
4. At Node (8): 8 <= 8 is true. 8 is not greater than 8. Move right (which is null).
5. Termination: Reached null. Loop ends.
   • Final Successor: 9.

Example 2: Finding Successor of 3

Let's trace finding the successor of 3 on the same tree:

1. Start at Root (5): 5 > 3 is true.
   • 5 is a valid candidate! Set successor = 5.
   • Move left to 3 to find a closer candidate.
2. At Node (3): 3 <= 3 is true. Not strictly greater. Move right to 4.
3. At Node (4): 4 > 3 is true.
   • 4 is a better (smaller) valid candidate than 5. Update successor = 4.
   • Move left to null.
4. Termination: Reached null. Loop ends.
   • Final Successor: 4.

6. Production-Ready Code Implementation

Because C++ and Java share identical object references and control-flow semantics for tree nodes, the implementation logic translates directly between both languages.

Java Implementation

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    
    TreeNode(int val) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}

public class BSTSuccessor {
    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        TreeNode successor = null;
        
        // Traverse down the tree using BST properties
        while (root != null) {
            if (root.val <= p.val) {
                // Current value is too small or equal; move right
                root = root.right;
            } else {
                // Current value is strictly greater; store candidate and search left for a tighter match
                successor = root;
                root = root.left;
            }
        }
        
        return successor;
    }
}

C++ Implementation

#include <iostream>

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {
        TreeNode* successor = nullptr;
        
        while (root != nullptr) {
            if (root->val <= p->val) {
                // Value is too small or equal, go right
                root = root->right;
            } else {
                // Potential successor found, record it and try to find a smaller valid value on the left
                successor = root;
                root = root->left;
            }
        }
        
        return successor;
    }
};

7. Real-World Practical Pitfalls & Debugging Mindset

When implementing or testing this algorithm in production environments or coding interviews, engineers often encounter a few recurring edge cases:

• Handling Skewed Trees: If a BST degenerates into a linear linked list (skewed tree), the height $H$ becomes equal to $N$. In this worst-case scenario, time complexity drops from $O(\log N)$ to $O(N)$.
• Passing Node vs. Node Value: Pay close attention to whether the function signature receives a full TreeNode object reference or just an integer value. Adjust comparisons accordingly (p.val vs. raw integer comparison).
• Missing Successor (Null Return): Failing to initialize successor to null will result in dangling pointer references or garbage values when no greater element exists in the tree.

8. Summary and Key Takeaways

• Inorder Successor Definition: The node that appears immediately after a given target node in an inorder (Left-Root-Right) traversal.
• BST Sorted Inorder Property: The inorder traversal of a Binary Search Tree always produces a strictly sorted ascending sequence.
• Optimal Traversal Efficiency: By leveraging BST ordering (left < root < right), we achieve an $O(H)$ time complexity where $H$ is the height of the tree.
• Constant Space Complexity: Iterative pointer manipulation requires $O(1)$ auxiliary space, avoiding recursion stack overflow risks.
• Decision Rule: When root.val <= target, discard the left subtree and move right. When root.val > target, record the node as a candidate and move left to find a tighter match.
• Homework Challenge (Inorder Predecessor): Finding the inorder predecessor follows the exact mirror logic: if root.val >= target, move left; if root.val < target, record the node as a candidate and move right.