lca-bst.ts

import { TreeNode } from "../lib/tree-node.js";

/**
 * 235. Lowest Common Ancestor of a Binary Search Tree  (Medium)
 * Link: https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree/
 *
 * Given a BST and two nodes p and q present in it, return their lowest common
 * ancestor (a node is allowed to be a descendant of itself).
 *
 * Example:
 *   Input:  root = [6,2,8,0,4,7,9], p = 2, q = 8
 *   Output: 6
 *
 * Approach:
 *   Exploit the BST ordering. Starting at the root: if both values are smaller,
 *   the LCA is in the left subtree; if both are larger, it is in the right.
 *   Otherwise the values split (or one equals the node), so the current node is
 *   the lowest common ancestor.
 *
 * Time:  O(h)
 * Space: O(1)
 */
export function lowestCommonAncestor(
  root: TreeNode | null,
  p: number,
  q: number,
): TreeNode | null {
  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;
    }
  }

  return null;
}