LeetCode Patterns ·

🎯 LCA

1️⃣ Core Framework

When discussing LCA, I frame it as:

What Lowest Common Ancestor means
LCA in a binary tree
LCA in a binary search tree
Recursive bottom-up thinking
Parent pointer approach
LCA with missing nodes
LCA of multiple nodes
LCA with repeated queries
Binary lifting
Senior-level explanation

2️⃣ What Problem Are We Solving?

LCA stands for Lowest Common Ancestor.

Given two nodes p and q, the LCA is:

the lowest node in the tree
that has both p and q as descendants

A node can be a descendant of itself.

It is commonly used for:

Lowest common ancestor in binary tree
Lowest common ancestor in BST
LCA with parent pointers
LCA when nodes may not exist
LCA of deepest leaves
LCA of multiple nodes
Distance between two nodes in a tree
Tree path queries
Ancestor relationship problems
Binary lifting for repeated LCA queries

The core idea is:

LCA is the first node where two target nodes split into different subtrees,
or where one target node is ancestor of the other.

👉 Interview Answer

Lowest Common Ancestor is the lowest node that has both target nodes in its subtree.

In a general binary tree, I usually solve it with postorder recursion.

In a binary search tree, I can use the BST ordering property to move left or right.

The key is to understand whether the tree is a general tree, a BST, or a tree with parent pointers.

3️⃣ Basic Example

Tree

For:

p = 5
q = 1

The LCA is:

Because 5 is in the left subtree, and 1 is in the right subtree.

Another Example

For:

p = 5
q = 4

The LCA is:

Because a node can be ancestor of itself.

👉 Interview Answer

If two nodes are found in different subtrees of a node, that node is their lowest common ancestor.

If one node is an ancestor of the other, then the ancestor node itself is the LCA.

4️⃣ LCA in General Binary Tree

Key Idea

In a general binary tree, there is no ordering property.

So we search both left and right subtrees.

For each node:

If current node is null:
    return null

If current node is p or q:
    return current node

Search left subtree
Search right subtree

If both sides return non-null:
    current node is LCA

Otherwise:
    return the non-null side

Why This Works

Each recursive call returns:

p if p is found in this subtree
q if q is found in this subtree
LCA if both are found
None if neither is found

👉 Interview Answer

In a general binary tree, I use postorder recursion.

Each subtree returns whether it contains p, q, or an LCA.

If both left and right return non-null, the current node is the split point, so it is the LCA.

If only one side returns non-null, I propagate that result upward.

5️⃣ LCA Binary Tree Code

Code

def lowest_common_ancestor(root, p, q):
    if not root or root == p or root == q:
        return root

    left = lowest_common_ancestor(root.left, p, q)
    right = lowest_common_ancestor(root.right, p, q)

    if left and right:
        return root

    return left if left else right

Complexity

Time: O(n)
Space: O(h)

Where:

n = number of nodes
h = height of tree

Worst-case space can be:

O(n)

for a skewed tree.

👉 Interview Answer

The binary tree LCA solution visits each node at most once, so the time complexity is O(n).

The recursion stack uses O(h) space, where h is the height of the tree.

In the worst case of a skewed tree, h can be O(n).

6️⃣ Why Postorder Traversal?

Children Before Parent

LCA needs information from both subtrees.

The current node cannot decide until it knows:

Does left subtree contain p or q?
Does right subtree contain p or q?

So the traversal is naturally:

left
right
root

This is postorder.

Return Meaning

left = dfs(root.left)
right = dfs(root.right)

Then:

left and right both exist -> current node is LCA
only one exists -> pass it upward
none exists -> return None

👉 Interview Answer

LCA in a binary tree is a postorder problem because the parent needs results from both children.

Only after checking left and right subtrees can the current node know whether it is the split point.

That is why the recursion processes children before deciding the current node’s result.

7️⃣ LCA in Binary Search Tree

BST Property

For every node:

left subtree values < node.val
right subtree values > node.val

So for nodes p and q:

If both are smaller than root:
    LCA is in left subtree

If both are larger than root:
    LCA is in right subtree

Otherwise:
    root is the split point

Key Insight

In a BST, we do not need to search both sides.

We can use ordering to choose one direction.

👉 Interview Answer

In a BST, LCA can be found using the ordering property.

If both target values are smaller than the current node, move left.

If both are larger, move right.

Otherwise, the current node is where the paths split, so it is the LCA.

8️⃣ LCA BST Code

Recursive Code

def lowest_common_ancestor_bst(root, p, q):
    if p.val < root.val and q.val < root.val:
        return lowest_common_ancestor_bst(root.left, p, q)

    if p.val > root.val and q.val > root.val:
        return lowest_common_ancestor_bst(root.right, p, q)

    return root

Iterative Code

def lowest_common_ancestor_bst(root, p, q):
    current = root

    while current:
        if p.val < current.val and q.val < current.val:
            current = current.left
        elif p.val > current.val and q.val > current.val:
            current = current.right
        else:
            return current

    return None

Complexity

Time: O(h)
Space: O(1) iterative

👉 Interview Answer

In a BST, the LCA can be found in O(h), where h is the tree height.

The iterative version uses O(1) extra space.

This is more efficient than searching the entire tree because the BST property tells us which direction to go.

9️⃣ Binary Tree LCA vs BST LCA

General Binary Tree

Need to search both sides.

No ordering information.
Use postorder recursion.
Time: O(n)

Binary Search Tree

Use values to move left or right.

Ordering information exists.
Use split point logic.
Time: O(h)

Comparison

Tree Type	Best Pattern	Why
General Binary Tree	Postorder DFS	Need search both subtrees
BST	Value comparison	Can use ordering
Tree with Parent Pointer	Ancestor set / two pointers	Can move upward
Many LCA Queries	Binary lifting	Preprocess ancestors

👉 Interview Answer

For a general binary tree, I cannot use values to guide the search, so I use postorder DFS.

For a BST, I use the ordering property.

The current node is the LCA when p and q split into different directions, or when the current node equals one of them.

🔟 LCA With Parent Pointers

Problem

Each node has a parent pointer:

node.parent

Find LCA of two nodes.

Idea 1: Ancestor Set

Put all ancestors of p into a set.

Then move upward from q.

