Lowest Common Ancestor and Binary Lifting

This is an extension topic beyond most interviews: a single LCA in a binary tree is standard interview material, while binary lifting pays off when you must answer many ancestor, LCA or distance queries on the same tree.

Intuition

The lowest common ancestor (LCA) of u and v in a rooted tree is the deepest vertex that is an ancestor of both (a vertex counts as its own ancestor). Every tree path u -> v goes up from u to lca(u, v) and then down to v, so

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

and many path questions reduce to LCA plus prefix information from the root.

Three levels of solutions:

• One query, binary tree. Recurse: if the current node is p or q, return it; if p and q come back from different subtrees, the current node is the LCA. O(n) per query.
• Climbing. Lift the deeper vertex until both have equal depth, then lift both together until they meet. O(depth) per query, fine for one query, too slow for 10^5 queries on a path-shaped tree.
• Binary lifting. Precompute up[j][v], the 2^j-th ancestor of v. Any upward move of k steps is a sum of powers of two (the bits of k), so it takes O(log n) jumps. For the LCA, equalize depths, then try jumps from the largest power down, taking a jump only if it keeps the two vertices apart. They end just below the LCA.

When to use it in interviews / OAs

• "Lowest common ancestor of a binary tree / BST / nodes with parent pointers": single-query techniques.
• "Kth ancestor of a tree node" with many queries: binary lifting.
• Many distance queries, or "how many operations to make all edge weights on the path equal" (path statistics from root prefix counts minus twice the LCA's).
• Path minimum or maximum edge weight for many queries: lift a second table alongside up.

Template

One query in a binary tree

from dataclasses import dataclass


@dataclass(eq=False)
class TreeNode:
    val: int
    left: "TreeNode | None" = None
    right: "TreeNode | None" = None
    parent: "TreeNode | None" = None


def lca_binary_tree(root: TreeNode | None, p: TreeNode, q: TreeNode) -> TreeNode | None:
    # assumes both p and q are in the tree
    if root is None or root is p or root is q:
        return root
    left = lca_binary_tree(root.left, p, q)
    right = lca_binary_tree(root.right, p, q)
    if left and right:
        return root  # p and q sit in different subtrees
    return left or right


def lca_with_parents(p: TreeNode, q: TreeNode) -> TreeNode:
    # like the intersection of two linked lists: both pointers walk depth(p) + depth(q) steps
    a, b = p, q
    while a is not b:
        a = a.parent if a else q
        b = b.parent if b else p
    return a

In a BST you can do even less: walk from the root and go left while both values are smaller, right while both are larger; the first split point is the LCA.

Binary lifting

class BinaryLifting:
    def __init__(self, n: int, edges: list[tuple[int, int]], root: int = 0):
        adj: list[list[int]] = [[] for _ in range(n)]
        for u, v in edges:
            adj[u].append(v)
            adj[v].append(u)
        self.depth = [0] * n
        parent = [root] * n  # the root is its own parent, so jumps clamp there
        seen = [False] * n
        seen[root] = True
        stack = [root]
        while stack:
            u = stack.pop()
            for v in adj[u]:
                if not seen[v]:
                    seen[v] = True
                    parent[v] = u
                    self.depth[v] = self.depth[u] + 1
                    stack.append(v)
        self.LOG = max(1, n.bit_length())
        self.up = [parent]  # up[j][v] = 2**j-th ancestor of v
        for _ in range(1, self.LOG):
            prev = self.up[-1]
            self.up.append([prev[prev[v]] for v in range(n)])

    def kth_ancestor(self, v: int, k: int) -> int:
        if k > self.depth[v]:
            return -1
        j = 0
        while k:
            if k & 1:  # take the jumps that match the set bits of k
                v = self.up[j][v]
            k >>= 1
            j += 1
        return v

    def lca(self, u: int, v: int) -> int:
        if self.depth[u] < self.depth[v]:
            u, v = v, u
        u = self.kth_ancestor(u, self.depth[u] - self.depth[v])  # equal depths now
        if u == v:
            return u
        for j in range(self.LOG - 1, -1, -1):
            if self.up[j][u] != self.up[j][v]:  # jump only if we stay below the LCA
                u, v = self.up[j][u], self.up[j][v]
        return self.up[0][u]

    def dist(self, u: int, v: int) -> int:
        return self.depth[u] + self.depth[v] - 2 * self.depth[self.lca(u, v)]

Complexity

• Recursive binary-tree LCA: O(n) time, O(h) stack.
• Parent-pointer LCA: O(depth(p) + depth(q)), O(1) memory.
• Binary lifting: O(n log n) time and memory to build; O(log n) per k-th ancestor, LCA or distance query.

Common pitfalls

• Assuming both nodes exist. The recursive version returns p even when q is missing from the tree. If that can happen, count how many targets were found.
• Comparing by value instead of identity when node values repeat; compare node objects (is).
• Root handling. Make the root its own parent (or use -1 and guard every jump); otherwise jumps past the root index garbage.
• Too few levels. LOG must satisfy 2^LOG > max depth; n.bit_length() is enough.
• Jumping in the wrong order. Equalize depths first, then go from the largest power down; going small to large skips past the answer.
• Deep recursion in Python for skewed trees: build depths and parents iteratively as above.

Interview variations

• Kth ancestor of a tree node. kth_ancestor; with a parent array as input, skip the traversal and compute depths by memoized climbing.
• Distance between two nodes / nodes at distance k. dist(u, v) for many queries; a single query is easier with BFS after adding parent pointers.
• LCA of the deepest leaves. One post-order pass returning (depth, lca) pairs; no lifting needed.
• Path aggregates. Store prefix counts from the root (for example, how many edges of each weight); the count on path u-v is cnt[u] + cnt[v] - 2 * cnt[lca].
• Path maximum edge. Keep mx[j][v] = maximum edge on the 2^j jump; combine while lifting. Useful for "minimum bottleneck between two cities" on an MST.
• Other methods. Offline LCA with union-find (Tarjan), or Euler tour plus a sparse table for O(1) queries; good to name, rarely needed.