Lowest Common Ancestor: BST, Binary Tree & Binary Lifting

The Lowest Common Ancestor (LCA) of two nodes p and q in a tree is the deepest node that is an ancestor of both. It is one of the most frequently asked tree problems in interviews, and the techniques you learn here (recursive DFS, binary lifting) appear in many other tree problems.

What is LCA?

Given a tree and two nodes p and q, the LCA is the node n such that:

• n is an ancestor of both p and q
• No descendant of n is also an ancestor of both p and q

Special cases:

• A node can be its own ancestor — if p is an ancestor of q, then LCA(p, q) = p
• If both nodes are in the same subtree, the LCA is in that subtree
• If the nodes are in different subtrees of a node, that node is the LCA

LCA in a BST (the easy version)

In a BST, the structure gives us a shortcut. Starting from the root:

• If both p and q are smaller than the current node, the LCA is in the left subtree
• If both are larger, the LCA is in the right subtree
• Otherwise, the current node is the LCA (the paths to p and q diverge here)

def lca_bst(root, p, q):
    """Find LCA of nodes p and q in a BST.
    p and q are values (integers).
    """
    current = root
    while current:
        if p < current.val and q < current.val:
            current = current.left
        elif p > current.val and q > current.val:
            current = current.right
        else:
            return current
    return None

Time: O(h) where h is height. Space: O(1).

BST LCA walkthrough

BST:
        20
       /  \
      10   30
     / \   / \
    5  15 25  35

LCA(5, 15):
  5 < 20 and 15 < 20 → go left
  5 < 10 and 15 > 10 → diverge! LCA = 10 ✓

LCA(5, 35):
  5 < 20 and 35 > 20 → diverge! LCA = 20 ✓

LCA(25, 35):
  25 > 20 and 35 > 20 → go right
  25 < 30 and 35 > 30 → diverge! LCA = 30 ✓

LCA in a general binary tree (recursive DFS)

This is the classic approach. The idea: search for p and q in the left and right subtrees. If both are found (one on each side), the current node is the LCA.

def lca_binary_tree(root, p, q):
    """Find LCA of nodes p and q in a binary tree.
    p and q are TreeNode objects.
    """
    # Base case: reached null or found one of the targets
    if root is None or root == p or root == q:
        return root

    # Search in both subtrees
    left = lca_binary_tree(root.left, p, q)
    right = lca_binary_tree(root.right, p, q)

    # If both sides found something, current node is LCA
    if left and right:
        return root

    # Otherwise, return whichever side found something
    return left if left else right

Time: O(n) — visit every node once. Space: O(h) — recursion stack.

How does this work?

The function returns:

• None if neither p nor q is in this subtree
• p or q if one of them is found (it bubbles up)
• The LCA node when both subtrees return non-None

Find LCA(4, 5) in:
        1
       / \
      2   3
     / \
    4   5

Call lca(1, 4, 5):
  left = lca(2, 4, 5):
    left = lca(4, 4, 5): returns 4 (found p)
    right = lca(5, 4, 5): returns 5 (found q)
    Both non-None → return 2 (LCA!)
  right = lca(3, 4, 5): returns None
  left=2, right=None → return 2

Answer: Node 2

Edge case: one node is ancestor of the other

Find LCA(2, 4) in:
        1
       / \
      2   3
     /
    4

Call lca(1, 2, 4):
  left = lca(2, 2, 4): returns 2 (root == p, base case)
    (we never recurse further — 2 is returned immediately)
  right = lca(3, 2, 4): returns None
  left=2, right=None → return 2

Answer: Node 2 (which is p itself)

This works because when we find p, we return it immediately without checking if q is below. Since q must be somewhere in the tree, and it was not found in the right subtree, it must be under p.

LCA with parent pointers

If each node has a pointer to its parent, we can solve LCA by finding the intersection of the paths from each node to the root — similar to finding the intersection of two linked lists.

Approach 1: Using a set

