Lowest Common Ancestor

The Idea

The lowest common ancestor of two nodes is the deepest node that still has both below it. In a BST you never really search: start at the root and keep stepping while both targets lie the same way. The node where they split is the answer.

Real-World Example

Two walkers heading for different waymarked huts from the same trailhead. They stay together while every signpost points both destinations down the same path. The first signpost that sends them apart is the last place they were still travelling together.

The Code

class Node:
    def __init__(self, v, l=None, r=None): self.val, self.left, self.right = v, l, r

def lca(node, a, b):
    while node:
        if a < node.val and b < node.val:   node = node.left    # both smaller
        elif a > node.val and b > node.val: node = node.right   # both larger
        else: return node.val               # they split here, so this is the LCA
    return None

root = Node(6, Node(2, Node(0), Node(4)), Node(8, Node(7), Node(9)))
print(lca(root, 0, 4))   # 2
print(lca(root, 2, 8))   # 6 -> the paths split right at the root
print(lca(root, 7, 9))   # 8

class Node:
  def __init__(self, v, l=None, r=None): self.val, self.left, self.right = v, l, r

root = Node(6, Node(2, Node(0), Node(4)), Node(8, Node(7), Node(9)))
node, a, b = root, 0, 4
while node:
  if a < node.val and b < node.val: node = ___
  elif a > node.val and b > node.val: node = node.right
  else: break
print(node.val if node else None)   # should print 2