Inorder Successor in BST

Link: GeeksforGeeks – Inorder Successor in BST

Problem Statement

Given a Binary Search Tree (BST) and a node x in it, find the inorder successor of that node.
The inorder successor of a node is the node with the smallest key greater than x.data.
Return null if the successor does not exist.

Intuition

In a BST, the inorder traversal visits nodes in sorted order.
The successor of node x is therefore:

1. If x has a right subtree
   – The left‑most (minimum) node in that right subtree.

2. If x lacks a right subtree
   – Climb up using parent pointers (or simulate with traversal) and find the nearest ancestor for which x lies in its left subtree.

Approach (without explicit parent pointers)

1. Perform a standard BST search for x, keeping track of a potential successor:

   • When moving left (because x is smaller), the current node is a candidate successor (it is larger than x).

   • When moving right (because x is larger), successor stays unchanged.

2. Once x is found:

   • If it has a right child, return minNode(x.right).

   • Otherwise, return the stored candidate successor.

Java Code

class Solution {
    // Helper: minimum node in a subtree
    private Node minNode(Node node) {
        while (node != null && node.left != null) {
            node = node.left;
        }
        return node;
    }

    // Main function
    public Node inOrderSuccessor(Node root, Node x) {
        Node successor = null;
        Node curr = root;

        // Search for x while tracking potential successor
        while (curr != null) {
            if (x.data < curr.data) {
                successor = curr;      // current node could be next larger
                curr = curr.left;
            } else if (x.data > curr.data) {
                curr = curr.right;
            } else {
                break;                 // found node x
            }
        }

        if (curr == null) return null; // x not present

        // Case 1: right subtree exists
        if (curr.right != null) {
            return minNode(curr.right);
        }

        // Case 2: no right subtree – successor is ancestor stored earlier
        return successor;
    }
}

Time & Space Complexity

• Time Complexity: O(H)
H is the height of the tree (O(log N) for balanced, O(N) for skewed).

• Space Complexity: O(1)
  Only a few pointers are used; recursion is avoided.

Dry Run

Consider the BST

        20
       /  \
     10    30
      \
      15

For x = 15:

1. Traverse: 20 (succ=20) ➜ left to 10 (succ=20) ➜ right to 15 (found).

2. 15 has no right child. Stored succ = 20.
   Result → 20.

For x = 10:

1. Traverse: 20 (succ=20) ➜ left to 10 (found).

2. 10 has right child 15. Return min of that subtree ⇒ 15.

Conclusion

The algorithm leverages BST order properties to find the next‑greater node in O(H) time and O(1) space, efficiently handling both cases (with or without a right subtree).