24 May 2026 11 min read cracking the coding interview series

Cracking The Coding Interview Together – Problem 4.6: In-Order Successor in a BST

Let's face it, navigating tree structures is a cornerstone of computer science, and Binary Search Trees (BSTs) are particularly fascinating due to their ordered nature. When we talk about "in-order traversal," we're referring to visiting nodes in a specific sequence: left child, current node, right child. This sequence naturally yields elements in sorted order. But what if you're at a specific node and need to find the very next element in that sorted sequence, without performing a full traversal? This isn't just an academic exercise; it's a common requirement in scenarios like database indexing, efficient range queries, or implementing iterators for tree-based collections.

The core conflict here lies in efficiently determining that "next" node. If a node has a right child, the successor is often straightforward to find within that right subtree. But what happens when there's no right child? How do we "go up" the tree to find our way? This is where the seemingly simple addition of a parent link to each node becomes a game-changer, transforming a potentially complex search into an elegant, efficient operation. Our shared goal today is to demystify this process, building a robust algorithm that leverages these parent pointers to find the in-order successor with optimal performance.

Problem Statement

We are tasked with writing an algorithm to find the "next" node (specifically, the in-order successor) of a given node in a Binary Search Tree (BST). A crucial assumption for this problem is that each node in the tree has a link to its parent.

Given:

A root node of a Binary Search Tree.
A Node p for which we need to find its in-order successor.

Return:

The in-order successor of p, or null if p is the largest element in the BST.

Analyze the Problem Together

Before we jump into coding, let's break down the problem's core components and constraints.

Constraints & Key Properties:

Binary Search Tree (BST): This is paramount. For any given node, all values in its left subtree are smaller, and all values in its right subtree are larger. This property is what allows for efficient searching and ordering.
Parent Link: Each node has a parent pointer. This is the "Aha!" moment for this problem. Without it, finding a successor when a node has no right child would require either a full tree traversal or storing the path from the root, both of which are less efficient.
In-Order Successor: This means the node that would come immediately after p if we were to list all elements of the BST in ascending order.

The "Aha!" Conflict and Core Cases:

The challenge isn't just finding any larger node, but the immediately next one in sorted order. This naturally splits into two primary scenarios:

p has a right subtree: If p has a right child, then its in-order successor must be the smallest node in p's right subtree. Think about it: after visiting p, the in-order traversal moves to p's right child, and then recursively to its leftmost descendant. This is a direct consequence of the BST property.
p does not have a right subtree: This is where the parent link becomes invaluable. If p has no right child, we need to go "up" the tree. We are looking for the first ancestor of p that p is in the left subtree of. Why? Because if p is a left child of its parent, then the parent itself is the next node in in-order sequence. If p is a right child of its parent, then its parent (and all ancestors until we find one where p is in its left subtree) would have already been visited in an in-order traversal. We keep moving up until we find an ancestor q such that p is in q's left subtree. If we reach the root and p is still a right child (or p is the root itself and has no right child), then p is the largest element in the tree, and thus has no successor.

Naive Approaches (and why we avoid them):

Full In-Order Traversal: We could perform a complete in-order traversal of the BST, store all elements in a list, find p in the list, and then return the next element. This works, but it's O(N) time complexity and O(N) space complexity, which is highly inefficient if we only need one successor.
Searching from Root without Parent Pointers: Without parent pointers, if p has no right child, we'd have to restart a search from the root, keeping track of the path taken to p to identify potential ancestors. This would still be O(h) but more complex to implement and potentially less intuitive.

Justifying Our Architectural Choice:

Our approach will directly leverage the BST properties and the parent links. This allows us to find the successor in O(h) time complexity, where h is the height of the tree (which is log N for a balanced BST, and N in the worst case for a skewed tree). This is optimal because, in the worst case, we might have to traverse from p all the way up to the root or down to a leaf.

Questions for the Interviewer

As a senior engineer, you'd want to clarify a few points to ensure your solution is robust and handles all expected scenarios.

