Lowest Common Ancestor of a Binary Search Tree
Given a BST and two nodes p and q, return their lowest common ancestor (LCA): the lowest node that has both p and q as descendants (a node can be a descendant of itself).
Constraints:
- The number of nodes is in the range
[2, 10^5]. - All values are unique,
p != q, and both exist in the BST.
Intuition
1 82 / \3 4 124 / \ / \5 2 6 10 14For p = 2 and q = 6 the LCA is 4. For p = 2 and q = 14 it is 8. For p = 4 and q = 6 it is 4 (a node can be its own ancestor).
In a general binary tree we would have to search both sides. In a BST, comparing values is enough:
- If both p and q are smaller than the current node, they are both in the left subtree, so the LCA is on the left.
- If both are larger, the LCA is on the right.
- Otherwise they split here (one on each side, or one of them is this node), so this node is the LCA.
Approach: Walk Down Until the Paths Split
- Start at the root.
- While the node exists:
- If
p.val < node.valandq.val < node.val, go left. - Else if
p.val > node.valandq.val > node.val, go right. - Otherwise return this node.
- If
The first node where p and q go in different directions (or one equals the node) is the lowest one that still contains both.
Code
class Solution {public:TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {while (root != nullptr) {if (p->val < root->val && q->val < root->val) {root = root->left;} else if (p->val > root->val && q->val > root->val) {root = root->right;} else {return root;}}return nullptr;}};
Complexity
Time: O(h)
One root-to-leaf path is walked: O(log n) balanced, O(n) skewed.
Space: O(1)
The loop is iterative and uses no extra memory.
How to Explain It in an Interview
How to Explain it in an Interview
The 30-Second Spoken Pitch
"In a BST I can use the values to decide where the LCA is. I start at the root. If both p and q are smaller than the current node, they are both in the left subtree, so I go left. If both are larger, I go right. Otherwise they split at this node, either one on each side or one of them equal to the node, so this node is the lowest common ancestor and I return it. That follows a single path, so time is O of h and space is O of one. This is much simpler than the general binary tree version, which has to search both subtrees."
Next TopicConstruct Bst from Preorder Traversal