Lowest Common Ancestor of a Binary Tree
On this page
Problem statement
Given a binary tree and two of its nodes p and q, return their lowest common ancestor: the deepest node that has both p and q as descendants. A node counts as a descendant of itself. Both nodes are guaranteed to be in the tree, and values are unique.
The tree here is a plain binary tree, not a BST, so you can't steer by comparing values. The elegant answer lets each subtree report what it found and lets the first node that hears from both sides declare itself the answer. Original problem: LeetCode 236.
Example

Tree: [3, 5, 1, 6, 2, 0, 8, null, null, 7, 4]
p = 6, q = 4 -> 5
p = 5, q = 4 -> 5 # a node is its own ancestor
p = 6, q = 8 -> 3
Constraints (assumed)
- 2 ≤ nodes ≤ 100,000; values unique.
- p ≠ q, and both exist in the tree.
What this question tests
- Postorder recursion that combines results from both children.
- Defining exactly what a recursive call returns.
- Knowing when the BST shortcut applies and when it doesn't.
Questions to ask first
- Is it a BST? (Here: no. In a BST you can walk down by comparing values in O(h).)
- Are p and q guaranteed to exist? (Here: yes. If not, you must confirm both were found.)
- Do nodes have parent pointers? If yes, it becomes "intersection of two linked lists".
- Can p be an ancestor of q? (Yes; then p is the answer.)
Try it yourself first
You have the full problem. Sketch your answer, then sign up free to read the complete walkthrough.
- The complete design, flow by flow, with pictures
- Deep dives into the hard parts
- What mid, senior and staff candidates are expected to say
- Full company question lists
Free forever. No card needed.