These are the notes for DSA episode 38. Two nodes in a tree, like two cousins in a family tree, always have shared "elders" above them; the lowest common ancestor (LCA) is the closest one. We define every word from zero (ancestor, descendant, why a node is its own ancestor), then solve Lowest Common Ancestor of a Binary Tree (LeetCode 236). The obvious way walks down from the root and, at every step, searches the left subtree for both nodes: correct, but O(n · h), and it times out on a tall tree with 21 lakh nodes. The fix is one postorder pass (the same "ask your children first" idea as episode 37): every node returns p, q, the answer, or null, and the node where both sides come back non-null is the LCA, in O(n). As a bonus, LCA in a binary search tree (LeetCode 235) just walks down by value. Every program below was run with javac/java 21 (the SyntaxPilot compiler kills a run at 8 seconds), and the outputs shown are real.
The problem, in real life
At a family wedding, two cousins, Riya and Kabir, want to know their closest shared elder. Riya walks up her line: her mum, then her mum's father, Dadaji, then his father. Kabir walks up his: his dad, then his dad's father, also Dadaji. Great-grandpa is on both lines too, but Dadaji is the first person on both lines: the closest shared elder.
| At the wedding | In a tree |
|---|---|
| A person | a node |
| Your elders (parent, grandparent, ...) | your ancestors |
| Everyone born into your branch | your descendants |
| An elder of both cousins | a common ancestor |
| The closest shared elder (Dadaji) | the lowest common ancestor |
| A parent and their own child: the parent is the answer | a node is its own ancestor |
The same question appears in computers: Git finds the commit where two branches split (the "merge base"), a file system finds the nearest folder that holds two files, and a company chart finds the lowest manager over two employees.
Words, from zero
- Ancestor of a node x: x's parent, its parent's parent, and so on up to the root. By convention, x is also an ancestor of itself.
- Descendant of x: any node below x (its children, their children, ...). x is also its own descendant.
- Subtree of x: x together with all its descendants.
- Common ancestor of p and q: a node that is an ancestor of both. The root is always one.
- Lowest common ancestor (LCA) of p and q: the common ancestor with the greatest depth (farthest from the root). "Lowest" because trees are drawn upside down.
Our example tree (the LeetCode 236 example), used everywhere below:
3
/ \
5 1
/ \ / \
6 2 0 8
/ \
7 4
| Question | Answer | Why |
|---|---|---|
| Ancestors of 7 | 7, 2, 5, 3 | walk up parent by parent (7 counts itself) |
| Descendants of 5 | 5, 6, 2, 7, 4 | its whole subtree |
| Common ancestors of 7 and 4 | 2, 5, 3 | on both lists |
| LCA(7, 4) | 2 | the deepest common ancestor |
| LCA(5, 4) | 5 | 5 is above 4, and 5 is its own ancestor |
| LCA(5, 1) | 3 | they are in different subtrees of the root |
Why "a node is its own ancestor"? Without it, LCA(5, 4) would be 3, which is silly: 5 is directly above 4. With the rule, the answer is simply the higher of the two.
Problem statement
Lowest Common Ancestor of a Binary Tree (LeetCode 236). Given the root of a binary tree and two nodes p and q in it, return their lowest common ancestor.
- It is a plain binary tree: values are in no particular order (it is not a binary search tree).
pandqare node references, both guaranteed to exist in the tree; all values are unique;pmay equalq.- LeetCode allows up to 10^5 nodes.
p = 5, q = 1 → 3 (different subtrees of the root)
p = 5, q = 4 → 5 (p is an ancestor of q)
p = 5, q = 5 → 5 (p == q)
p = 3, q = 7 → 3 (p is the root)
p = 7, q = 8 → 3 (far apart)
p = 6, q = 4 → 5
All programs use this Node class and a helper find that returns the node with a given value (so that we can pass real nodes as p and q):
static class Node {
int val;
Node left, right;
Node(int v) { val = v; }
Node(int v, Node l, Node r) { val = v; left = l; right = r; }
}
static Node find(Node n, int v) {
if (n == null || n.val == v) return n;
Node l = find(n.left, v);
return l != null ? l : find(n.right, v);
}
Brute force: walk down to the side that holds both
- If the root is
porq, it is the answer (it is above the other one, or equal to it). - Otherwise search the left subtree: is
pthere? Isqthere? - Both on the left: the answer is on the left, so move left. Neither: move right.
- One on each side: their paths split here, so this node is the LCA.
contains(n, x) answers "is node x anywhere under n?" by visiting the subtree.
import java.util.*;
public class Main {
static class Node {
int val;
Node left, right;
Node(int v) { val = v; }
Node(int v, Node l, Node r) { val = v; left = l; right = r; }
}
static boolean contains(Node n, Node x) {
if (n == null) return false;
return n == x || contains(n.left, x) || contains(n.right, x);
}
static Node bruteLCA(Node root, Node p, Node q) {
if (root == p || root == q) return root;
boolean pLeft = contains(root.left, p);
boolean qLeft = contains(root.left, q);
if (pLeft && qLeft) return bruteLCA(root.left, p, q);
if (!pLeft && !qLeft) return bruteLCA(root.right, p, q);
return root;
}
static Node find(Node n, int v) {
if (n == null || n.val == v) return n;
Node l = find(n.left, v);
return l != null ? l : find(n.right, v);
}
public static void main(String[] args) {
Node t = new Node(3, new Node(5, new Node(6),
new Node(2, new Node(7), new Node(4))),
new Node(1, new Node(0), new Node(8)));
System.out.println(bruteLCA(t, find(t, 5), find(t, 1)).val);
System.out.println(bruteLCA(t, find(t, 5), find(t, 4)).val);
}
}
Real output:
3
5
Correct. Now a huge, tall "family": full(21) builds a complete tree 21 levels deep (2^21 - 1 = 20,97,151 ≈ 21 lakh nodes), and a single line of 3,000 ancestors (each with only a left child) is put on top of it. p is the last leaf on the right edge of the big tree's left half, q the last leaf on the right edge of its right half, so their LCA is the big tree's root bottom.
import java.util.*;
public class Main {
static class Node {
int val;
Node left, right;
Node(int v) { val = v; }
Node(int v, Node l, Node r) { val = v; left = l; right = r; }
}
static boolean contains(Node n, Node x) {
if (n == null) return false;
return n == x || contains(n.left, x) || contains(n.right, x);
}
static Node bruteLCA(Node root, Node p, Node q) {
if (root == p || root == q) return root;
boolean pLeft = contains(root.left, p);
boolean qLeft = contains(root.left, q);
if (pLeft && qLeft) return bruteLCA(root.left, p, q);
if (!pLeft && !qLeft) return bruteLCA(root.right, p, q);
return root;
}
static Node full(int depth) {
if (depth == 0) return null;
return new Node(depth, full(depth - 1), full(depth - 1));
}
public static void main(String[] args) {
Node bottom = full(21), root = bottom;
for (int i = 1; i <= 3000; i++) root = new Node(-i, root, null);
Node p = bottom.left, q = bottom.right;
while (p.right != null) p = p.right;
while (q.right != null) q = q.right;
long t0 = System.nanoTime();
Node ans = bruteLCA(root, p, q);
long ms = (System.nanoTime() - t0) / 1000000;
System.out.println("correct: " + (ans == bottom) + ", " + ms + " ms");
}
}
Real result: Time Limit Exceeded in the compiler (8 s). Run locally without a limit, it printed correct: true, 48967 ms, correct: true, 64303 ms and correct: true, 71054 ms in three runs (about a minute).
Why the brute force fails
At each of the 3,000 steps down the chain, contains(root.left, p) and contains(root.left, q) search the subtree below again from scratch. The 21 lakh nodes sit below every one of those steps: about half of them are visited to find p, and all of them to find q, so roughly 31 lakh visits per step, × 3,000 steps ≈ 940 crore node visits.
In general: at depth d the search costs the size of the subtree, so the total is O(n) per level, O(n · h) for height h. For a balanced tree (h ≈ log n) that is fine; for a tall, chain-like tree (h ≈ n) it is O(n²). The same people are found again and again.
The key insight: one postorder pass, answers flow up
Instead of searching down repeatedly, let every node report up what it found. That is postorder (left, right, then the node), the same pattern as episode 37 where every node asked its children for their heights.
lca(root, p, q) returns:
| Situation at this node | Return |
|---|---|
empty subtree (root == null) |
null (nothing found) |
this node is p or q |
this node |
| left result and right result both non-null | this node: the LCA |
| only one side non-null | pass that one up unchanged |
| both null | null |
Trace for p = 7, q = 8 (children answer before parents):
| Node | left returns | right returns | node returns |
|---|---|---|---|
| 6 | null | null | null |
| 7 | (not visited: 7 is p) | 7 | |
| 4 | null | null | null |
| 2 | 7 | null | 7 |
| 5 | null (from 6) | 7 | 7 |
| 0 | null | null | null |
| 8 | (not visited: 8 is q) | 8 | |
| 1 | null | 8 | 8 |
| 3 | 7 | 8 | 3 (both non-null: the LCA) |
Why returning p early is safe
When the walk reaches p, it returns at once without looking below p. If q is below p, then p is the LCA (a node is its own ancestor), and p is exactly what travels up, because the other side of every node above it returns null. If q is elsewhere, some node above receives p from one side and q from the other and becomes the answer. For p = 5, q = 4, node 5 is returned and node 4 is never visited.
This relies on the guarantee that both p and q are in the tree. If q is missing, lca still returns p (see the mistakes table); then check both exist first, or count how many of the two were actually found.
The optimal solution in Java
static Node lca(Node root, Node p, Node q) {
if (root == null || root == p || root == q) return root;
Node left = lca(root.left, p, q);
Node right = lca(root.right, p, q);
if (left != null && right != null) return root;
return left != null ? left : right;
}
import java.util.*;
public class Main {
static class Node {
int val;
Node left, right;
Node(int v) { val = v; }
Node(int v, Node l, Node r) { val = v; left = l; right = r; }
}
static Node lca(Node root, Node p, Node q) {
if (root == null || root == p || root == q) return root;
Node left = lca(root.left, p, q);
Node right = lca(root.right, p, q);
if (left != null && right != null) return root;
return left != null ? left : right;
}
static Node find(Node n, int v) {
if (n == null || n.val == v) return n;
Node l = find(n.left, v);
return l != null ? l : find(n.right, v);
}
public static void main(String[] args) {
Node t = new Node(3, new Node(5, new Node(6),
new Node(2, new Node(7), new Node(4))),
new Node(1, new Node(0), new Node(8)));
System.out.println(lca(t, find(t, 5), find(t, 1)).val);
System.out.println(lca(t, find(t, 5), find(t, 4)).val);
System.out.println(lca(t, find(t, 5), find(t, 5)).val);
System.out.println(lca(t, find(t, 3), find(t, 7)).val);
System.out.println(lca(t, find(t, 7), find(t, 8)).val);
System.out.println(lca(t, find(t, 6), find(t, 4)).val);
}
}
Real output:
3
5
5
3
3
5
The six cases: different subtrees (5, 1), p an ancestor of q (5, 4), p == q (5, 5), p is the root (3, 7), far apart (7, 8), and (6, 4).
On the huge tree that timed out:
import java.util.*;
public class Main {
static class Node {
int val;
Node left, right;
Node(int v) { val = v; }
Node(int v, Node l, Node r) { val = v; left = l; right = r; }
}
static Node lca(Node root, Node p, Node q) {
if (root == null || root == p || root == q) return root;
Node left = lca(root.left, p, q);
Node right = lca(root.right, p, q);
if (left != null && right != null) return root;
return left != null ? left : right;
}
static Node full(int depth) {
if (depth == 0) return null;
return new Node(depth, full(depth - 1), full(depth - 1));
}
public static void main(String[] args) {
Node bottom = full(21), root = bottom;
for (int i = 1; i <= 3000; i++) root = new Node(-i, root, null);
Node p = bottom.left, q = bottom.right;
while (p.right != null) p = p.right;
while (q.right != null) q = q.right;
long t0 = System.nanoTime();
Node ans = lca(root, p, q);
long ms = (System.nanoTime() - t0) / 1000000;
System.out.println("correct: " + (ans == bottom) + ", " + ms + " ms");
}
}
Real output: correct: true, 20 ms (a few milliseconds in every run).
Stack depth: the recursion goes as deep as the tree. Here it is about 3,020 calls deep, which is fine. With a chain of 10,000 ancestors instead of 3,000, the same program ended with:
Exception in thread "main" java.lang.StackOverflowError
at Main.lca(Main.java:12)
at Main.lca(Main.java:12)
...
For very tall trees, use an iterative version: walk the tree with your own stack, store every node's parent in a HashMap, put all ancestors of p in a HashSet, then walk up from q until you hit one of them.
The same code in C++
#include <bits/stdc++.h>
using namespace std;
struct Node {
int val;
Node *left, *right;
Node(int v, Node* l = nullptr, Node* r = nullptr) : val(v), left(l), right(r) {}
};
Node* find(Node* n, int v) {
if (!n || n->val == v) return n;
Node* l = find(n->left, v);
return l ? l : find(n->right, v);
}
// optimal: one postorder pass, O(n)
Node* lca(Node* root, Node* p, Node* q) {
if (!root || root == p || root == q) return root;
Node* left = lca(root->left, p, q);
Node* right = lca(root->right, p, q);
if (left && right) return root;
return left ? left : right;
}
// bonus: binary search tree, O(h)
Node* bstLCA(Node* root, Node* p, Node* q) {
Node* cur = root;
while (cur) {
if (p->val < cur->val && q->val < cur->val) cur = cur->left;
else if (p->val > cur->val && q->val > cur->val) cur = cur->right;
else return cur;
}
return nullptr;
}
int main() {
Node* t = new Node(3, new Node(5, new Node(6), new Node(2, new Node(7), new Node(4))),
new Node(1, new Node(0), new Node(8)));
int pairs[6][2] = {{5, 1}, {5, 4}, {5, 5}, {3, 7}, {7, 8}, {6, 4}};
for (auto& pr : pairs)
cout << "lca(" << pr[0] << ", " << pr[1] << ") = "
<< lca(t, find(t, pr[0]), find(t, pr[1]))->val << '\n';
Node* b = new Node(6, new Node(2, new Node(0), new Node(4, new Node(3), new Node(5))),
new Node(8, new Node(7), new Node(9)));
cout << "bst(2, 8) = " << bstLCA(b, find(b, 2), find(b, 8))->val << '\n';
cout << "bst(2, 4) = " << bstLCA(b, find(b, 2), find(b, 4))->val << '\n';
}
Real output (g++ -O2):
lca(5, 1) = 3
lca(5, 4) = 5
lca(5, 5) = 5
lca(3, 7) = 3
lca(7, 8) = 3
lca(6, 4) = 5
bst(2, 8) = 6
bst(2, 4) = 2
The same code in Python
class Node:
def __init__(self, val, left=None, right=None):
self.val, self.left, self.right = val, left, right
def find(n, v):
if n is None or n.val == v:
return n
return find(n.left, v) or find(n.right, v)
def lca(root, p, q): # one postorder pass, O(n)
if root is None or root is p or root is q:
return root
left = lca(root.left, p, q)
right = lca(root.right, p, q)
if left and right:
return root
return left or right
def bst_lca(root, p, q): # binary search tree, O(h)
cur = root
while cur:
if p.val < cur.val and q.val < cur.val:
cur = cur.left
elif p.val > cur.val and q.val > cur.val:
cur = cur.right
else:
return cur
return None
t = Node(3, Node(5, Node(6), Node(2, Node(7), Node(4))), Node(1, Node(0), Node(8)))
for a, b in [(5, 1), (5, 4), (5, 5), (3, 7), (7, 8), (6, 4)]:
print(f"lca({a}, {b}) = {lca(t, find(t, a), find(t, b)).val}")
bst = Node(6, Node(2, Node(0), Node(4, Node(3), Node(5))), Node(8, Node(7), Node(9)))
print("bst(2, 8) =", bst_lca(bst, find(bst, 2), find(bst, 8)).val)
print("bst(2, 4) =", bst_lca(bst, find(bst, 2), find(bst, 4)).val)
Real output (python3):
lca(5, 1) = 3
lca(5, 4) = 5
lca(5, 5) = 5
lca(3, 7) = 3
lca(7, 8) = 3
lca(6, 4) = 5
bst(2, 8) = 6
bst(2, 4) = 2
Python's default recursion limit is 1000, so on a tree deeper than about 1,000 levels this raises RecursionError; use the iterative parent-map version there.
Bonus: LCA in a binary search tree (LeetCode 235)
In a binary search tree (BST), every value in a node's left subtree is smaller than the node and every value in its right subtree is bigger (episode 39 covers BSTs properly). Then the values show the way, and no searching is needed:
- both values smaller than the current node: go left;
- both bigger: go right;
- otherwise they split here (or one of them is this node): this node is the LCA.
6
/ \
2 8
/ \ / \
0 4 7 9
/ \
3 5
import java.util.*;
public class Main {
static class Node {
int val;
Node left, right;
Node(int v) { val = v; }
Node(int v, Node l, Node r) { val = v; left = l; right = r; }
}
static Node bstLCA(Node root, Node p, Node q) {
Node cur = root;
while (cur != null) {
if (p.val < cur.val && q.val < cur.val) cur = cur.left;
else if (p.val > cur.val && q.val > cur.val) cur = cur.right;
else return cur;
}
return null;
}
static Node find(Node n, int v) {
if (n == null || n.val == v) return n;
Node l = find(n.left, v);
return l != null ? l : find(n.right, v);
}
public static void main(String[] args) {
Node b = new Node(6, new Node(2, new Node(0),
new Node(4, new Node(3), new Node(5))),
new Node(8, new Node(7), new Node(9)));
System.out.println(bstLCA(b, find(b, 2), find(b, 8)).val);
System.out.println(bstLCA(b, find(b, 2), find(b, 4)).val);
System.out.println(bstLCA(b, find(b, 3), find(b, 5)).val);
}
}
Real output:
6
2
4
One walk from the root down: O(h) time and O(1) extra space (a loop, no recursion). It only works when the tree really is a BST (bug 3 below).
Brute force vs optimal
| Approach | Time | Extra space | Huge tree (3,000 chain + 21 lakh nodes) |
|---|---|---|---|
Walk down, contains both sides at each step |
O(n · h), O(n²) on a tall tree | O(h) recursion | 49-71 s locally, TLE at 8 s |
| One postorder pass | O(n) | O(h) recursion (log n balanced, n for a chain) | ~20 ms |
| Parent map + ancestor set (iterative) | O(n) | O(n) | no recursion, no stack overflow |
| BST only: walk down by value | O(h) | O(1) | (needs a BST) |
Three real bugs
Bug 1: no "both non-null" check
import java.util.*;
public class Main {
static class Node {
int val;
Node left, right;
Node(int v) { val = v; }
Node(int v, Node l, Node r) { val = v; left = l; right = r; }
}
static Node lca(Node root, Node p, Node q) {
if (root == null || root == p || root == q) return root;
Node left = lca(root.left, p, q);
Node right = lca(root.right, p, q);
return left != null ? left : right;
}
static Node find(Node n, int v) {
if (n == null || n.val == v) return n;
Node l = find(n.left, v);
return l != null ? l : find(n.right, v);
}
public static void main(String[] args) {
Node t = new Node(3, new Node(5, new Node(6),
new Node(2, new Node(7), new Node(4))),
new Node(1, new Node(0), new Node(8)));
System.out.println(lca(t, find(t, 5), find(t, 1)).val);
}
}
Real output: 5 (expected 3). At node 3 the left side returned 5 and the right side returned 1, but the code only passed up the left one. No error, just a wrong answer.
Bug 2: no root == null in the base case
import java.util.*;
public class Main {
static class Node {
int val;
Node left, right;
Node(int v) { val = v; }
Node(int v, Node l, Node r) { val = v; left = l; right = r; }
}
static Node lca(Node root, Node p, Node q) {
if (root == p || root == q) return root;
Node left = lca(root.left, p, q);
Node right = lca(root.right, p, q);
if (left != null && right != null) return root;
return left != null ? left : right;
}
static Node find(Node n, int v) {
if (n == null || n.val == v) return n;
Node l = find(n.left, v);
return l != null ? l : find(n.right, v);
}
public static void main(String[] args) {
Node t = new Node(3, new Node(5, new Node(6),
new Node(2, new Node(7), new Node(4))),
new Node(1, new Node(0), new Node(8)));
System.out.println(lca(t, find(t, 7), find(t, 8)).val);
}
}
Real output:
Exception in thread "main" java.lang.NullPointerException: Cannot read field "left" because "<parameter1>" is null
at Main.lca(Main.java:12)
at Main.lca(Main.java:12)
at Main.lca(Main.java:12)
at Main.lca(Main.java:12)
at Main.main(Main.java:26)
(For lca(t, find(t, 5), find(t, 1)) this bug stays hidden, because 5 and 1 are reached before any leaf. It shows up as soon as the walk reaches a leaf, here leaf 6 on the way to 7.)
Bug 3: the BST shortcut on a plain binary tree
import java.util.*;
public class Main {
static class Node {
int val;
Node left, right;
Node(int v) { val = v; }
Node(int v, Node l, Node r) { val = v; left = l; right = r; }
}
static Node bstLCA(Node root, Node p, Node q) {
Node cur = root;
while (cur != null) {
if (p.val < cur.val && q.val < cur.val) cur = cur.left;
else if (p.val > cur.val && q.val > cur.val) cur = cur.right;
else return cur;
}
return null;
}
static Node find(Node n, int v) {
if (n == null || n.val == v) return n;
Node l = find(n.left, v);
return l != null ? l : find(n.right, v);
}
public static void main(String[] args) {
Node t = new Node(3, new Node(5, new Node(6),
new Node(2, new Node(7), new Node(4))),
new Node(1, new Node(0), new Node(8)));
System.out.println(bstLCA(t, find(t, 6), find(t, 4)).val);
}
}
Real output:
Exception in thread "main" java.lang.NullPointerException: Cannot read field "val" because the return value of "Main.bstLCA(Main$Node, Main$Node, Main$Node)" is null
at Main.main(Main.java:28)
At 3, both 6 and 4 are bigger, so it went right, to 1, then right again to 8, then left to null, away from both nodes. Our tree is not sorted, so the value trick does not apply.
Common mistakes
| Mistake | What you see | Why | Fix |
|---|---|---|---|
No if (left != null && right != null) return root; |
prints 5 for (5, 1), expected 3 |
the split point is passed over | check both sides first |
No root == null in the base case |
java.lang.NullPointerException: Cannot read field "left" because "<parameter1>" is null |
recursion walks past a leaf | if (root == null \|\| root == p \|\| root == q) return root; |
bstLCA on a plain binary tree |
java.lang.NullPointerException: Cannot read field "val" because the return value of "Main.bstLCA(Main$Node, Main$Node, Main$Node)" is null |
values are not sorted | use the postorder lca |
q not in the tree |
lca(t, find(t, 5), find(t, 42)).val prints 5, no error |
the code assumes both exist | check both are found first |
| Comparing values instead of nodes when values can repeat | the wrong node is treated as p | two nodes share a value | compare references (root == p) |
| Very tall tree with recursion | java.lang.StackOverflowError (a 10,000 chain did it) |
one stack frame per level | iterative parent-map version |
Mini project: the family tree finder
Build a family tree as a binary tree of String names (each person has at most two children listed), for example Great-grandpa → Dadaji and his brother, Dadaji → Riya's mum and Kabir's dad, Riya's mum → Riya, Kabir's dad → Kabir. Read two names and print:
- their closest shared elder (the LCA, using
findby name andlca); - how many generations each of them is below that elder (the depth difference);
- a relationship word: same person, parent/child (one is the LCA and 1 generation apart), siblings (both 1 below), cousins (both 2 below), otherwise "related through
".
Practice
- Distance between two nodes: the number of edges on the path from p to q.
Solution
dist(p, q) = depth(p) + depth(q) - 2 · depth(lca(p, q)). Or directly: find the LCA, then the distance from the LCA down to p plus the distance down to q. Example tree: dist(7, 8) = 3 + 2 - 2·0 = 5; dist(6, 4) = 2 + 3 - 2·1 = 3.
static int depthOf(Node n, Node x, int d) {
if (n == null) return -1;
if (n == x) return d;
int l = depthOf(n.left, x, d + 1);
return l != -1 ? l : depthOf(n.right, x, d + 1);
}
static int dist(Node root, Node p, Node q) {
Node a = lca(root, p, q);
return depthOf(a, p, 0) + depthOf(a, q, 0);
}
- LCA when p or q may be missing (LeetCode 1644): return
nullif either is not in the tree.
Solution
Do not stop early at p or q: always visit both children, and count how many of p and q were seen.
static int found = 0;
static Node lca2(Node root, Node p, Node q) {
if (root == null) return null;
Node left = lca2(root.left, p, q), right = lca2(root.right, p, q);
if (root == p || root == q) { found++; return root; }
if (left != null && right != null) return root;
return left != null ? left : right;
}
// answer = lca2(root, p, q); if (found < 2) answer = null; (reset found = 0 before each call)
- LCA with parent pointers (LeetCode 1650): every node also has
parent.
Solution
Like the cousins walking up: put every ancestor of p in a HashSet, then walk up from q until a node is in the set. O(h) time. A trick with O(1) space: two pointers a = p, b = q; step each up, and when one reaches the top (null) restart it at the other node; they meet at the LCA (same idea as the intersection of two linked lists).
- LCA of the deepest leaves (LeetCode 1123).
Solution
Postorder that returns a pair (height, lca). If the left and right heights are equal, this node is the answer for its subtree; otherwise pass up the taller side's answer with height + 1. Example tree: the deepest leaves are 7 and 4, so the answer is 2.
Quick quiz
On the example tree, what is the LCA of 6 and 4? (a) 3 (b) 5 (c) 2 (d) 6
Answer
(b) 5. 6 is in 5's left subtree and 4 is in 5's right subtree (under 2), so in the postorder pass node 5 gets 6 from the left and 4 from the right: both non-null.
Interview questions
- Why is a node considered its own ancestor? So that when p is above q, the answer is p itself, and the recursive rule "return p when you reach it" is correct.
- What does the recursive function return, in words?
nullif neither p nor q is in this subtree; p or q if only one is; the LCA if both are. - Why is it O(n)? Each node is visited at most once, with O(1) work per node. Space is O(h) for the recursion stack.
- What changes if the tree is a BST? Compare values: both smaller go left, both bigger go right, else this node. O(h) time, O(1) space.
- What if p or q might not exist? The standard code returns the one that exists. Visit the whole tree and count how many were found, or check existence first.
- How would you answer many LCA queries on a fixed tree? Preprocess: binary lifting (O(n log n) preprocessing, O(log n) per query) or an Euler tour plus a range-minimum structure. These come later in the course.
- How do you avoid a StackOverflowError on a very tall tree? Iterative traversal with an explicit stack and a parent map, then walk up from p and q.
Glossary
| Term | Meaning |
|---|---|
| Ancestor | A node's parent, the parent's parent, and so on up to the root; a node counts as its own ancestor |
| Descendant | Any node below a given node (and the node itself) |
| Subtree | A node together with all its descendants |
| Common ancestor | A node that is an ancestor of both p and q |
| Lowest common ancestor (LCA) | The deepest common ancestor of p and q, the one farthest from the root |
| Depth | Number of edges from the root to a node |
| Height (h) | Number of levels in the tree |
| Postorder | Visit left subtree, right subtree, then the node: children answer first |
| Base case | The condition that stops the recursion (root == null, or root is p or q) |
null |
"No node here"; reading a field of it throws NullPointerException |
| Node reference | A variable pointing at a specific node object; root == p compares references, not values |
| Binary tree | Every node has at most two children, left and right |
| Binary search tree (BST) | A binary tree where left-subtree values are smaller and right-subtree values are bigger than the node |
| Brute force | The straightforward solution, correct but slow |
| O(n · h) | Work proportional to the number of nodes times the height |
| Time Limit Exceeded (TLE) | The program ran longer than allowed (8 s in the SyntaxPilot compiler) |
StackOverflowError |
Java's error when recursion goes too deep for the call stack |
RecursionError |
Python's error when recursion passes the recursion limit (1000 by default) |
| Merge base | Git's name for the LCA of two commits |
Summary
- An ancestor is any node on the way up to the root, and a node is its own ancestor. The LCA of p and q is their deepest common ancestor.
- Walking down and searching both sides at every step is O(n · h): O(n²) on a tall tree, and it timed out on a 3,000-level chain above 21 lakh nodes (about a minute locally).
- One postorder pass: return
null, p or q upward; the node where left and right both come back non-null is the LCA. O(n) time, O(h) space; 20 ms on the same tree. - Edge cases handled for free: p above q, p == q, p or q is the root, nodes in different subtrees. It assumes both nodes exist.
- In a BST, walk down by value: O(h), O(1).
Next episode: Validate a BST and the kth smallest element.