Lowest Common Ancestor
The Lowest Common Ancestor (LCA) of two nodes in a binary tree is the deepest node that is an ancestor of both. This is a classic problem with efficient recursive solution.
Algorithm:
1. If root is null or root equals p or q, return root.
2. Recursively search left and right subtrees.
3. If both left and right return non-null, then root is LCA.
4. If only one side returns non-null, return that.
Java implementation for Binary Tree (not necessarily BST):
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == null || root == p || root == q) return root;
TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right = lowestCommonAncestor(root.right, p, q);
if (left != null && right != null) return root;
return left != null ? left : right;
}
For BST, we can leverage the BST property to avoid full recursion:
public TreeNode lowestCommonAncestorBST(TreeNode root, TreeNode p, TreeNode q) {
if (p.val < root.val && q.val < root.val)
return lowestCommonAncestorBST(root.left, p, q);
if (p.val > root.val && q.val > root.val)
return lowestCommonAncestorBST(root.right, p, q);
return root;
}
Two Minute Drill
- LCA finds deepest common ancestor of two nodes.
- Recursive solution for binary tree: O(n).
- For BST, use values to decide path.
- Common interview question.
Need more clarification?
Drop us an email at career@quipoinfotech.com