Find the lowest common ancestor in binary trees and BSTs; use binary lifting on rooted graphs
Converge two nodes upward to the deepest shared ancestor using structure-specific methods.
Use to answer ancestry queries efficiently over static trees.
Binary-tree LCA via divide-and-conquer, BST LCA by ordering, and binary lifting for many queries after preprocessing.
# Lowest Common Ancestor Templates
def lca_binary_tree(root, p, q):
if not root or root==p or root==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
return left or right
def lca_bst(root, p, q):
cur=root
while cur:
if p.val < cur.val and q.val < cur.val: cur=cur.left
elif p.val > cur.val and q.val > cur.val: cur=cur.right
else: return curReturn node when diverging between left/right
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)Use BST ordering to descend
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 rootJump powers of two after depth aligning
# 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]Depends on preprocessing.
Binary lifting stores jump table.