Coding problem · Medium · Trees

Lowest Common Ancestor of a BST

Medium Algorithms & data structures Seen at Meta, Amazon, LinkedIn

Given a binary search tree root and two values p and q that both exist in it, return the value of their lowest common ancestor — the deepest node that has both as descendants (a node is a descendant of itself).

Example 1

Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
Output: 6

Example 2

Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
Output: 2

Hints

Hint 1

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

Hint 2

Otherwise the paths split here — this node is the answer.

Write and run your solution

Loading the editor… (JavaScript is required to run code in your browser.)

Solution and explanation

Show the solution

Time O(h) · Space O(1)

Walk down from the root using the BST ordering: while both targets are on the same side, move to that child. The first node where they split (or that equals one target) is the LCA. No recursion or extra memory needed.

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

function lowestCommonAncestor(root: TreeNode | null, p: number, q: number): number {
  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;
}

def lowest_common_ancestor(root: Optional[TreeNode], p: int, q: int) -> int:
    node = root
    while node:
        if p < node.val and q < node.val:
            node = node.left
        elif p > node.val and q > node.val:
            node = node.right
        else:
            return node.val
    return -1

<?php

function lowestCommonAncestor(?TreeNode $root, int $p, int $q): int
{
    $node = $root;
    while ($node !== null) {
        if ($p < $node->val && $q < $node->val) {
            $node = $node->left;
        } elseif ($p > $node->val && $q > $node->val) {
            $node = $node->right;
        } else {
            return $node->val;
        }
    }
    return -1;
}

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

Follow-up questions

LCA in a general binary tree (no ordering) — recursive search returning found nodes.

Maximum Depth of Binary Tree · Easy
Invert Binary Tree · Easy
Binary Tree Level Order Traversal · Medium
Validate Binary Search Tree · Medium