44. Lowest Common Ancestor of a BST

MediumTree BST Binary Search

You are given the root of a binary search tree with distinct values, and two different values p and q that both occur in the tree. Return the value of their lowest common ancestor (LCA): the deepest node that has both p and q in its subtree.

A node counts as a descendant of itself, so if p sits above q then p is the answer.

Adapted for this site: the classic version passes node references and returns a node. Here p and q are the values of the two nodes, and you return the LCA's value as an integer.

Example 1

Input: root = [20,10,30,5,15,25,35,null,null,12,18], p = 5, q = 18
Output: 10

Explanation: 5 is in the left subtree of 10 and 18 is in its right subtree, so 10 is the deepest node above both.

Example 2

Input: root = [20,10,30,5,15,25,35,null,null,12,18], p = 12, q = 35
Output: 20

Example 3

Input: root = [20,10,30,5,15,25,35,null,null,12,18], p = 15, q = 12
Output: 15

Explanation: 12 is a child of 15, and a node is its own ancestor.

Constraints

The number of nodes is in the range [2, 10^5]
-2^31 <= Node.val <= 2^31 - 1
All values are distinct
p != q, and both values exist in the tree

💡 Hint 1

In a general binary tree you would have to search both subtrees. What does the BST ordering tell you about where p and q are?

💡 Hint 2

If both values are smaller than the current node, the LCA is in the left subtree; if both are larger, it is in the right subtree.

💡 Hint 3

The first node where p and q fall on different sides (or one of them equals the node) is the answer. No recursion is needed.

Try it yourself first ✎

Solutions stick better after a real attempt. Peek when you're ready.

Approach

Use the BST ordering to walk down a single path from the root. If both p and q are smaller than the current value, the LCA must be in the left subtree; if both are larger, it is in the right subtree. Otherwise the two values split here (or one of them is this node), so this node is the lowest one above both. Return its value.

Time O(h), where h is the tree heightSpace O(1)

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 null;
}

class Solution {
    public int lowestCommonAncestor(TreeNode root, int p, int q) {
        TreeNode node = root;
        while (node != null) {
            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;
    }
}

/**
 * Definition for a binary tree node (provided):
 * function TreeNode(val, left, right) { this.val = val ?? 0; this.left = left ?? null; this.right = right ?? null; }
 *
 * @param {TreeNode} root
 * @param {number} p
 * @param {number} q
 * @return {number} the value of the lowest common ancestor
 */
function lowestCommonAncestor(root, p, q) {

}

Ctrl/⌘ + ' run · Ctrl/⌘ + Enter submit