The first node also in the set is the LCA.

Code

def lowest_common_ancestor_parent(p, q):
    ancestors = set()

    while p:
        ancestors.add(p)
        p = p.parent

    while q:
        if q in ancestors:
            return q

        q = q.parent

    return None

👉 Interview Answer

With parent pointers, I can move upward from each node.

A simple solution is to store all ancestors of one node in a set, then walk upward from the other node.

The first common ancestor is the LCA.

1️⃣1️⃣ Parent Pointer Two-Pointer Method

Code

def lowest_common_ancestor_parent(p, q):
    a = p
    b = q

    while a != b:
        a = a.parent if a else q
        b = b.parent if b else p

    return a

Why It Works

Both pointers travel the same total distance:

distance from p to root + distance from q to root

So they align at the common ancestor.

👉 Interview Answer

The two-pointer parent approach is similar to linked list intersection.

Each pointer walks upward.

When it reaches null, it switches to the other node.

This equalizes path lengths, and the pointers meet at the lowest common ancestor.

1️⃣2️⃣ LCA When Nodes May Not Exist

Problem

Sometimes the problem does not guarantee that both p and q exist in the tree.

The standard LCA code may return one node even if the other is missing.

Example:

p exists
q does not exist

Standard code may return:

But correct answer may be:

None

Safer Approach

Return both:

candidate LCA
whether p was found
whether q was found

Code

def lowest_common_ancestor_maybe_missing(root, p, q):
    def dfs(node):
        if not node:
            return None, False, False

        left_lca, left_has_p, left_has_q = dfs(node.left)
        right_lca, right_has_p, right_has_q = dfs(node.right)

        has_p = left_has_p or right_has_p or node == p
        has_q = left_has_q or right_has_q or node == q

        if node == p or node == q:
            return node, has_p, has_q

        if left_lca and right_lca:
            return node, has_p, has_q

        if left_lca:
            return left_lca, has_p, has_q

        if right_lca:
            return right_lca, has_p, has_q

        return None, has_p, has_q

    lca, has_p, has_q = dfs(root)

    return lca if has_p and has_q else None

👉 Interview Answer

If the problem does not guarantee both nodes exist, the standard LCA solution is not enough.

I need to track whether p and q were actually found.

Only if both nodes are found should I return the LCA.

Otherwise, I return None.

1️⃣3️⃣ LCA of Multiple Nodes

Problem

Find the LCA of a list of nodes.

Example:

nodes = [7, 4, 6]

Idea

Convert target nodes into a set.

During DFS:

if current node is in target set:
    return current node

Then same LCA logic applies.

Code

def lowest_common_ancestor_multiple(root, nodes):
    targets = set(nodes)

    def dfs(node):
        if not node:
            return None

        if node in targets:
            return node

        left = dfs(node.left)
        right = dfs(node.right)

        if left and right:
            return node

        return left if left else right

    return dfs(root)

👉 Interview Answer

LCA of multiple nodes is a generalization of LCA of two nodes.

I put all target nodes into a set.

During DFS, if the current node is a target, I return it.

If targets are found from multiple child branches, the current node becomes the LCA.

1️⃣4️⃣ LCA of Deepest Leaves

Problem

Find the LCA of the deepest leaves in a binary tree.

Key Idea

Return two things from each subtree:

depth
lca

If left depth equals right depth:

current node is LCA

If one side is deeper:

return that side's LCA

Code

def lca_deepest_leaves(root):
    def dfs(node):
        if not node:
            return 0, None

        left_depth, left_lca = dfs(node.left)
        right_depth, right_lca = dfs(node.right)

        if left_depth == right_depth:
            return left_depth + 1, node

        if left_depth > right_depth:
            return left_depth + 1, left_lca

        return right_depth + 1, right_lca

    depth, lca = dfs(root)
    return lca

👉 Interview Answer

For LCA of deepest leaves, each subtree returns its depth and the LCA of its deepest leaves.

If left and right depths are equal, the deepest leaves exist on both sides, so the current node is their LCA.

If one side is deeper, the answer comes from that deeper side.

1️⃣5️⃣ Distance Between Two Nodes

Problem

Find the distance between two nodes in a binary tree.

Idea

Use LCA.

Distance is:

distance(lca, p) + distance(lca, q)

Code

def distance_between_nodes(root, p, q):
    lca = lowest_common_ancestor(root, p, q)

    def distance(node, target):
        if not node:
            return -1

        if node == target:
            return 0

        left = distance(node.left, target)
        if left != -1:
            return left + 1

        right = distance(node.right, target)
        if right != -1:
            return right + 1

        return -1

    return distance(lca, p) + distance(lca, q)

👉 Interview Answer

To find distance between two tree nodes, I first find their LCA.

Then the path from p to q must go through the LCA.

So the distance is the distance from LCA to p plus the distance from LCA to q.

1️⃣6️⃣ LCA in N-ary Tree

Problem

Each node may have many children.

Idea

Same as binary tree, but instead of checking left and right, count how many child subtrees return non-null.

If at least two branches return targets:

current node is LCA

Code

def lowest_common_ancestor_nary(root, p, q):
    if not root or root == p or root == q:
        return root

    found = []

    for child in root.children:
        result = lowest_common_ancestor_nary(child, p, q)

        if result:
            found.append(result)

    if len(found) >= 2:
        return root

    if len(found) == 1:
        return found[0]

    return None

👉 Interview Answer

LCA in an N-ary tree is similar to LCA in a binary tree.

The difference is that the current node may have many child branches.

If targets are found in two or more different child branches, the current node is the LCA.

Otherwise, I return the non-null result upward.

1️⃣7️⃣ Binary Lifting for Repeated LCA Queries

Problem

If there are many LCA queries, running DFS every time may be too slow.

For example:

n = 100000
queries = 100000

O(n) per query is too expensive.

Binary Lifting Idea

Preprocess ancestors:

up[node][j] = the 2^j-th ancestor of node

Then each query can jump upward in powers of two.

Complexity

Preprocessing: O(n log n)
Query: O(log n)
Space: O(n log n)

👉 Interview Answer

For many LCA queries, I would use binary lifting.

I preprocess each node’s 2^j-th ancestor.

