Inorder Successor in BST

Inorder Successor in BST

1. What is this problem about?

The Inorder Successor in BST interview question asks you to find the node that comes immediately after a given node p in the in-order traversal of a Binary Search Tree (BST). If p is the last node in the traversal, you return null. This problem is a fundamental test of your ability to navigate tree structures using their inherent properties.

2. Why is this asked in interviews?

Companies like Microsoft, Google, and Amazon ask the Inorder Successor in BST coding problem to see if you understand the core properties of Binary Search Trees. It evaluates whether you can leverage the "left < root < right" property to avoid a full $O(N)$ traversal. It’s an essential part of the Binary Search Tree interview pattern, testing your efficiency in both recursive and iterative thinking.

3. Algorithmic pattern used

This problem relies on the Binary Search Tree Property.

• If the node p has a right child, the successor is the leftmost node in that right subtree.
• If p has no right child, you must look "up" the tree. The successor is the lowest ancestor of p such that p is in that ancestor's left subtree.
• An efficient iterative approach uses a successor variable that updates as you perform a standard BST search for p.

4. Example explanation

Suppose you have a BST: 5 is root, 3 is left, 7 is right. 3 has 2 (left) and 4 (right).

• Find successor of 3: 3 has no right child. We traverse from root 5. 3 is in 5's left subtree. So 5 is a potential successor. We move to the left. Since we reach 3, the last "left-turn" parent was 5. Successor is 5.
• Find successor of 4: 4 has no right child. From root 5, we go left to 3. From 3, we go right to 4. The last node where we went left was 5. Successor is 5.

5. Common mistakes candidates make

• Full Traversal: Doing a complete in-order traversal into a list and then finding p ($O(N)$ time and space). This misses the $O(H)$ optimization.
• Ignoring the Right Child: Forgetting that if p.right exists, the answer is always in that subtree.
• Handling Nulls: Not correctly returning null when p is the largest element in the tree.

6. Interview preparation tip

Always remember the "successor" logic: "If right exists, go right then all the way left. Otherwise, it's the first ancestor that contains the current node in its left branch." Practice this alongside "Inorder Predecessor" to solidify your Tree interview pattern knowledge.