Typorithm · medium

Lowest Common Ancestor (BST)

lowest-common-ancestor-bsttreesbstnavigationsplit-point

Saved on this device

Full lesson · 8 learning steps Open any exercise for focused practice

Step 1 of 8 · intro card

Learn Lowest Common Ancestor (BST)

Trees

Walk down the BST; the first node where the two targets diverge (one each side, or one equals it) is the LCA.

In a BST, the lowest common ancestor is the node where the search paths to the two targets split.

If both targets are smaller, go left; if both are larger, go right.

The moment they no longer agree on direction, the current node is the answer.

Both smaller → go left.

Both larger → go right.

Otherwise the split node is the LCA.

function lowestCommonAncestor(root, p, q) {
  let node = root;
  while (node !== null) {
    if (p.val < node.val && q.val < node.val) {
      node = node.left;
    } else if (p.val > node.val && q.val > node.val) {
      node = node.right;
    } else {
      return node;
    }
  }
  return null;
}

Read the implementation

Connect each part of the code to the concept before you type.

1. Walk from root

Descend the BST without recursion.

let node = root

2. Both smaller

If both targets are smaller, the LCA is in the left subtree.

if (p.val < node.val && q.val < node.val)

3. Both larger

If both are larger, go right.

else if (p.val > node.val && q.val > node.val)

4. Split point

The first node that splits the two targets is their LCA.

return node

A complete learning loop

Understand

Read the concept map and follow the code breakdown.

Reconstruct

Type the implementation, repair mistakes and work through every recall exercise.

Verify

Use the final check without hints; revisit weak concepts in short practice sessions.