def lca_with_parents_set(p, q):
    """Find LCA when nodes have parent pointers. Uses a set."""
    ancestors = set()

    # Walk p to root, recording all ancestors
    current = p
    while current:
        ancestors.add(current)
        current = current.parent

    # Walk q to root, first match is LCA
    current = q
    while current:
        if current in ancestors:
            return current
        current = current.parent

    return None

Time: O(h). Space: O(h) for the set.

Approach 2: Two-pointer (no extra space)

Equalize depths first, then walk up together:

def lca_with_parents_optimal(p, q):
    """Find LCA with parent pointers using O(1) space."""
    # Find depths
    def get_depth(node):
        depth = 0
        while node:
            depth += 1
            node = node.parent
        return depth

    depth_p = get_depth(p)
    depth_q = get_depth(q)

    # Move deeper node up to same level
    while depth_p > depth_q:
        p = p.parent
        depth_p -= 1
    while depth_q > depth_p:
        q = q.parent
        depth_q -= 1

    # Walk up together until they meet
    while p != q:
        p = p.parent
        q = q.parent

    return p

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

This is essentially the same algorithm as finding the intersection of two linked lists.

Binary lifting for O(log n) LCA queries

When you need to answer many LCA queries on the same tree, the approaches above are too slow (each query is O(n) or O(h)). Binary lifting preprocesses the tree in O(n log n) time and answers each query in O(log n).

The idea

For each node, precompute its ancestor at distance 1, 2, 4, 8, 16, … (powers of 2). To jump to any ancestor at distance d, decompose d into powers of 2 and jump.

import math

class BinaryLifting:
    def __init__(self, n, edges, root=0):
        """
        n: number of nodes (0-indexed)
        edges: list of (u, v) pairs
        root: root node
        """
        self.n = n
        self.LOG = max(1, int(math.log2(n)) + 1)

        # Build adjacency list
        self.adj = [[] for _ in range(n)]
        for u, v in edges:
            self.adj[u].append(v)
            self.adj[v].append(u)

        # up[k][v] = 2^k-th ancestor of v
        self.up = [[-1] * n for _ in range(self.LOG)]
        self.depth = [0] * n

        # BFS to fill depth and direct parents
        self._bfs(root)

        # Fill sparse table
        for k in range(1, self.LOG):
            for v in range(n):
                if self.up[k-1][v] != -1:
                    self.up[k][v] = self.up[k-1][self.up[k-1][v]]

    def _bfs(self, root):
        from collections import deque
        visited = [False] * self.n
        queue = deque([(root, -1, 0)])
        visited[root] = True

        while queue:
            node, parent, d = queue.popleft()
            self.up[0][node] = parent
            self.depth[node] = d
            for neighbor in self.adj[node]:
                if not visited[neighbor]:
                    visited[neighbor] = True
                    queue.append((neighbor, node, d + 1))

    def _lift(self, node, dist):
        """Move node up by dist levels."""
        for k in range(self.LOG):
            if dist & (1 << k):
                node = self.up[k][node]
                if node == -1:
                    return -1
        return node

    def lca(self, u, v):
        """Find LCA of nodes u and v in O(log n)."""
        # Ensure u is deeper
        if self.depth[u] < self.depth[v]:
            u, v = v, u

        # Lift u to same depth as v
        diff = self.depth[u] - self.depth[v]
        u = self._lift(u, diff)

        if u == v:
            return u

        # Binary lift both until they converge
        for k in range(self.LOG - 1, -1, -1):
            if self.up[k][u] != self.up[k][v]:
                u = self.up[k][u]
                v = self.up[k][v]

        return self.up[0][u]

Using binary lifting

# Tree:
#       0
#      / \
#     1   2
#    / \   \
#   3   4   5
#  /
# 6

edges = [(0,1), (0,2), (1,3), (1,4), (2,5), (3,6)]
bl = BinaryLifting(7, edges, root=0)