Then during a query, I first lift the deeper node to the same depth, and then lift both nodes together until their parents match.

This gives O(log n) per query after O(n log n) preprocessing.

1️⃣8️⃣ Binary Lifting Template

Code Skeleton

from collections import defaultdict

class LCA:
    def __init__(self, n, edges, root=0):
        self.LOG = 20
        self.graph = defaultdict(list)
        self.depth = [0] * n
        self.up = [[-1] * self.LOG for _ in range(n)]

        for u, v in edges:
            self.graph[u].append(v)
            self.graph[v].append(u)

        self.dfs(root, -1)

    def dfs(self, node, parent):
        self.up[node][0] = parent

        for j in range(1, self.LOG):
            if self.up[node][j - 1] != -1:
                self.up[node][j] = self.up[self.up[node][j - 1]][j - 1]

        for neighbor in self.graph[node]:
            if neighbor == parent:
                continue

            self.depth[neighbor] = self.depth[node] + 1
            self.dfs(neighbor, node)

    def query(self, a, b):
        if self.depth[a] < self.depth[b]:
            a, b = b, a

        diff = self.depth[a] - self.depth[b]

        for j in range(self.LOG):
            if diff & (1 << j):
                a = self.up[a][j]

        if a == b:
            return a

        for j in range(self.LOG - 1, -1, -1):
            if self.up[a][j] != self.up[b][j]:
                a = self.up[a][j]
                b = self.up[b][j]

        return self.up[a][0]

Note

For larger n, compute:

LOG = n.bit_length()

instead of hardcoding 20.

👉 Interview Answer

Binary lifting stores ancestors at powers of two.

To answer a query, I first lift the deeper node to the same depth as the shallower node.

Then I lift both nodes upward from large jumps to small jumps.

When their parents become the same, that parent is the LCA.

1️⃣9️⃣ Euler Tour + RMQ

Alternative for Many Queries

Another advanced LCA method is:

Euler Tour + Range Minimum Query

Idea

Do a DFS Euler tour.

Record:

node visit order
depth of each visit
first occurrence of each node

Then LCA becomes:

the node with minimum depth
between first occurrences of p and q in Euler tour

Complexity

With Sparse Table:

Preprocessing: O(n log n)
Query: O(1)

👉 Interview Answer

Euler Tour plus RMQ is another way to answer many LCA queries.

During DFS, I record the Euler traversal and depth of each visit.

The LCA of two nodes is the minimum-depth node between their first occurrences in the Euler tour.

With Sparse Table, queries can be answered in O(1) after preprocessing.

2️⃣0️⃣ LCA for Path Queries

Common Extension

Once we can find LCA, we can answer path-related questions.

Examples:

distance between two nodes
sum of values on path
min edge on path
max edge on path
ancestor check

Common Formula

For distance:

dist(u, v) = depth[u] + depth[v] - 2 * depth[lca(u, v)]

With Prefix Sum on Tree

If each node has a value, path sum can be:

prefix[u] + prefix[v] - 2 * prefix[lca] + value[lca]

👉 Interview Answer

LCA is often a building block for tree path queries.

Once I know the lowest common ancestor, the path from u to v is split into u to LCA and LCA to v.

This allows formulas for distance, path sum, and other path aggregations.

2️⃣1️⃣ Common Edge Cases

One Node Is Ancestor of the Other

p is ancestor of q

Then:

LCA = p

p Equals q

If:

p == q

Then:

LCA = p

Empty Tree

root = None

Return:

None

One or Both Nodes Missing

Need special handling if not guaranteed.

Duplicate Values

Compare node references, not only values, unless problem gives values only.

Skewed Tree

Recursive stack may become O(n).

👉 Interview Answer

Common LCA edge cases include one node being ancestor of the other, p and q being the same node, empty tree, missing nodes, duplicate values, and skewed trees.

In most binary tree LCA problems, I compare node references rather than values.

2️⃣2️⃣ Common Mistakes

Mistake 1: Using BST Logic on General Binary Tree

BST value comparison only works for BST.

Mistake 2: Returning Root Too Early

In general binary tree, only return root immediately if:

root == p or root == q

Otherwise, must check both subtrees.

Mistake 3: Ignoring Missing Nodes

Standard LCA assumes both nodes exist.

If not guaranteed, must verify both were found.

Mistake 4: Comparing Values Instead of Nodes

If duplicate values exist, this is wrong:

root.val == p.val

Better:

root == p

Mistake 5: Forgetting Parent Pointer Null Handling

Parent pointer solutions must handle root parent being null.

Mistake 6: Binary Lifting LOG Too Small

If LOG is too small, ancestor jumps may fail.

Use:

LOG = n.bit_length()

👉 Interview Answer

Common LCA mistakes include applying BST logic to a general binary tree, ignoring the case where nodes may be missing, comparing node values instead of node references, mishandling parent pointer nulls, and using too small a LOG value in binary lifting.

2️⃣3️⃣ When LCA Applies

Good Fit

Use LCA when the problem asks for:

lowest common ancestor
common ancestor
distance between two tree nodes
path between two nodes
relationship between two nodes
tree path query
ancestor check
deepest leaves ancestor

Problem Signals

Look for words like:

ancestor
common ancestor
lowest
path between nodes
distance in tree
parent pointer
rooted tree
subtree contains both

👉 Interview Answer

I consider LCA when the problem asks about the relationship between two nodes in a tree.

Common signals include common ancestor, path between two nodes, distance in a tree, and ancestor-descendant relationships.

Then I choose the approach based on whether the tree is a binary tree, BST, parent-pointer tree, or many-query tree.

2️⃣4️⃣ When LCA Does Not Apply

Not Good Fit

LCA may not be enough when:

graph is not a tree
graph has cycles
need shortest path in weighted graph
need connected components only
need topological ordering
need dynamic tree updates

Better Alternatives

Problem Type	Better Pattern
General graph shortest path	BFS / Dijkstra
Graph with cycles	Graph DFS with visited
Dependency order	Topological Sort
Dynamic connectivity	Union Find
Dynamic tree path queries	Heavy-Light Decomposition
Subtree range query	Euler Tour + Segment Tree

👉 Interview Answer

LCA is specifically a tree concept.

