Given a binary tree and two nodes p and q, explain how you would find their lowest common ancestor (LCA). The LCA is the deepest node that is an ancestor of both p and q. A node can be its own ancestor.
For example:
3
/ \
5 1
/ \ / \
6 2 0 8
/ \
7 4LCA of 5 and 1 is 3. LCA of 5 and 4 is 5 (since 5 is an ancestor of 4 and itself).
How does your approach handle the case where one node is an ancestor of the other?
Explain your approach and analyze the time and space complexity.
How to approach it
- Hint 1
Use a recursive post-order traversal. Search for p and q in the left and right subtrees.
- Hint 2
If the left subtree returns a non-null result and the right subtree also returns non-null, the current node is the LCA.
- Hint 3
If only one side returns non-null, propagate that result upward. If the current node itself is p or q, return it immediately.
Ready to answer it out loud?
Record your answer in 1:30 and Preptile scores it 1–10 with specifics — what landed, what you skipped, and what to say next time.
Practising needs an invite code. Join the waitlist and we’ll send you one.