Lowest Common Ancestor of a BST

Medium

Problem

Given a BST and two nodes p and q in it, return their lowest common ancestor (a node counts as its own descendant). Use the BST ordering instead of searching the whole tree.

Example 1

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

Example 2

Input:  same tree, p = 2, q = 4
Output: 2

Test cases

Case 1

Input:    [6,2,8,0,4,7,9,null,null,3,5], 2, 8
Expected: 6

Case 2

Input:    [6,2,8,0,4,7,9,null,null,3,5], 2, 4
Expected: 2

Case 3

Input:    [2,1], 2, 1
Expected: 2

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution1 approach

1. Walk down using ordering

Time O(h)Space O(1)

Both values smaller → go left; both larger → go right; otherwise this node splits them and is the LCA.

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