← Tree Traversal

Micro-Drill #213 — Lowest common ancestor (binary tree)

Tree Traversal Target: 10s

If both sides return non-null, current node is LCA. Otherwise, LCA is on the non-null side. O(n) time.

def lowestCommonAncestor(root, p, q):
    if not root or root == p or root == q:
        return root
    left = lowestCommonAncestor(root.left, p, q)
    right = lowestCommonAncestor(root.right, p, q)
    if left and right: return root  # split point = LCA
    return left or right

Type it from memory. Go.

Practice Problems

• 236. Lowest Common Ancestor of a Binary Tree

Related Coding Drills

• Drill #89 — Lowest common ancestor Medium
• Drill #90 — Diameter of binary tree Easy
• Drill #36 — Height of a binary tree Easy