If the structure is a general graph with cycles, LCA may not be well-defined unless the graph is rooted as a tree.

If the problem involves weighted shortest paths, dependency ordering, or dynamic updates, other algorithms may be more appropriate.

2️⃣5️⃣ Standard Templates

Binary Tree LCA Template

def lowest_common_ancestor(root, p, q):
    if not root or root == p or root == q:
        return root

    left = lowest_common_ancestor(root.left, p, q)
    right = lowest_common_ancestor(root.right, p, q)

    if left and right:
        return root

    return left if left else right

BST LCA Template

def lowest_common_ancestor_bst(root, p, q):
    current = root

    while current:
        if p.val < current.val and q.val < current.val:
            current = current.left
        elif p.val > current.val and q.val > current.val:
            current = current.right
        else:
            return current

    return None

Parent Pointer LCA Template

def lowest_common_ancestor_parent(p, q):
    ancestors = set()

    while p:
        ancestors.add(p)
        p = p.parent

    while q:
        if q in ancestors:
            return q

        q = q.parent

    return None

Parent Pointer Two-Pointer Template

def lowest_common_ancestor_parent(p, q):
    a = p
    b = q

    while a != b:
        a = a.parent if a else q
        b = b.parent if b else p

    return a

Binary Lifting Query Template

def query_lca(a, b):
    if depth[a] < depth[b]:
        a, b = b, a

    diff = depth[a] - depth[b]

    for j in range(LOG):
        if diff & (1 << j):
            a = up[a][j]

    if a == b:
        return a

    for j in range(LOG - 1, -1, -1):
        if up[a][j] != up[b][j]:
            a = up[a][j]
            b = up[b][j]

    return up[a][0]

🧠 Staff-Level Answer Final

👉 Interview Answer Full Version

Lowest Common Ancestor is the lowest node in a tree that has both target nodes in its subtree.

A node can be an ancestor of itself, so if one target node is an ancestor of the other, that node is the LCA.

For a general binary tree, I usually use postorder recursion. Each recursive call searches its subtree and returns one of four meanings: it found p, it found q, it found the LCA, or it found nothing.

At each node, I recursively search the left and right subtrees. If both sides return non-null, then p and q are found in different branches, so the current node is the LCA. If only one side returns non-null, I propagate that result upward. If the current node is p or q, I return the current node.

This binary tree solution is O(n) time, because it may visit every node, and O(h) space due to recursion stack.

For a binary search tree, I use the BST ordering property. If both p and q are smaller than the current node, I move left. If both are larger, I move right. Otherwise, the current node is the split point and therefore the LCA. This runs in O(h) time and can be O(1) space iteratively.

If nodes have parent pointers, I can move upward. One approach is to store all ancestors of one node in a set, then walk upward from the other node. Another approach is the two-pointer method, similar to linked list intersection.

If the problem does not guarantee both nodes exist, the standard binary tree LCA solution is not enough. I also need to track whether p and q were actually found. Only when both exist should I return the LCA.

For many LCA queries on a static tree, I would use binary lifting. It preprocesses each node’s 2^j-th ancestor. Then each LCA query can be answered in O(log n).

At a senior level, I would explain: what tree type we have, whether p and q are guaranteed to exist, whether nodes have parent pointers, whether we need one query or many queries, whether node values are unique, and why the selected LCA method fits those constraints.

⭐ Final Insight

LCA 的核心不是“背一个递归模板”。

它的核心是判断 tree model 和 query model：

general binary tree 用 postorder DFS， BST 用 value split point， parent pointer tree 可以向上走， nodes may be missing 时要验证存在性， many queries 时用 binary lifting 或 Euler Tour + RMQ。

Senior-level 的重点是：

当前 node 返回什么信息， p 和 q 是否 guaranteed exist，比较 node reference 还是 value，一个 node 是另一个 node ancestor 时如何处理，为什么 BST 可以只走一边，为什么 general binary tree 必须看左右子树，以及 repeated queries 为什么需要 preprocessing。

能讲清楚这些， LCA 就是一类处理 tree relationship、ancestor、path query 和 distance query 的核心模式。

中文部分

🎯 LCA

1️⃣ 核心框架

讨论 LCA 时，我通常从：

Lowest Common Ancestor 是什么
LCA in a binary tree
LCA in a binary search tree
Recursive bottom-up thinking
Parent pointer approach
LCA with missing nodes
LCA of multiple nodes
LCA with repeated queries
Binary lifting
高级工程师解释方式

2️⃣ 要解决什么问题？

LCA 是 Lowest Common Ancestor。

给定两个 nodes p 和 q， LCA 是：

tree 中最低的一个 node，
它同时拥有 p 和 q 作为 descendants

一个 node 可以是自己的 descendant。

它常用于：

Lowest common ancestor in binary tree
Lowest common ancestor in BST
LCA with parent pointers
LCA when nodes may not exist
LCA of deepest leaves
LCA of multiple nodes
Distance between two nodes in a tree
Tree path queries
Ancestor relationship problems
Binary lifting for repeated LCA queries

核心思想是：

LCA 是两个 target nodes 路径第一次分叉的 node，
或者其中一个 target node 本身就是另一个的 ancestor。

👉 面试回答

Lowest Common Ancestor 是 tree 中最低的、同时包含两个目标 nodes 的 ancestor。

在 general binary tree 中，通常用 postorder recursion。

在 binary search tree 中，可以利用 BST ordering property。

关键是先判断这是 general tree、BST，还是带 parent pointers 的 tree。

3️⃣ Basic Example

Tree

对于：

p = 5
q = 1

LCA 是：

因为 5 在 left subtree， 1 在 right subtree。

Another Example

对于：

p = 5
q = 4

LCA 是：

因为一个 node 可以是自己的 ancestor。

👉 面试回答

如果两个 nodes 分别出现在某个 node 的不同 subtrees 中，那么这个 node 就是它们的 lowest common ancestor。

如果一个 node 是另一个 node 的 ancestor，那么这个 ancestor node 本身就是 LCA。

4️⃣ LCA in General Binary Tree

Key Idea

在 general binary tree 中，没有 ordering property。

所以必须同时搜索 left 和 right subtrees。

对每个 node：

如果 current node 是 null:
    return null

如果 current node 是 p 或 q:
    return current node

