A moderation queue stores nested content buckets as a binary tree. IDs are assignment keys, not search order. Two flagged posts need the lowest bucket that still covers both so the takedown policy attaches once, as deep as possible. The first patch compared IDs and walked like LCA of a BST. That post walks the split by comparing keys. Here 9 sits left of 3 — a value walk of 9 and 4 splits at 8; the LCA is 3. Search both subtrees.

The lowest common ancestor is the deepest node that still has both targets under it — including itself. DFS owns recursion versus an explicit stack. Here we only care about searching both children and bubbling a hit. Do not stamp finish times.

The problem

Given the root of a binary tree and two nodes p and q that exist in the tree, return their lowest common ancestor. A node may be an ancestor of itself. Empty tree and missing keys are out of contract — the prompt promises both nodes are present.

final class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int val) {
        this.val = val;
    }
}

Sample tree and the shapes that matter: a true split, a node that is an ancestor of the other, a split one level down, and why a value walk fails. The drawing is unordered — 9 left of 3 is legal.

        8
       / \
      3   1
     / \ / \
    9  4 7  2
      / \
     6   5

p=3, q=1  →  8     split at the root
p=3, q=4  →  3     3 is an ancestor of 4
p=6, q=5  →  4     both under 4
p=9, q=4  →  3     a BST walk would return 8

Note: Do not start a three-way value split. That is LCA of a BST. Comparing p.val to node.val here sends you down the wrong child: p=9, q=4 would return 8.

Two paths, last shared node

Walk from the root to p, then from the root to q. The last shared node is the LCA — correct, extra lists. On a BST this ignores an order you already paid for. Here there was no order to ignore.

TreeNode lowestCommonAncestorBrute(TreeNode root, TreeNode p, TreeNode q) {
    List<TreeNode> pathP = new ArrayList<>();
    List<TreeNode> pathQ = new ArrayList<>();
    pathTo(root, p, pathP);
    pathTo(root, q, pathQ);
    TreeNode lca = null;
    int n = Math.min(pathP.size(), pathQ.size());
    for (int i = 0; i < n && pathP.get(i) == pathQ.get(i); i++) {
        lca = pathP.get(i);
    }
    return lca;
}

boolean pathTo(TreeNode node, TreeNode target, List<TreeNode> path) {
    if (node == null) {
        return false;
    }
    path.add(node);
    if (node == target) {
        return true;
    }
    if (pathTo(node.left, target, path) || pathTo(node.right, target, path)) {
        return true;
    }
    path.remove(path.size() - 1);
    return false;
}

At a handful of nodes this is fine. On a tall spine you built two O(h) lists for a walk the intended recursion already does with returns.

Search both sides, combine when both hit

At each node: null returns null. If this node is p or q, return it — that is the ancestor-of-itself case; do not keep walking under it looking for the other key. Otherwise recurse left and right. Both non-null means each side found one of the two, so this node is the LCA. One non-null side bubbles up. Both null means this subtree has neither.

p=3, q=1
lca(8)
  left  = lca(3) → 3 is p, return 3
  right = lca(1) → 1 is q, return 1
  both hit → 8

p=3, q=4
lca(8)
  left  = lca(3) → 3 is p, return 3    (do not search under 3)
  right = lca(1) → neither, null
  only left → 3

p=6, q=5
lca(8)
  left = lca(3)
    lca(4): lca(6) is p, lca(5) is q, both hit → 4
  right = lca(1) → null
  only left → 4

The Java is that walk:

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;
    }
    return left != null ? left : right;
}

Time is O(n) — no order, so a worst case visits every node. Space is O(h) for the call stack, h being height. A spine of a million buckets is a million frames; an explicit stack is the same bound without blowing the JVM stack.

Note: Compare node identity (root == p), not values. The arguments are node references. The BST walk compared keys because the split is the keys.

What interviewers usually poke next

  • LCA of a BST. Keys split, so you walk one path by comparing values. Different problem; do not start that loop here. Writeup: LCA of a BST.
  • Missing p or q. The prompt promised both exist. Returning early on the first hit can claim an LCA when the other key is absent. If they might be missing, say the contract changed — you would have to prove presence.
  • A node is an ancestor of itself. p=3, q=4 returning 3 is the test. If they want a strict parent, that is a different return.
  • Parent pointers. Walk to the root collecting ancestors, then take the first shared. Extra structure this prompt does not give.
  • Why the two paths then? Still correct. You paid two lists for returns the recursion already has.

You are done with this problem when you can return the node that is p when q sits under it, combine both hits at the split, and refuse to walk by comparing keys.