Overview

Given a binary search tree (BST) and two node values p and q, find the lowest common ancestor (LCA) of the two nodes.

The LCA is the deepest node that is an ancestor of both p and q (a node can be an ancestor of itself).

Implement lowestCommonAncestor(root, p, q) that returns the value of the LCA node.

Constraints

• Both p and q are guaranteed to exist in the tree.
• All node values are unique.
• p !== q.
• Tree nodes have shape { val, left, right }.
• Leverage the BST property for $O(H)$ time where H is tree height.

Examples

//       6
//      / \\
//     2   8
//    / \\ / \\
//   0  4 7  9
//     / \\
//    3   5

lowestCommonAncestor(root, 2, 8);  // 6
lowestCommonAncestor(root, 2, 4);  // 2 — a node is its own ancestor
lowestCommonAncestor(root, 3, 5);  // 4

Notes

• BST property: all left descendants < node < all right descendants.
• If both p and q are less than the current node, the LCA is in the left subtree.
• If both are greater, it's in the right subtree.
• Otherwise, the current node is the LCA (the split point).
• This can be solved iteratively without recursion.

Solution

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

Resources

• Lowest Common Ancestor of a BST — LeetCode
• Lowest Common Ancestor — Wikipedia