Lowest Common Ancestor of a Binary Search Tree

medium tree bst dfs

Problem

Given a binary search tree and two values p and q present in it, find their lowest common ancestor — the deepest node having both p and q as descendants (a node is allowed to be its own descendant).

Use the BST property: starting from the root, if both p and q are smaller than the current node, the answer lies entirely in the left subtree; if both are larger, it lies in the right subtree; otherwise the current node is the split point — return it.

Inputroot = [6,2,8,0,4,7,9,_,_,3,5], p = 2, q = 8

Output6

tree (level-order, '_' = null)

def lowest_common_ancestor(root, p, q):
    while root:
        if p.val < root.val and q.val < root.val:
            root = root.left
        elif p.val > root.val and q.val > root.val:
            root = root.right
        else:
            return root

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

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        while (root != null) {
            if (p.val < root.val && q.val < root.val) root = root.left;
            else if (p.val > root.val && q.val > root.val) root = root.right;
            else return root;
        }
        return null;
    }
}

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    while (root) {
        if (p->val < root->val && q->val < root->val) root = root->left;
        else if (p->val > root->val && q->val > root->val) root = root->right;
        else return root;
    }
    return nullptr;
}

Explanation

Because this is a binary search tree, every node neatly splits values: everything smaller sits on the left, everything larger on the right. We can use that ordering to find the split point of p and q without any recursion.

We just walk down from the root. If both p and q are smaller than the current node, the answer must be in the left subtree, so move left. If both are larger, move right.

The moment the two targets are no longer on the same side — one is <= the node and the other is >= it — the current node is exactly where their paths diverge. That node is the lowest common ancestor, so we return it.

Example: tree rooted at 6 with p = 2, q = 8. At 6, we see 2 < 6 but 8 > 6 — they split right here, so the answer is 6.

Since we only ever step down one path, this runs in time proportional to the tree's height and uses no extra memory.

Time: O(h) Space: O(1)