搜索 left subtree
搜索 right subtree

如果左右都返回 non-null:
    current node 是 LCA

否则:
    返回 non-null 的那一侧

Why This Works

每个 recursive call 返回：

如果 p 在这个 subtree 中，返回 p
如果 q 在这个 subtree 中，返回 q
如果 p 和 q 都在这个 subtree 中，返回 LCA
如果都不在，返回 None

👉 面试回答

在 general binary tree 中，我使用 postorder recursion。

每个 subtree 返回它是否包含 p、q 或 LCA。

如果 left 和 right 都返回 non-null，说明当前 node 是 split point，所以它就是 LCA。

如果只有一边返回 non-null，就把那一边的结果向上传递。

5️⃣ LCA Binary Tree Code

Code

def lowest_common_ancestor(root, p, q):
    if not root or root == p or root == q:
        return root

    left = lowest_common_ancestor(root.left, p, q)
    right = lowest_common_ancestor(root.right, p, q)

    if left and right:
        return root

    return left if left else right

Complexity

Time: O(n)
Space: O(h)

其中：

n = number of nodes
h = height of tree

Worst case 如果是 skewed tree：

Space: O(n)

👉 面试回答

Binary tree LCA solution 会最多访问每个 node 一次，所以 time complexity 是 O(n)。

Recursion stack 使用 O(h) space， h 是 tree height。

如果是 skewed tree， h 可能退化成 O(n)。

6️⃣ Why Postorder Traversal?

Children Before Parent

LCA 需要来自两个 subtrees 的信息。

Current node 必须知道：

Left subtree 是否包含 p 或 q？
Right subtree 是否包含 p 或 q？

所以 traversal 自然是：

left
right
root

也就是 postorder。

Return Meaning

left = dfs(root.left)
right = dfs(root.right)

然后：

left and right both exist -> current node is LCA
only one exists -> pass it upward
none exists -> return None

👉 面试回答

Binary tree LCA 是 postorder problem，因为 parent 需要先得到 children 的结果。

只有检查完 left 和 right subtrees 后，当前 node 才知道自己是不是 split point。

所以 recursion 会先处理 children，再决定 current node 的返回值。

7️⃣ LCA in Binary Search Tree

BST Property

对每个 node：

left subtree values < node.val
right subtree values > node.val

所以对于 nodes p 和 q：

如果两个都小于 root:
    LCA 在 left subtree

如果两个都大于 root:
    LCA 在 right subtree

否则:
    root 是 split point

Key Insight

在 BST 中，不需要同时搜索左右两边。

可以用 ordering 选择方向。

👉 面试回答

在 BST 中， LCA 可以利用 ordering property。

如果两个 target values 都小于 current node，就往 left 走。

如果两个都大于 current node，就往 right 走。

否则， current node 就是两个路径的 split point，因此它是 LCA。

8️⃣ LCA BST Code

Recursive Code

def lowest_common_ancestor_bst(root, p, q):
    if p.val < root.val and q.val < root.val:
        return lowest_common_ancestor_bst(root.left, p, q)

    if p.val > root.val and q.val > root.val:
        return lowest_common_ancestor_bst(root.right, p, q)

    return root

Iterative Code

def lowest_common_ancestor_bst(root, p, q):
    current = root

    while current:
        if p.val < current.val and q.val < current.val:
            current = current.left
        elif p.val > current.val and q.val > current.val:
            current = current.right
        else:
            return current

    return None

Complexity

Time: O(h)
Space: O(1) iterative

👉 面试回答

在 BST 中， LCA 可以在 O(h) 时间内找到， h 是 tree height。

Iterative version 只需要 O(1) extra space。

它比搜索整棵 tree 更高效，因为 BST property 告诉我们应该往哪一边走。

9️⃣ Binary Tree LCA vs BST LCA

General Binary Tree

需要搜索两边：

No ordering information.
Use postorder recursion.
Time: O(n)

Binary Search Tree

使用 value 判断方向：

Ordering information exists.
Use split point logic.
Time: O(h)

Comparison

Tree Type	Best Pattern	Why
General Binary Tree	Postorder DFS	Need search both subtrees
BST	Value comparison	Can use ordering
Tree with Parent Pointer	Ancestor set / two pointers	Can move upward
Many LCA Queries	Binary lifting	Preprocess ancestors

👉 面试回答

对 general binary tree，不能用 values 指导搜索，所以要用 postorder DFS。

对 BST，可以利用 ordering property。

当 p 和 q 分别落在 current node 两边，或 current node 就是其中一个 target， current node 就是 LCA。

🔟 LCA With Parent Pointers

Problem

每个 node 有 parent pointer：

node.parent

求两个 nodes 的 LCA。

Idea 1: Ancestor Set

把 p 的所有 ancestors 放入 set。

然后从 q 往上走。

第一个也在 set 中的 node 就是 LCA。

Code

def lowest_common_ancestor_parent(p, q):
    ancestors = set()

    while p:
        ancestors.add(p)
        p = p.parent

    while q:
        if q in ancestors:
            return q

        q = q.parent

    return None

👉 面试回答

如果 node 有 parent pointer，就可以从 node 向上走。

一个简单方法是把一个 node 的所有 ancestors 存入 set，然后从另一个 node 向上走。

第一个共同 ancestor 就是 LCA。

1️⃣1️⃣ Parent Pointer Two-Pointer Method

Code

def lowest_common_ancestor_parent(p, q):
    a = p
    b = q

    while a != b:
        a = a.parent if a else q
        b = b.parent if b else p

    return a

Why It Works

两个 pointers 走过的总距离相同：

distance from p to root + distance from q to root

所以最终会在 common ancestor 对齐。

👉 面试回答

Parent pointer 的 two-pointer 方法类似 linked list intersection。

两个 pointers 都向 parent 方向走。

当其中一个到达 null，就切换到另一个 node。

这样可以抵消两个 nodes 深度不同的问题，最终在 lowest common ancestor 相遇。

1️⃣2️⃣ LCA When Nodes May Not Exist

Problem

有些题目不保证 p 和 q 都存在于 tree 中。

标准 LCA code 可能在其中一个 missing 时仍然返回另一个 node。

Example:

p exists
q does not exist