print(bl.lca(6, 4))  # 1 (parent of both subtrees)
print(bl.lca(6, 5))  # 0 (root, different sides)
print(bl.lca(3, 4))  # 1
print(bl.lca(6, 3))  # 3 (3 is ancestor of 6)

Preprocessing: O(n log n) time, O(n log n) space. Each query: O(log n) time.

Euler tour + RMQ approach (brief overview)

This is the fastest approach — O(n) preprocessing and O(1) per query. The idea:

1. Perform an Euler tour of the tree, recording node and depth at each step
2. For nodes u and v, the LCA is the node with minimum depth between their first occurrences in the Euler tour
3. This reduces LCA to a Range Minimum Query (RMQ) problem, solvable in O(1) with sparse tables

# Euler tour produces a sequence like:
# Nodes:  [0, 1, 3, 6, 3, 1, 4, 1, 0, 2, 5, 2, 0]
# Depths: [0, 1, 2, 3, 2, 1, 2, 1, 0, 1, 2, 1, 0]
#
# LCA(6, 4): first occurrence of 6 at index 3, first of 4 at index 6
# Minimum depth in range [3, 6] is depth 1 at index 5 → node 1
# LCA = 1 ✓

This approach is optimal but complex to implement. For most interview scenarios, the recursive DFS approach is sufficient.

Comparison of approaches

Approach	Preprocessing	Query Time	Space	Best For
Recursive DFS	None	O(n)	O(h)	Single query
BST property	None	O(h)	O(1)	BSTs only
Parent pointers	None	O(h)	O(1)	When parents available
Binary lifting	O(n log n)	O(log n)	O(n log n)	Many queries
Euler + RMQ	O(n)	O(1)	O(n)	Maximum performance

LCA variations

LCA of multiple nodes

The LCA of multiple nodes is the LCA of the two nodes with the minimum and maximum positions in an in-order traversal:

def lca_multiple(root, nodes):
    """Find LCA of a list of nodes."""
    if not nodes:
        return None
    result = nodes[0]
    for i in range(1, len(nodes)):
        result = lca_binary_tree(root, result, nodes[i])
    return result

Distance between two nodes

Once you have LCA, the distance between two nodes is:

def distance(root, p, q):
    """Find distance between nodes p and q."""
    lca_node = lca_binary_tree(root, p, q)
    d1 = depth_from(lca_node, p, 0)
    d2 = depth_from(lca_node, q, 0)
    return d1 + d2

def depth_from(root, target, depth):
    """Find depth of target from root."""
    if root is None:
        return -1
    if root == target:
        return depth
    left = depth_from(root.left, target, depth + 1)
    if left != -1:
        return left
    return depth_from(root.right, target, depth + 1)

LCA in a directed acyclic graph (DAG)

In a DAG, a node can have multiple parents. The LCA concept extends but becomes more complex — there may be multiple LCAs. This is beyond typical interview scope.

Practice problems

1. LCA of a BST (LeetCode 235) — Use the BST property
2. LCA of a Binary Tree (LeetCode 236) — Classic recursive DFS
3. LCA of Deepest Leaves (LeetCode 1123) — Combine depth + LCA
4. Distance Between Nodes — LCA + depth calculation
5. All Ancestors of a Node (LeetCode 2096) — Path to root
6. Kth Ancestor of a Node (LeetCode 1483) — Binary lifting
7. LCA of a Binary Tree II (LeetCode 1644) — Nodes might not exist
8. LCA of a Binary Tree III (LeetCode 1650) — With parent pointers

Key takeaways

• In a BST, LCA is found by tracking where paths diverge — O(h) time, O(1) space
• In a general binary tree, recursive DFS finds LCA in O(n) — the most important technique to master
• Parent pointers reduce LCA to a linked list intersection problem
• Binary lifting trades O(n log n) preprocessing for O(log n) per query — essential for competitive programming
• The recursive DFS approach handles edge cases naturally (node as its own ancestor)