Lowest Common Ancestor Patterns
Five harder prompts on LCA in BSTs and general binary trees, with the parent-pointer variant. Code-anchored interview prep.
Question Bank
Hard
JavaScript
lowest-common-ancestor
trees
interview-prep
algorithms
832 views
5
Implement lcaBST(root, p, q) for a BST where every value is unique. Aim for O(h) time and O(1) extra space.
Examples
Example 1:
Input: BST 6 -> (2 -> (0, 4), 8 -> (7, 9)); p = node(2), q = node(4)
Output: the node holding 2
Explanation: Both target values are <= 2 in the left subtree's range, but 4 sits in the right side of node 2, so node 2 splits them and is the LCA. O(h) time, O(1) space.Example 2:
Input: same BST; p = node(2), q = node(8)
Output: the root, node(6)
Explanation: 2 < 6 and 8 > 6, so node 6 splits the pair and is the LCA.4 more questions, with full solutions and explanations, are available for premium members.
Upgrade to Premium