#236 Lowest Common Ancestor of a Binary Tree
the problem
In plain words
Given two different nodes p and q that are both in the tree, return their lowest common ancestor: the deepest node that has both p and q as descendants (a node counts as a descendant of itself).
in root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
out 3
in root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
out 5
5 is an ancestor of 4, and a node is its own descendant.
in root = [1,2], p = 1, q = 2
out 1
- 2 ≤ number of nodes ≤ 10⁵
- -10⁹ ≤ Node.val ≤ 10⁹
- All values unique
- p ≠ q, both exist in the tree
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.
Solve it in the browser
LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
patternTree DFS (bottom-up)
where this runsgit merge-base answers the same question on a commit graph: the best common ancestor of two commits, used as the base of a three-way merge.
Let each call report what it found below it (p, q, or the answer). The first node to receive non-null reports from both sides is where p and q split — the LCA.
solutions
From brute force to optimal
Find the path from the root to p and to q; the last shared node is the LCA.
- DFS with backtracking to record root → p.
- Same for q.
- Walk both lists while they match.
Two DFS searches plus a linear compare — but three passes and extra lists.
The two path lists and the recursion stack.
class Solution { public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { List<TreeNode> toP = new ArrayList<>(), toQ = new ArrayList<>(); pathTo(root, p, toP); pathTo(root, q, toQ); TreeNode lca = null; for (int i = 0; i < Math.min(toP.size(), toQ.size()) && toP.get(i) == toQ.get(i); i++) { lca = toP.get(i); // last node both paths share } return lca; } /** Fills path with root → target; returns true if target is in this subtree. */ private boolean pathTo(TreeNode node, TreeNode target, List<TreeNode> path) { if (node == null) return false; path.add(node); if (node == target || pathTo(node.left, target, path) || pathTo(node.right, target, path)) return true; path.remove(path.size() - 1); // dead end: backtrack return false; }}Record every node's parent iteratively, collect p's ancestors, climb from q until you hit one.
- Iterative DFS filling
parentuntil both p and q are seen. - Put p and all its ancestors in a set.
- Climb from q until the set contains the node.
Each node is discovered once; the climbs are at most h steps.
The parent map — but no recursion, so deep trees are safe.
class Solution { public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { Map<TreeNode, TreeNode> parent = new HashMap<>(); parent.put(root, null); Deque<TreeNode> stack = new ArrayDeque<>(); stack.push(root); while (!parent.containsKey(p) || !parent.containsKey(q)) { // until both are discovered TreeNode node = stack.pop(); if (node.left != null) { parent.put(node.left, node); stack.push(node.left); } if (node.right != null) { parent.put(node.right, node); stack.push(node.right); } } Set<TreeNode> ancestors = new HashSet<>(); for (TreeNode a = p; a != null; a = parent.get(a)) ancestors.add(a); // p and everything above it TreeNode b = q; while (!ancestors.contains(b)) b = parent.get(b); // climb from q until we meet return b; }}Return root if it is null, p or q; otherwise combine the two children's reports.
- If root is null, p or q → return root.
- left = lca(left), right = lca(right).
- Both non-null → return root (split point).
- Else return whichever is non-null.
Each node visited at most once.
Recursion stack only.
class Solution { 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; // p and q split here return left != null ? left : right; // pass up whatever was found }}Dry run
in the room
How to say it in the interview
talk track
- Clarify: are both nodes guaranteed to be in the tree? (Here yes — that's why returning early at p is safe.)
- Explain the return value's meaning: "p, q, the LCA, or null".
- Mention the iterative parent-map version for very deep trees.
traps
- Comparing values instead of references when values could repeat.
- If p or q might be missing (LC 1644), the early return is wrong — you must search the whole tree and count how many you found.
what they ask next
Follow-ups
LCA in a BST (LC 235)?
Use the ordering: if both values are smaller go left, both larger go right, otherwise the current node is the LCA. O(h), O(1) iteratively.
Nodes have parent pointers (LC 1650)?
It's the linked-list intersection problem: walk up from both, switching to the other start when you hit null.
before you submit
Edge cases to test
- p is an ancestor of q → p (a node is its own descendant).
- p and q in different subtrees of the root → the root.
- A deep chain: recursion depth equals the depth of the deeper node.
practise next
Similar problems
- #235Lowest Common Ancestor of a Binary Search TreeMediumin BST
- #863All Nodes Distance K in Binary TreeMediumin Traversals
- #104Maximum Depth of Binary TreeEasyin Tree Recursion