What if the given node p is null or not present in the tree? Should we throw an exception, return null, or handle it gracefully? (Assuming p is always a valid node in the tree for this problem, but good to ask).
Are there duplicate values in the BST? While BSTs typically assume unique values, some implementations allow duplicates. If duplicates are allowed, how should the in-order successor be defined for them? (For this problem, we'll assume unique values, which is standard).
What is the expected behavior if p is the largest element in the tree? Should the function return null or throw an error? (We'll return null as per standard practice).
What is the maximum height of the tree? This helps understand potential stack overflow risks if recursion were used extensively (though our iterative solution avoids this) and gives context for performance expectations.

Think About the Solution

Let's outline the high-level architecture of our inorderSuccessor function. We've identified two main cases, and our solution will be a direct implementation of these.

High-Level Architecture:

The inorderSuccessor(Node p) function will primarily check two conditions:

Does p have a right child?
- If yes, the successor is the leftmost node in p's right subtree. We'll need a helper function, say findMin(Node node), to achieve this.
Does p not have a right child?
- If no, we need to traverse up the tree using p.parent. We'll look for the first ancestor q such that p is in q's left subtree.

Components:

Node Class: A simple class to represent a BST node, containing data, left, right, and crucially, parent pointers.
inorderSuccessor(Node p): The main function implementing the logic.
findMin(Node node) (Helper): A utility function to find the minimum value node in a given subtree. This is simply traversing left until left is null.

Edge Cases to Consider:

p is null: The problem statement implies p is a valid node, but defensively, we might check for this.
p is the largest element: This means p has no right child, and when traversing up, p is always a right child of its parent (or p is the root). In this case, the successor is null. Our algorithm should naturally handle this by returning null when the while loop for traversing up finishes and q is null.
p is a leaf node: This is covered by the two main cases. If it's a leaf and has a right child (impossible), or if it's a leaf and has no right child (most common leaf scenario).

Write Code and Explain

Let's translate our thought process into production-ready Java code. We'll define a TreeNode class and then implement the inorderSuccessor method.

class TreeNode {
    int data;
    TreeNode left;
    TreeNode right;
    TreeNode parent; // Crucial for this problem

    public TreeNode(int data) {
        this.data = data;
        this.left = null;
        this.right = null;
        this.parent = null;
    }
}

public class BSTSuccessor {

    /**
     * Finds the in-order successor of a given node 'p' in a Binary Search Tree.
     * Assumes each node has a link to its parent.
     *
     * @param p The node for which to find the successor.
     * @return The in-order successor of 'p', or null if 'p' is the largest element.
     */
    public TreeNode inorderSuccessor(TreeNode p) {
        // Edge case: If the input node is null, there's no successor.
        if (p == null) {
            return null;
        }

        // Case 1: If 'p' has a right subtree, the successor is the leftmost node in that subtree.
        if (p.right != null) {
            return findMin(p.right);
        }

        // Case 2: 'p' does not have a right subtree.
        // We need to go up using parent pointers.
        // The successor is the first ancestor 'q' for which 'p' is in 'q's left subtree.
        TreeNode current = p;
        TreeNode parent = p.parent;

        // Traverse up the tree until we find a parent 'parent' such that 'current' is its left child.
        // Or until 'parent' becomes null (meaning 'p' was the largest element).
        while (parent != null && parent.right == current) {
            current = parent;
            parent = parent.parent;
        }

        // At this point, 'parent' is either the successor (if 'current' was its left child)
        // or 'null' (if 'p' was the largest element in the tree).
        return parent;
    }

    /**
     * Helper function to find the node with the minimum value in a given subtree.
     * This is done by repeatedly traversing to the left child until no more left children exist.
     *
     * @param node The root of the subtree to search.
     * @return The node with the minimum value in the subtree.
     */
    private TreeNode findMin(TreeNode node) {
        // If the node itself is null, there's no minimum.
        if (node == null) {
            return null; // Or throw IllegalArgumentException, depending on requirements.
        }
        // Keep going left until we hit a null left child.
        while (node.left != null) {
            node = node.left;
        }
        return node;
    }

    // --- Example Usage (for testing purposes) ---
    public static void main(String[] args) {
        BSTSuccessor solver = new BSTSuccessor();

        // Construct a sample BST
        //       20
        //      /  \
        //     10   30
        //    / \   / \
        //   5  15 25  35
        //  / \    /
        // 3   7  22

        TreeNode root = new TreeNode(20);
        TreeNode node10 = new TreeNode(10);
        TreeNode node30 = new TreeNode(30);
        TreeNode node5 = new TreeNode(5);
        TreeNode node15 = new TreeNode(15);
        TreeNode node25 = new TreeNode(25);
        TreeNode node35 = new TreeNode(35);
        TreeNode node3 = new TreeNode(3);
        TreeNode node7 = new TreeNode(7);
        TreeNode node22 = new TreeNode(22);

        root.left = node10; node10.parent = root;
        root.right = node30; node30.parent = root;

        node10.left = node5; node5.parent = node10;
        node10.right = node15; node15.parent = node10;

        node30.left = node25; node25.parent = node30;
        node30.right = node35; node35.parent = node30;

        node5.left = node3; node3.parent = node5;
        node5.right = node7; node7.parent = node5;

        node25.left = node22; node22.parent = node25;

        // Test cases
        System.out.println("Successor of 15: " + (solver.inorderSuccessor(node15) != null ? solver.inorderSuccessor(node15).data : "null")); // Expected: 20
        System.out.println("Successor of 7: " + (solver.inorderSuccessor(node7) != null ? solver.inorderSuccessor(node7).data : "null"));   // Expected: 10
        System.out.println("Successor of 22: " + (solver.inorderSuccessor(node22) != null ? solver.inorderSuccessor(node22).data : "null")); // Expected: 25
        System.out.println("Successor of 35 (largest): " + (solver.inorderSuccessor(node35) != null ? solver.inorderSuccessor(node35).data : "null")); // Expected: null
        System.out.println("Successor of 20: " + (solver.inorderSuccessor(root) != null ? solver.inorderSuccessor(root).data : "null")); // Expected: 22
        System.out.println("Successor of 3: " + (solver.inorderSuccessor(node3) != null ? solver.inorderSuccessor(node3).data : "null")); // Expected: 5
    }
}

Step-by-Step Walkthrough:

inorderSuccessor(TreeNode p) Function:
- Null Check: We first handle the trivial case where p itself is null. If so, there's no successor, and we return null.
- Case 1: p has a right child (p.right != null):
  - If p has a right subtree, its in-order successor is the smallest node in that right subtree.
  - We delegate this task to our findMin helper function, passing p.right as the starting point.
  - The result from findMin is immediately returned.
- Case 2: p does not have a right child (p.right == null):
  - This is the more intricate part. We need to move up the tree using parent pointers.
  - We initialize current to p and parent to p.parent.
  - We enter a while loop:
    - The loop continues as long as parent is not null (meaning we haven't reached the root's parent) AND current is the right child of its parent.
    - Why parent.right == current? If current is the right child of parent, it means parent would have been visited before current in an in-order traversal. So, parent cannot be current's successor. We need to keep moving up.
    - Inside the loop, we update current to parent and parent to parent.parent, effectively moving one level up.
  - Once the loop terminates, parent will hold one of two values:
    - The in-order successor: This happens if current was the left child of parent when the loop condition parent.right == current became false. In this scenario, parent is indeed the next node in the in-order sequence.
    - null: This happens if we traversed all the way up to the root, and p (or its ancestors) was always a right child. This indicates that p is the largest element in the BST, and thus has no successor.
  - We return the final parent value.
findMin(TreeNode node) Helper Function:
- This function takes a node (which will be the root of a subtree) and finds the smallest element within it.
- It handles a null input defensively.
- It iteratively moves node to its left child (node = node.left) as long as node.left is not null.
- When the loop finishes, node will be the leftmost node in the subtree, which by BST definition, is the smallest.
- This node is then returned.

This structured approach ensures we cover all scenarios efficiently and correctly.

Time & Space Complexity

Let's analyze the efficiency of our solution.

findMin function: In the worst case, this function traverses from the given node all the way down to the leftmost leaf. This takes O(h) time, where h is the height of the subtree.
inorderSuccessor function:
- Case 1 (has right child): We call findMin on p.right. This takes O(h_right) time, where h_right is the height of the right subtree.
- Case 2 (no right child): We traverse up the tree using parent pointers. In the worst case, p could be a leaf, and we might have to go all the way up to the root. This takes O(h) time, where h is the height of the entire tree.
Combining both cases, the overall time complexity is O(h), where h is the height of the BST. For a balanced BST, h = log N, making it O(log N). For a skewed BST (worst case), h = N, making it O(N).
Our solution uses a constant number of variables (current, parent). We are not using any auxiliary data structures that grow with the input size (like a stack for recursion or a list for storing elements).
Therefore, the space complexity is O(1).

Space Complexity:

Time Complexity:

This O(h) time and O(1) space complexity is optimal for this problem, given the constraints.

Why This Problem Matters (The Senior Perspective)

Understanding how to find an in-order successor isn't just about passing an interview; it's about grasping fundamental tree traversal mechanics and appreciating the power of well-designed data structures. From a senior engineering perspective, here's why this problem resonates:

Database Indexing and B-Trees: Many database systems use tree-like structures (like B-trees or B+ trees) for indexing. Efficiently finding the "next" record in a sorted sequence is crucial for range queries (WHERE value BETWEEN X AND Y) and cursor operations. The logic for navigating these structures shares conceptual similarities with finding successors in a BST.
Iterators for Tree-Based Collections: If you were implementing your own TreeSet or TreeMap in Java, or similar ordered collections in other languages, you'd need an efficient way to provide an Iterator. This iterator would rely on finding the next (or previous) element in sorted order, which is precisely what our successor algorithm does. Parent pointers simplify this significantly.
Understanding Tree Properties: This problem reinforces the core properties of BSTs and how they enable efficient operations beyond simple search. It highlights that parent pointers, while adding a small overhead to node creation and tree modifications, can dramatically simplify and optimize certain traversal patterns.
Architectural Decisions: When designing data structures, the decision to include (or omit) parent pointers is a trade-off. Including them simplifies upward traversal and successor/predecessor finding, but adds complexity to insertion/deletion operations (as parent pointers also need updating). This problem helps you weigh those design choices.
Scalability and Performance: In large-scale systems, even small O(N) operations can become bottlenecks. An O(log N) or O(h) solution, especially with O(1) space, is critical for maintaining performance as data volumes grow. This problem teaches us to seek out these optimal solutions.
Robustness and Edge Cases: The careful handling of null nodes, the largest element, and the two distinct successor cases demonstrates a thorough approach to problem-solving – a hallmark of senior engineering.

This problem, therefore, is a microcosm of larger architectural and performance considerations you'll face in real-world software development.

Final Thoughts

We've successfully navigated the intricacies of finding an in-order successor in a Binary Search Tree, leveraging the power of parent pointers. We've seen how breaking the problem into distinct cases and utilizing helper functions leads to a clean, efficient, and robust solution.

This exercise is a fantastic way to solidify your understanding of BSTs and their practical applications. As a next step, I encourage you to consider how you would find the in-order predecessor (the element immediately before p in sorted order). The logic will be strikingly similar, just mirrored! Also, ponder how this problem would change if nodes did not have parent links – that's a significantly harder challenge that often requires a different approach, perhaps involving iterative in-order traversal with a stack.

Keep exploring, keep building, and remember that every problem solved deepens your understanding of the underlying principles that power our digital world. Happy coding!