← Tree Traversal

Micro-Drill #212 — Lowest common ancestor (BST)

Tree Traversal Target: 10s

BST property: if both targets < root go left, both > root go right, otherwise root is LCA. O(h) time.

def lowestCommonAncestor(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

Type it from memory. Go.

Practice Problems

• 235. Lowest Common Ancestor of a BST

Related Coding Drills

• Drill #89 — Lowest common ancestor Medium
• Drill #34 — BST insert Easy
• Drill #35 — BST search Easy