What signals in a problem statement indicate the Lowest common ancestor sub-pattern?

"lowest common ancestor"; "a node can be a descendant of itself"; "smallest subtree containing all the deepest nodes"

Lowest common ancestor (Tree DFS Sub-pattern)

Q: What makes Lowest common ancestor different from other sub-patterns?

**LCA of a BST** compares values: both smaller go left, both larger go right, otherwise this is the split. O(h), no recursion needed. **LCA of a Binary Tree** has no order to use, so one post-order pass returns "what I found below"; when both sides return something, you're at the LCA. **LCA of Deepest Leaves** returns a **pair** (deepest depth below, the LCA of those leaves); equal depths on both sides make the current node the answer.

Find the deepest node that has both targets in its subtree: the first node where the two targets split to different sides.

Signals in the problem statement

›
"lowest common ancestor"
›
"a node can be a descendant of itself"
›
"smallest subtree containing all the deepest nodes"

What makes it different

LCA of a BST compares values: both smaller go left, both larger go right, otherwise this is the split. O(h), no recursion needed. LCA of a Binary Tree has no order to use, so one post-order pass returns "what I found below"; when both sides return something, you're at the LCA. LCA of Deepest Leaves returns a pair (deepest depth below, the LCA of those leaves); equal depths on both sides make the current node the answer.

Questions

ordered from “learn the idea” to “recognise it without help”

1
Lowest Common Ancestor of a BST
Basic Anchor·LeetCode #235
WalkthroughMedium
2
Lowest Common Ancestor of a Binary Tree
Medium·LeetCode #236
WalkthroughMedium
3
Lowest Common Ancestor of Deepest Leaves
Interview-Level·LeetCode #1123
WalkthroughMedium

Template

lca-template.cpp

// Lowest common ancestor in a plain binary tree, in one post-order pass.
// Each call returns p or q if it found one below (or is one), else nullptr.
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    if (!root || root == p || root == q) return root;
    TreeNode* left = lowestCommonAncestor(root->left, p, q);
    TreeNode* right = lowestCommonAncestor(root->right, p, q);
    if (left && right) return root;                      // p and q split here: this is the LCA
    return left ? left : right;                          // pass up whichever side found something
}

Remember this · Tree DFS

Trigger

Paths, heights, diameters, validating structure, ancestors, anything "for every subtree".

Think

If my left and right children already gave me their answers, how do I build mine?

Key question

What does my recursive function return, and what do I pass down?

BST properties Build / transform / serialize