Back to solutions

Lowest Common Ancestor of a BST

MediumBST

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

Open problem
Constraints
  • 2 <= nodes <= 10^5
  • All Node.val are unique
  • p != q

Walk down using BST order

Time O(h)Space O(1)

Starting at the root, if both values are smaller go left, if both are larger go right; the first node that splits them (or equals one) is their lowest common ancestor.

struct TreeNode { int val; TreeNode* left; TreeNode* right; };

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;
}