标准代码可能返回：

但正确答案可能应该是：

None

Safer Approach

返回三个信息：

candidate LCA
whether p was found
whether q was found

Code

def lowest_common_ancestor_maybe_missing(root, p, q):
    def dfs(node):
        if not node:
            return None, False, False

        left_lca, left_has_p, left_has_q = dfs(node.left)
        right_lca, right_has_p, right_has_q = dfs(node.right)

        has_p = left_has_p or right_has_p or node == p
        has_q = left_has_q or right_has_q or node == q

        if node == p or node == q:
            return node, has_p, has_q

        if left_lca and right_lca:
            return node, has_p, has_q

        if left_lca:
            return left_lca, has_p, has_q

        if right_lca:
            return right_lca, has_p, has_q

        return None, has_p, has_q

    lca, has_p, has_q = dfs(root)

    return lca if has_p and has_q else None

👉 面试回答

如果题目不保证两个 nodes 都存在，标准 LCA solution 不够。

我需要额外追踪 p 和 q 是否真的被找到。

只有当两个 nodes 都存在时，才返回 LCA。

否则返回 None。

1️⃣3️⃣ LCA of Multiple Nodes

Problem

求一组 nodes 的 LCA。

Example:

nodes = [7, 4, 6]

Idea

把 target nodes 放入 set。

DFS 时：

如果 current node 在 target set 中:
    return current node

然后使用相同的 LCA 逻辑。

Code

def lowest_common_ancestor_multiple(root, nodes):
    targets = set(nodes)

    def dfs(node):
        if not node:
            return None

        if node in targets:
            return node

        left = dfs(node.left)
        right = dfs(node.right)

        if left and right:
            return node

        return left if left else right

    return dfs(root)

👉 面试回答

多个 nodes 的 LCA 是两个 nodes LCA 的泛化。

我会把所有 target nodes 放入 set。

DFS 时，如果 current node 是 target，就返回它。

如果多个 child branches 中都找到 target， current node 就是 LCA。

1️⃣4️⃣ LCA of Deepest Leaves

Problem

求 binary tree 中 deepest leaves 的 LCA。

Key Idea

每个 subtree 返回两个信息：

depth
lca

如果 left depth 等于 right depth：

current node 是 LCA

如果一边更深：

返回更深那边的 LCA

Code

def lca_deepest_leaves(root):
    def dfs(node):
        if not node:
            return 0, None

        left_depth, left_lca = dfs(node.left)
        right_depth, right_lca = dfs(node.right)

        if left_depth == right_depth:
            return left_depth + 1, node

        if left_depth > right_depth:
            return left_depth + 1, left_lca

        return right_depth + 1, right_lca

    depth, lca = dfs(root)
    return lca

👉 面试回答

对 deepest leaves 的 LCA，每个 subtree 返回 depth 和它内部 deepest leaves 的 LCA。

如果 left 和 right depths 相同，说明 deepest leaves 分布在两边， current node 是 LCA。

如果一边更深，答案来自更深那一边。

1️⃣5️⃣ Distance Between Two Nodes

Problem

求 binary tree 中两个 nodes 的 distance。

Idea

使用 LCA。

Distance 是：

distance(lca, p) + distance(lca, q)

Code

def distance_between_nodes(root, p, q):
    lca = lowest_common_ancestor(root, p, q)

    def distance(node, target):
        if not node:
            return -1

        if node == target:
            return 0

        left = distance(node.left, target)
        if left != -1:
            return left + 1

        right = distance(node.right, target)
        if right != -1:
            return right + 1

        return -1

    return distance(lca, p) + distance(lca, q)

👉 面试回答

求两个 tree nodes 的 distance 时，我先找它们的 LCA。

从 p 到 q 的路径一定经过 LCA。

所以 distance 等于 LCA 到 p 的距离，加上 LCA 到 q 的距离。

1️⃣6️⃣ LCA in N-ary Tree

Problem

每个 node 可能有很多 children。

Idea

和 binary tree 类似，只是从 left/right 变成遍历所有 children。

如果至少两个 child branches 返回 non-null：

current node 是 LCA

Code

def lowest_common_ancestor_nary(root, p, q):
    if not root or root == p or root == q:
        return root

    found = []

    for child in root.children:
        result = lowest_common_ancestor_nary(child, p, q)

        if result:
            found.append(result)

    if len(found) >= 2:
        return root

    if len(found) == 1:
        return found[0]

    return None

👉 面试回答

N-ary tree 中的 LCA 和 binary tree 类似。

区别是 current node 有多个 child branches。

如果两个或多个 child branches 中找到了 target， current node 就是 LCA。

否则把 non-null result 向上传递。

1️⃣7️⃣ Binary Lifting for Repeated LCA Queries

Problem

如果有大量 LCA queries，每次 O(n) DFS 会太慢。

例如：

n = 100000
queries = 100000

O(n) per query 无法接受。

Binary Lifting Idea

预处理 ancestors：

up[node][j] = node 的第 2^j 个 ancestor

然后每次 query 可以用 powers of two 向上跳。

Complexity

Preprocessing: O(n log n)
Query: O(log n)
Space: O(n log n)

👉 面试回答

对大量 LCA queries，我会使用 binary lifting。

先预处理每个 node 的 2^j-th ancestor。

查询时，先把较深的 node 提升到同一 depth，然后两个 nodes 一起向上跳，直到它们的 parent 相同。

预处理后每次 query 是 O(log n)。

1️⃣8️⃣ Binary Lifting Template

Code Skeleton

from collections import defaultdict

class LCA:
    def __init__(self, n, edges, root=0):
        self.LOG = 20
        self.graph = defaultdict(list)
        self.depth = [0] * n
        self.up = [[-1] * self.LOG for _ in range(n)]

        for u, v in edges:
            self.graph[u].append(v)
            self.graph[v].append(u)

        self.dfs(root, -1)

    def dfs(self, node, parent):
        self.up[node][0] = parent

        for j in range(1, self.LOG):
            if self.up[node][j - 1] != -1:
                self.up[node][j] = self.up[self.up[node][j - 1]][j - 1]

        for neighbor in self.graph[node]:
            if neighbor == parent:
                continue

            self.depth[neighbor] = self.depth[node] + 1
            self.dfs(neighbor, node)

    def query(self, a, b):
        if self.depth[a] < self.depth[b]:
            a, b = b, a

        diff = self.depth[a] - self.depth[b]

        for j in range(self.LOG):
            if diff & (1 << j):
                a = self.up[a][j]

        if a == b:
            return a

        for j in range(self.LOG - 1, -1, -1):
            if self.up[a][j] != self.up[b][j]:
                a = self.up[a][j]
                b = self.up[b][j]

        return self.up[a][0]

