SyntaxPilot
Courses/DSA and Coding Problems/Lesson 38
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

DSA and Coding Problems · Lesson 38 of 90

Lowest common ancestor

queued

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).
  • p and q are node references, both guaranteed to exist in the tree; all values are unique; p may equal q.
  • 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

  1. If the root is p or q, it is the answer (it is above the other one, or equal to it).
  2. Otherwise search the left subtree: is p there? Is q there?
  3. Both on the left: the answer is on the left, so move left. Neither: move right.
  4. 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:

  1. their closest shared elder (the LCA, using find by name and lca);
  2. how many generations each of them is below that elder (the depth difference);
  3. 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

  1. 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);
    }
  1. LCA when p or q may be missing (LeetCode 1644): return null if 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)
  1. 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).

  1. 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

  1. 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.
  2. What does the recursive function return, in words? null if neither p nor q is in this subtree; p or q if only one is; the LCA if both are.
  3. 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.
  4. 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.
  5. 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.
  6. 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.
  7. 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.