Find LCA in a BST
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Technical Screen
Quick Answer: This interview question evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer for Find LCA in a BST states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.
Constraints
- 0 <= len(insert_order) <= 10^4
- 0 <= node values <= 10^9 (all non-negative so -1 is an unambiguous 'not found' sentinel)
- All values in insert_order are distinct (duplicates are ignored on insertion)
- p and q are integers; they may or may not be present in the BST
Examples
Input: ([6, 2, 8, 0, 4, 7, 9, 3, 5], 2, 8)
Expected Output: 6
Explanation: 2 lives in the left subtree and 8 in the right subtree of the root, so the root 6 is the split point and the LCA.
Input: ([6, 2, 8, 0, 4, 7, 9, 3, 5], 2, 4)
Expected Output: 2
Explanation: 4 is a descendant of 2, so the deeper ancestor common to both is 2 itself.
Input: ([6, 2, 8, 0, 4, 7, 9, 3, 5], 3, 5)
Expected Output: 4
Explanation: Both 3 and 5 are children of 4 (3 on the left, 5 on the right), so 4 is the LCA.
Input: ([6, 2, 8, 0, 4, 7, 9, 3, 5], 2, 2)
Expected Output: 2
Explanation: When both keys are the same existing node, that node is its own ancestor and the LCA.
Input: ([6, 2, 8, 0, 4, 7, 9, 3, 5], 0, 5)
Expected Output: 2
Explanation: 0 and 5 both sit under 2 (0 far left, 5 in the 4-subtree), and 2 is the deepest node between them.
Input: ([6, 2, 8, 0, 4, 7, 9, 3, 5], 7, 11)
Expected Output: -1
Explanation: 11 is not present in the BST, so the sentinel -1 is returned.
Input: ([], 1, 2)
Expected Output: -1
Explanation: Empty tree: neither key exists, so return the sentinel -1.
Input: ([5], 5, 5)
Expected Output: 5
Explanation: Single-node tree where both keys equal the root; the root is trivially the LCA.
Input: ([20, 10, 30, 5, 15, 25, 35], 5, 35)
Expected Output: 20
Explanation: 5 is in the far-left subtree and 35 in the far-right subtree, so the root 20 is the LCA.
Hints
- Reconstruct the BST first: walk down from the root for each value, going left when smaller and right when larger, attaching a new node where you fall off the tree.
- Use the BST property for the LCA: the lowest common ancestor is the first node (from the root) whose value lies between p and q inclusive. If the node is greater than both keys go left; if less than both go right; otherwise it is the answer.
- Before searching, verify both p and q actually exist in the tree with two ordinary BST lookups — return -1 if either lookup fails or the tree is empty.