Inorder Successor in BST II

Inorder Successor in BST II

1. What is this problem about?

The Inorder Successor in BST II interview question is a variation where nodes have a parent pointer. You are given a specific node p, and you must find its in-order successor. Unlike the first version, you may not be given the root of the tree, so you must use the parent pointers to navigate upwards when necessary.

2. Why is this asked in interviews?

Companies like Meta and Microsoft use the Inorder Successor in BST II coding problem to test a candidate's comfort with non-traditional tree navigation. Having parent pointers changes the strategy and simplifies some parts while complicating others. It’s a great test of Tree interview pattern flexibility and attention to structural details.

3. Algorithmic pattern used

This problem uses Parent-Pointer Traversal.

• If p has a right child: The successor is the leftmost node of the right subtree (same as version I).
• If p has no right child: Move up using parent pointers until you find a node x that is the left child of its parent. That parent is the successor.
• If you reach the root and haven't found a "left-child" relationship, the successor is null.

4. Example explanation

Consider a path: Parent(10) -> Child(15) -> LeftChild(12).

• If you are at 12, the successor is 15 because 12 is the left child of 15.
• If you are at 15, and it has no right child, move up to 10. If 15 was the right child of 10, keep moving up. If 10 has a parent where 10 is the left child, that's the one.

5. Common mistakes candidates make

• Ignoring the parent pointer: Trying to find the root first and then using the version I algorithm. While it works, it’s not utilizing the provided data structure effectively.
• Infinite Upward Loop: Forgetting to stop at the root when moving up.
• Successor vs Predecessor: Swapping the logic for moving up (finding a left-child relation vs a right-child relation).

6. Interview preparation tip

When nodes have parent pointers, the tree is essentially a doubly-linked structure. Practice "going up" and "going down" logic. This is a common requirement in advanced Binary Tree interview patterns like AVL tree rotations or Red-Black tree rebalancing.