Lowest Common Ancestor of a Binary Tree
1Try it yourself first
Think for 20-30 minutes before you open any hint. Being stuck is where the learning happens.
Only for you, saved in this browser. After you see the approach you will compare it with your idea.2What is being asked
Given two nodes p and q in a binary tree, find their lowest common ancestor: the deepest node that has both of them below it (a node counts as below itself).
3Hint ladder
Take one rung at a time. Stop as soon as the idea clicks.
- Hint 1What should a subtree report when it contains neither p nor q? One of them? Both?
- Hint 2If the left side reports a find and the right side reports a find, where do the paths to p and q split?
4The approach
Have you tried the hints? The approach is built as a path from the obvious way to the clever one.
Two employees p and q are somewhere in a big company. Their lowest common manager is the first boss under whom both of them work. Start at the CEO and ask each department head: "is p or q in your department?". The first boss who gets a "yes" from BOTH his departments (or who is himself one of the two and gets a yes from below) is the lowest common manager.
- The obvious way
Find the path from the root to p and to q, then compare the two paths: O(n) but needs two paths stored.
- The key insight
A recursive function returns the node it found: nothing if the subtree contains neither target; the node itself if this node is p or q; otherwise whatever the children found. If both children return something, the current node is where the two targets split: it is the answer and is passed upward. If only one child returns something, pass that up.
- The algorithm
- Empty spot, or this node is p or q? Return it.
- Ask the left subtree and the right subtree what they found.
- Both found something? This node is the lowest common ancestor: return it.
- Only one side found something? Return that.
Watch it run
Exampletree = [3, 5, 1, 6, 2, 0, 8, null, null, 7, 4], p = 5, q = 1
Root 3 asks its left side. The left child is 5, which is p itself: it reports "found 5" straight away.
left reports: 5
Where people slip
- If p is an ancestor of q, the answer is p itself: the function returns p as soon as it meets it, which is correct.
- Compare nodes by identity, not by value.
How close was your idea?
You did not write an idea, and that is fine.
Be honest with yourself. This sets your revision list.
5Code
Try writing it yourself from the steps first. Then compare.
def lowest_common_ancestor(root, p, q):
if root is None or root is p or root is q:
return root # a target, or nothing here
left = lowest_common_ancestor(root.left, p, q)
right = lowest_common_ancestor(root.right, p, q)
if left and right:
return root # the paths split here
return left or right # pass up whichever side found somethingNow close this and write it again from memory, in the language you will use in the interview. Reattempt after 1 day, 7 days and about 30 days.
6Still stuck? Watch a video
Seeing someone explain it out loud can make it click. Try the video after you have read the approach above.