236. Lowest Common Ancestor of a Binary Tree
Medium · solved 2026-10-06 · Open on LeetCode
treebinary-treedfs
Time O(n) · Space O(h)
How to get there
The lowest node whose subtree holds both
1. Restate the LCA. The ancestors of a node are the nodes on its path up to the root, the node itself included. The lowest common ancestor of p and q is the deepest node that is an ancestor of both: the point where their two paths up first meet.
2. Find it by hand and see where that gets stuck. In LeetCode’s first tree, with p = 5 and q = 1, the paths up are 5 → 3 and 1 → 3, so they meet at 3. With p = 5 and q = 4, the path up from 4 is 4 → 2 → 5 → 3, which passes through 5 itself, so the answer is 5. Tracing paths upward needs to know each node’s parent, but a tree node knows only its children.
3. Look from above instead. A node is a common ancestor of p and q exactly when its subtree contains both of them. So the LCA is the lowest node whose subtree holds both: walking back up from the bottom, the first node where both have been found.
4. Find what each call must report. How many of p and q its subtree holds: 0, 1 or 2. A node’s count is its children’s counts plus 1 if it is p or q itself, so the children must finish first. It is a postorder walk, like 104’s depth.
5. Stop growing the answer once it is found. The first node whose count reaches 2 is the LCA. Every node above it also holds both, but none is lower, so they pass the answer up unchanged. solution-1-original.py also skips the right subtree when the node and its left subtree already hold both.
6. Check the cost. Each node is visited at most once: O(n) time, and O(h) for the recursion.
The reusable recipe: when the answer is the lowest node whose subtree has some property, have each call report that property upward, and fix the answer at the first node where it holds.
Let the count's meaning write the five exits
| Value | Always means |
|---|---|
walk(found, node) returns (count, answer) |
count is how many of p and q are in node’s subtree; when count is 2, answer is their LCA |
found_self |
1 when node is p or q, otherwise 0 |
Each exit keeps that meaning true:
| Code | What it means | Returns |
|---|---|---|
if not node: return (0, None) |
an empty subtree holds neither | count 0 |
if found_left == 2 |
both are in the left subtree, and its LCA is already known | the left answer, unchanged |
if found_self == 1 and found_left == 1 |
this node is one of them, and the other is in its left subtree | this node; the right subtree is never walked |
if found_right == 2 |
both are in the right subtree | the right answer, unchanged |
if found_self + found_left + found_right == 2 |
the two are split across this node: one in each subtree, or this node and one in the right | this node |
return (found_left+found_right+found_self, node) |
fewer than two so far | the count; node is a placeholder, read only when the count is 2 |
found is passed down but never read. node.val == p.val relies on LeetCode’s guarantee that values are unique; node is p compares the nodes themselves.
solution-2-short.py packs the same meaning into one returned node: None for “neither”, p or q for “one of them”, the LCA for “both”. It stops at p or q without searching below, which is safe: if the other node is below, this node is the LCA anyway, and if not, the split higher up finds it.
The method carries over: give each call’s return value one meaning, then every exit is a way that meaning can come true.
Alternatives compared
| Approach | Time | Space | How it works |
|---|---|---|---|
| Parent pointers and an ancestor set | O(n) | O(n) | Walk the tree once to record each node’s parent, collect p’s ancestors in a set, then climb from q until reaching one of them. |
| Compare root-to-node paths | O(n) | O(n) | Find the path from the root to p and to q; the LCA is the last node the two paths share. |
Count found in each subtree (chosen, solution-1-original.py) |
O(n) | O(h) | Each call returns how many of p and q its subtree holds; the first count of 2 marks the LCA. |
Return the node itself (solution-2-short.py) |
O(n) | O(h) | Each call returns None, p or q, or the LCA; a node whose two subtrees both return something is the LCA. |
The first two follow the definition directly, tracing paths, but need memory for the whole tree or path. The recursive two find the meeting point from above with only the recursion stack. A tree can have 100,000 nodes, and on a chain that long solution-1-original.py raised RecursionError under Python’s default limit of 1,000 calls when run locally.
solution-1-original.py
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
def walk(found: int, node: 'TreeNode') -> tuple[int, 'TreeNode']:
if not node:
return (0, None)
found_self = 1 if node.val == p.val or node.val == q.val else 0
found_left, left_node = walk(found, node.left)
if found_left == 2:
return (2, left_node)
if found_self == 1 and found_left == 1:
return (2, node)
found_right, right_node = walk(found, node.right)
if found_right == 2:
return (2, right_node)
if found_self + found_left + found_right == 2:
return (2, node)
return (found_left+found_right+found_self, node)
_, lca = walk(0, root)
return lcasolution-2-short.py
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
if not root or root is p or root is q:
return root
left = self.lowestCommonAncestor(root.left, p, q)
right = self.lowestCommonAncestor(root.right, p, q)
if left and right:
return root
return left or rightNotes
Write your approach, insights, and mistakes here. Any other file in this folder (e.g. solution.py, attempt-1.py) is rendered below as code.