Note

对于更大的 n，可以使用：

LOG = n.bit_length()

不要 hardcode 20。

👉 面试回答

Binary lifting 会存每个 node 在 powers of two 距离上的 ancestors。

查询时，我先把较深的 node 提升到和较浅 node 同一 depth。

然后从大 jump 到小 jump，同时提升两个 nodes。

当它们的 parents 相同时，这个 parent 就是 LCA。

1️⃣9️⃣ Euler Tour + RMQ

Alternative for Many Queries

另一种高级 LCA 方法是：

Euler Tour + Range Minimum Query

Idea

做 DFS Euler tour。

记录：

node visit order
depth of each visit
first occurrence of each node

然后 LCA 变成：

在 Euler tour 中，
p 和 q 第一次出现位置之间，
depth 最小的 node

Complexity

如果配合 Sparse Table：

Preprocessing: O(n log n)
Query: O(1)

👉 面试回答

Euler Tour + RMQ 也是处理大量 LCA queries 的方法。

DFS 时记录 Euler traversal 和每次访问的 depth。

两个 nodes 的 LCA，就是 Euler tour 中它们第一次出现位置之间 depth 最小的 node。

配合 Sparse Table 后， query 可以做到 O(1)。

2️⃣0️⃣ LCA for Path Queries

Common Extension

一旦能求 LCA，就可以回答 tree path 相关问题。

Examples:

distance between two nodes
sum of values on path
min edge on path
max edge on path
ancestor check

Common Formula

对于 distance：

dist(u, v) = depth[u] + depth[v] - 2 * depth[lca(u, v)]

With Prefix Sum on Tree

如果每个 node 有 value， path sum 可以是：

prefix[u] + prefix[v] - 2 * prefix[lca] + value[lca]

👉 面试回答

LCA 经常是 tree path queries 的基础。

一旦知道 lowest common ancestor， u 到 v 的路径就可以拆成 u 到 LCA 和 LCA 到 v 两段。

这样可以计算 distance、path sum，或其他 path aggregation。

2️⃣1️⃣ 常见 Edge Cases

One Node Is Ancestor of the Other

p is ancestor of q

那么：

LCA = p

p Equals q

如果：

p == q

那么：

LCA = p

Empty Tree

root = None

None

One or Both Nodes Missing

如果题目不保证存在，需要 special handling。

Duplicate Values

应该比较 node reference，而不是只比较 value，除非题目只给 values。

Skewed Tree

Recursive stack 可能变成 O(n)。

👉 面试回答

LCA 常见 edge cases 包括：一个 node 是另一个 node 的 ancestor、 p 和 q 是同一个 node、 empty tree、 nodes 可能 missing、 duplicate values，以及 skewed tree。

在大多数 binary tree LCA problems 中，我比较的是 node references，不是单纯比较 values。

2️⃣2️⃣ 常见错误

Mistake 1: General Binary Tree 中使用 BST Logic

BST value comparison 只适用于 BST。

Mistake 2: 过早返回 Root

在 general binary tree 中，只有当：

root == p or root == q

才直接返回 root。

否则必须检查左右 subtrees。

Mistake 3: 忽略 Missing Nodes

标准 LCA 假设两个 nodes 都存在。

如果题目不保证，必须验证两者都被找到。

Mistake 4: 比较 Values 而不是 Nodes

如果有 duplicate values，这个是错的：

root.val == p.val

更安全：

root == p

Mistake 5: Parent Pointer 中没有处理 Null

Parent pointer solution 要处理 root parent 为 null 的情况。

Mistake 6: Binary Lifting LOG 太小

如果 LOG 太小， ancestor jumps 可能失败。

使用：

LOG = n.bit_length()

👉 面试回答

LCA 常见错误包括：把 BST logic 用在 general binary tree 上、忽略 nodes 可能 missing 的情况、比较 node values 而不是 node references、 parent pointer 中没有处理 null、以及 binary lifting 中 LOG 设置太小。

2️⃣3️⃣ 什么时候 LCA 适用？

Good Fit

当题目问：

lowest common ancestor
common ancestor
distance between two tree nodes
path between two nodes
relationship between two nodes
tree path query
ancestor check
deepest leaves ancestor

Problem Signals

看到这些关键词想到 LCA：

ancestor
common ancestor
lowest
path between nodes
distance in tree
parent pointer
rooted tree
subtree contains both

👉 面试回答

当问题问 tree 中两个 nodes 之间的关系时，我会考虑 LCA。

常见信号包括 common ancestor、 path between two nodes、 distance in a tree，以及 ancestor-descendant relationship。

然后根据 tree 是 binary tree、BST、 parent-pointer tree，还是 many-query tree，选择不同方法。

2️⃣4️⃣ 什么时候 LCA 不适用？

Not Good Fit

LCA 不一定适合：

graph is not a tree
graph has cycles
need shortest path in weighted graph
need connected components only
need topological ordering
need dynamic tree updates

Better Alternatives

Problem Type	Better Pattern
General graph shortest path	BFS / Dijkstra
Graph with cycles	Graph DFS with visited
Dependency order	Topological Sort
Dynamic connectivity	Union Find
Dynamic tree path queries	Heavy-Light Decomposition
Subtree range query	Euler Tour + Segment Tree

👉 面试回答

LCA 是 tree-specific concept。

如果结构是 general graph with cycles，除非先把 graph rooted 成 tree，否则 LCA 通常没有明确定义。

如果问题涉及 weighted shortest path、dependency ordering，或 dynamic updates，其他算法可能更合适。

2️⃣5️⃣ 标准模板

Binary Tree LCA Template

