Lowest Common Ancestor in a BST

Find the lowest node whose subtree contains both target nodes.

Start with the concrete trace below. It shows the state the algorithm must carry as it runs.

Problem trace

Lowest Common Ancestor in a BST: BST ordering discards one whole side until the targets split at their lowest shared ancestor.

Input and goalFind the lowest node whose subtree contains both target nodes.

Start at root 6Both targets are smaller: 3 < 6 and 5 < 6. The first branch moves root to 6.left at node 2.

6root=6/\28/\/\0479/\3first=35second=5

inputfirst=3, second=5currentRootroot=6targetsfirst=3, second=5decisionboth smaller -> move left to 2

Recognize it

Both target nodes are in a BST, so comparing both values with the current root reveals whether their lowest common ancestor must be entirely left, entirely right, or current.

Keep true

At the start of every loop iteration, the current root’s subtree contains both targets; moving only when both values are on the same side preserves that fact.

Reuse it

In an ordered search tree, track where multiple target values fall relative to the current separator; the first separator they do not share is their lowest common routing point.

Pattern: Use BST ordering to choose one branch.

Simple idea: If both targets are smaller, go left. If both are larger, go right. When they split across the current value, the current node is their lowest common ancestor.

def lowest_common_ancestor_bst(
   root: TreeNode, first: TreeNode, second: TreeNode
) -> TreeNode:
   while True:
      if first.val < root.val and second.val < root.val:
         root = root.left
      elif first.val > root.val and second.val > root.val:
         root = root.right
      else:
         return root

Cost: $O(h)$ time and $O(1)$ space.

The platform supplies TreeNode with val, left, and right; this snippet assumes that definition.