Inorder Successor in BST
Given a node in a Binary Search Tree, find the in-order successor of that node. The successor is the node with the smallest key greater than the key of the given node.
Why Interviewers Ask This
Netflix values engineers who write efficient, self-contained code without relying on external libraries. This question tests your ability to leverage BST properties rather than performing a full traversal. It evaluates logical deduction, edge case handling for nodes with or without right subtrees, and your capacity to optimize space complexity from O(N) to O(1).
How to Answer This Question
1. Clarify the input: Confirm if you have access to parent pointers or only child references, as this dictates your strategy. Netflix interviews often test assumptions.
2. Analyze the two distinct cases: If the node has a right child, the successor is the leftmost node in that subtree. If it lacks a right child, the successor is the lowest ancestor for which the given node is in the left subtree.
3. Draft the algorithm: For the first case, traverse left until null. For the second, move up using parent pointers (or simulate this via a stack if parents are missing).
4. Implement cleanly: Write pseudocode first, then translate to actual code, ensuring variable names are descriptive.
5. Validate with examples: Walk through a specific tree where the target is a leaf with no right child and another where it has a right subtree to prove correctness.
Key Points to Cover
- Distinguishing between nodes with and without a right child immediately
- Achieving O(h) time complexity instead of O(n)
- Handling the O(1) space constraint when parent pointers are present
- Correctly identifying the 'lowest ancestor' logic for nodes without right subtrees
- Clarifying input constraints like the existence of parent pointers before coding
Sample Answer
To solve this efficiently, I would first check if the node has a right subtree. If it does, the in-order successor is simply the node with the minimum value in that right subtree. I can find this by moving to the right child and then repeatedly traversing left until there are no more left children. This handles the case where the successor is a descendant.
However, if the node does not have a right child, the successor must be an ancestor. Specifically, it is the lowest ancestor for whom the current node lies in its left subtree. Since we might not always have direct parent pointers, I would need to clarify the input structure. If parent pointers exist, I traverse upward until I find a node where my current path came from its left side. If I am at the root or the path never came from a left child, then no successor exists.
In terms of complexity, this approach runs in O(h) time, where h is the height of the tree, because we only traverse down one branch or up to the root. The space complexity is O(1) if parent pointers are available, or O(h) if we use a stack to simulate the traversal. At Netflix, where performance is critical, avoiding a full tree traversal to collect all nodes is essential, making this targeted approach the preferred solution.
Common Mistakes to Avoid
- Performing a full in-order traversal to collect all nodes, resulting in unnecessary O(n) time complexity
- Failing to handle the edge case where the given node is the maximum element in the tree
- Ignoring whether parent pointers are available, leading to incorrect assumptions about traversal direction
- Incorrectly returning the immediate right child even when that child has a left subtree
Practice This Question with AI
Answer this question orally or via text and get instant AI-powered feedback on your response quality, structure, and delivery.