Skip to content
Shubham JangleResources
Trees

Explore topics

Lowest Common Ancestor of BST

Watch the walkthrough
Open on Instagram

Problem

Given a binary search tree and two existing nodes p and q, return their lowest common ancestor.

Approach and revision checks

If both values are smaller, move left; if both are larger, move right; otherwise the current node is the split point or one requested node. O(h) time. Recursion uses O(h) stack; the iterative version uses O(1) auxiliary space. The copied file defines both with the same name, so the iterative version wins when run together. The example assumes unique BST values and both nodes are present.

Original repository source

Copied from the supplied local DSA-Series checkout; code and comments are preserved. Run alternative definitions separately when comparing approaches.

13-lowest-common-ancestor-bst.js

Original file on GitHub

function TreeNode(val) {
  this.val = val;
  this.left = this.right = null;
}

// Recursive
var lowestCommonAncestor = function (root, p, q) {
  if (root.val < p.val && root.val < q.val) {
    return lowestCommonAncestor(root.right, p, q);
  }
  if (root.val > p.val && root.val > q.val) {
    return lowestCommonAncestor(root.left, p, q);
  }
  return root;
};

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