Lowest common ancestor in a BST

Medium TimeO(h) SpaceO(h)

The lowest common ancestor of two nodes is the deepest node with both of them somewhere below it, where a node counts as its own descendant — so one value may be the ancestor of the other. Given a binary search tree obeying its ordering, and two values p and q that are both present in it, return their lowest common ancestor.

Examples

Example 1

Input
node = buildTree()p = 1q = 3
Output
2
1 and 3 are the two children of 2, so 2 is the deepest node with both below it.

Example 2

Input
node = buildTree()p = 2q = 3
Output
2
3 is below 2, and a node counts as its own descendant — so the answer is 2 itself.

The Code

function buildTree() {
  return {
    val: 4,
    left: { val: 2, left: { val: 1, left: null, right: null }, right: { val: 3, left: null, right: null } },
    right: { val: 7, left: { val: 6, left: null, right: null }, right: { val: 9, left: null, right: null } }
  };
}
function lowestCommonAncestor(node, p, q) {
  if (node === null) return null;
  if (p < node.val && q < node.val) return lowestCommonAncestor(node.left, p, q);
  if (p > node.val && q > node.val) return lowestCommonAncestor(node.right, p, q);
  return node.val;
}
lowestCommonAncestor(buildTree(), 1, 3);
Done
Step through lowestCommonAncestor(buildTree(), 1, 3) call by call

More like this

All binary trees examples (9) →