def lowest_common_ancestor(root, p, q):
    if not root or root == p or root == q:
        return root

    left = lowest_common_ancestor(root.left, p, q)
    right = lowest_common_ancestor(root.right, p, q)

    if left and right:
        return root

    return left if left else right

BST LCA Template

def lowest_common_ancestor_bst(root, p, q):
    current = root

    while current:
        if p.val < current.val and q.val < current.val:
            current = current.left
        elif p.val > current.val and q.val > current.val:
            current = current.right
        else:
            return current

    return None

Parent Pointer LCA Template

def lowest_common_ancestor_parent(p, q):
    ancestors = set()

    while p:
        ancestors.add(p)
        p = p.parent

    while q:
        if q in ancestors:
            return q

        q = q.parent

    return None

Parent Pointer Two-Pointer Template

def lowest_common_ancestor_parent(p, q):
    a = p
    b = q

    while a != b:
        a = a.parent if a else q
        b = b.parent if b else p

    return a

Binary Lifting Query Template

def query_lca(a, b):
    if depth[a] < depth[b]:
        a, b = b, a

    diff = depth[a] - depth[b]

    for j in range(LOG):
        if diff & (1 << j):
            a = up[a][j]

    if a == b:
        return a

    for j in range(LOG - 1, -1, -1):
        if up[a][j] != up[b][j]:
            a = up[a][j]
            b = up[b][j]

    return up[a][0]

🧠 Staff-Level Answer Final

👉 面试回答完整版本

Lowest Common Ancestor 是 tree 中最低的一个 node，它的 subtree 同时包含两个 target nodes。

一个 node 可以是自己的 ancestor，所以如果一个 target node 是另一个 target node 的 ancestor，那么这个 node 本身就是 LCA。

对 general binary tree，我通常使用 postorder recursion。每个 recursive call 会搜索当前 subtree，并返回四种含义之一：找到 p，找到 q，找到 LCA，或什么都没找到。

对每个 node，我递归搜索 left 和 right subtrees。如果左右两边都返回 non-null，说明 p 和 q 分别在两个 branches 中， current node 就是 LCA。如果只有一边返回 non-null，就把那一边的结果向上传递。如果 current node 本身是 p 或 q，就返回 current node。

这个 binary tree solution 是 O(n) time，因为最坏情况要访问所有 nodes。 Space 是 O(h)，来自 recursion stack。

对 binary search tree，我使用 BST ordering property。如果 p 和 q 都小于 current node，就往 left 走。如果都大于 current node，就往 right 走。否则， current node 是 split point，因此就是 LCA。这个方法是 O(h) time， iterative version 是 O(1) space。

如果 nodes 有 parent pointers，可以从 nodes 向上走。一个方法是把一个 node 的所有 ancestors 存进 set，然后从另一个 node 向上找第一个 common ancestor。另一个方法是 two-pointer，类似 linked list intersection。

如果题目不保证两个 nodes 都存在，标准 LCA solution 不够。我还要追踪 p 和 q 是否真的被找到。只有两个都存在时，才返回 LCA。

对大量 static tree 上的 LCA queries，我会使用 binary lifting。它预处理每个 node 的 2^j-th ancestor。然后每次 query 可以 O(log n) 回答。

高级工程师解释 LCA 时，我会讲清楚： tree type 是什么， p 和 q 是否 guaranteed exist，是否有 parent pointers，是一次 query 还是 many queries， node values 是否 unique，以及为什么选择的方法符合这些 constraints。

⭐ Final Insight

LCA 的核心不是“背一个递归模板”。

它的核心是判断 tree model 和 query model：

general binary tree 用 postorder DFS， BST 用 value split point， parent pointer tree 可以向上走， nodes may be missing 时要验证存在性， many queries 时用 binary lifting 或 Euler Tour + RMQ。

Senior-level 的重点是：

当前 node 返回什么信息， p 和 q 是否 guaranteed exist，比较 node reference 还是 value，一个 node 是另一个 node ancestor 时如何处理，为什么 BST 可以只走一边，为什么 general binary tree 必须看左右子树，以及 repeated queries 为什么需要 preprocessing。

能讲清楚这些， LCA 就是一类处理 tree relationship、ancestor、path query 和 distance query 的核心模式。

🎯 LCA

1️⃣ Core Framework

2️⃣ What Problem Are We Solving?

3️⃣ Basic Example

Tree

Another Example

4️⃣ LCA in General Binary Tree

Key Idea

Why This Works

5️⃣ LCA Binary Tree Code

Code

Complexity

6️⃣ Why Postorder Traversal?

Children Before Parent

Return Meaning

7️⃣ LCA in Binary Search Tree

BST Property

Key Insight

8️⃣ LCA BST Code

Recursive Code

Iterative Code

Complexity

9️⃣ Binary Tree LCA vs BST LCA

General Binary Tree

Binary Search Tree

Comparison

🔟 LCA With Parent Pointers

Problem

Idea 1: Ancestor Set

Code

1️⃣1️⃣ Parent Pointer Two-Pointer Method

Similar to Linked List Intersection

Code

Why It Works

1️⃣2️⃣ LCA When Nodes May Not Exist

Problem

Safer Approach

Code

1️⃣3️⃣ LCA of Multiple Nodes

Problem

Idea

Code

1️⃣4️⃣ LCA of Deepest Leaves

Problem

Key Idea

Code

1️⃣5️⃣ Distance Between Two Nodes

Problem

Idea

Code

1️⃣6️⃣ LCA in N-ary Tree

Problem

Idea

Code

1️⃣7️⃣ Binary Lifting for Repeated LCA Queries

Problem

Binary Lifting Idea

Complexity

1️⃣8️⃣ Binary Lifting Template

Code Skeleton

Note

1️⃣9️⃣ Euler Tour + RMQ

Alternative for Many Queries

Idea

Complexity

2️⃣0️⃣ LCA for Path Queries

Common Extension

Common Formula

With Prefix Sum on Tree

2️⃣1️⃣ Common Edge Cases

One Node Is Ancestor of the Other

p Equals q

Empty Tree

One or Both Nodes Missing

Duplicate Values

Skewed Tree

2️⃣2️⃣ Common Mistakes

Mistake 1: Using BST Logic on General Binary Tree

Mistake 2: Returning Root Too Early

Mistake 3: Ignoring Missing Nodes