Q16: How do you find the Lowest Common Ancestor (LCA) of two nodes in a Binary Tree?
Use a recursive post-order traversal. If root == null, root == p, or root == q, return root. Recursively search left and right subtrees. If both left and right recursive calls return non-null nodes, root is the LCA. If only one returns non-null, pass that node upward.
Lowest Common Ancestor Solution
class TreeNode {
int val;
TreeNode left, right;
TreeNode(int val) { this.val = val; }
}
public class LCA {
public static 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;
}
}💡 Bubbles up matches from left and right subtrees to identify the common ancestor node.
Key Takeaways
- Recursive post-order traversal checks left and right subtrees.
- If both branches return target nodes, current root is the LCA.
Knowledge Check
What is the time complexity of finding the LCA in an unbalanced Binary Tree with N nodes?