IntermediateTrees

Lowest Common Ancestor

Find the lowest common ancestor in binary trees and BSTs; use binary lifting on rooted graphs

Time: O(h)–O(log n)
Space: O(1)–O(n)
Pattern Overview

Core Idea

Converge two nodes upward to the deepest shared ancestor using structure-specific methods.

When to Use

Use to answer ancestry queries efficiently over static trees.

General Recognition Cues
General indicators that this pattern might be applicable
  • Two nodes' ancestor
  • BST or general tree
  • Preprocess for many queries
Pattern Variants & Approaches
Different methodologies and implementations for this pattern
1

Binary Tree LCA

Return node when diverging between left/right

When to Use This Variant
  • General tree
Use Case
Single queries
Advantages
  • O(n) DFS or O(h) if parent pointers
Implementation
def lca(root, p, q):
    if not root or root == p or root == q: return root
    L = lca(root.left, p, q)
    R = lca(root.right, p, q)
    return root if L and R else (L or R)
2

BST LCA

Use BST ordering to descend

When to Use This Variant
  • Compare to root
Use Case
BST only
Advantages
  • O(h)
  • Simple
Implementation
def lca_bst(root, p, q):
    while root:
        if p.val < root.val and q.val < root.val: root = root.left
        elif p.val > root.val and q.val > root.val: root = root.right
        else: return root
3

Binary Lifting

Jump powers of two after depth aligning

When to Use This Variant
  • Multiple queries
Use Case
Static tree
Advantages
  • O(n log n) preprocess, O(log n) query
Implementation
# Binary Lifting: preprocess up table and depth, then lift nodes
LOG = 17  # ~ for n up to 1e5, set appropriately
def build_lifting(n, adj, root=0):
    up = [[-1]*n for _ in range(LOG)]
    depth = [0]*n
    def dfs(u, p):
        up[0][u] = p
        for v in adj[u]:
            if v == p: continue
            depth[v] = depth[u] + 1
            dfs(v, u)
    dfs(root, -1)
    for j in range(1, LOG):
        for v in range(n):
            if up[j-1][v] != -1:
                up[j][v] = up[j-1][ up[j-1][v] ]
    return up, depth
def lca_lift(a, b, up, depth):
    if depth[a] < depth[b]: a, b = b, a
    # lift a
    diff = depth[a] - depth[b]
    i = 0
    while diff:
        if diff & 1: a = up[i][a]
        diff >>= 1; i += 1
    if a == b: return a
    for i in range(LOG-1, -1, -1):
        if up[i][a] != up[i][b]: a = up[i][a]; b = up[i][b]
    return up[0][a]
Common Pitfalls
Watch out for these common mistakes
  • Not handling one node as ancestor
  • Mismatched depths
  • Preprocessing mistakes
Code Templates
Compare implementations across different languages
def template(*args, **kwargs):
    # General template placeholder
    pass
Example Problems
Classic LeetCode problems using this pattern
Complexity Analysis
Time Complexity
O(h)–O(log n)

Depends on preprocessing.

Space Complexity
O(1)–O(n)

Binary lifting stores jump table.

Ready to test your knowledge?

Test your pattern recognition with interactive questions