Binary Search Tree Lowest Common Ancestor

Given a binary search tree and two values a and b that both appear in it, find their lowest common ancestor — the deepest node that has both a and b somewhere beneath it (a node counts as a descendant of itself). Think of a company org chart sorted by employee ID: the lowest common ancestor of two people is the most junior manager whose reporting chain still contains both of them. You return that node's value.

A binary search tree keeps every value to the left of a node smaller than the node, and every value to the right larger. You will use that ordering to walk straight to the answer without exploring the whole tree.

Signature

// Each node is a plain object. Leaves have left === null and right === null.
type TreeNode = { val: number; left: TreeNode | null; right: TreeNode | null };

// root is never null; a and b are distinct values, both present in the tree.
// Returns the VALUE (a number) of the lowest common ancestor node.
function binarySearchTreeLowestCommonAncestor(
  root: TreeNode,
  a: number,
  b: number,
): number;

Examples

Consider this tree:

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

// a and b sit on opposite sides of the root — 6 is the split point.
binarySearchTreeLowestCommonAncestor(root, 2, 8); // -> 6

// 2 is an ancestor of 4, so the answer is 2 itself.
// Both values live in the left subtree; the walk turns left, then stops at 2.
binarySearchTreeLowestCommonAncestor(root, 2, 4); // -> 2

Notes

• Valid BST — left subtree values are all smaller than the node, right subtree values all larger. You may rely on this ordering; you do not need to validate it.
• Both present — a and b are guaranteed to exist in the tree, so you never have to handle a missing value.
• A node is its own ancestor — if a is an ancestor of b, the lowest common ancestor can be a itself.
• Order does not matter — calling with (root, a, b) and (root, b, a) returns the same value.
• Return the value — return the LCA node's val (a number), not the node object.