Lowest Common Ancestor of BST
Watch the walkthrough
Open on InstagramProblem
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
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;
};