On this page

Lowest Common Ancestor of a Binary Search Tree

Given a BST and two nodes p and q, return their lowest common ancestor (LCA): the lowest node that has both p and q as descendants (a node can be a descendant of itself).

Constraints:

  • The number of nodes is in the range [2, 10^5].
  • All values are unique, p != q, and both exist in the BST.

Intuition

1 8
2 / \
3 4 12
4 / \ / \
5 2 6 10 14

For p = 2 and q = 6 the LCA is 4. For p = 2 and q = 14 it is 8. For p = 4 and q = 6 it is 4 (a node can be its own ancestor).

In a general binary tree we would have to search both sides. In a BST, comparing values is enough:

  • If both p and q are smaller than the current node, they are both in the left subtree, so the LCA is on the left.
  • If both are larger, the LCA is on the right.
  • Otherwise they split here (one on each side, or one of them is this node), so this node is the LCA.

Approach: Walk Down Until the Paths Split

  1. Start at the root.
  2. While the node exists:
    • If p.val < node.val and q.val < node.val, go left.
    • Else if p.val > node.val and q.val > node.val, go right.
    • Otherwise return this node.

The first node where p and q go in different directions (or one equals the node) is the lowest one that still contains both.

Code

class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
while (root != nullptr) {
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;
}
};

Complexity

Time: O(h)

One root-to-leaf path is walked: O(log n) balanced, O(n) skewed.

Space: O(1)

The loop is iterative and uses no extra memory.

How to Explain It in an Interview

How to Explain it in an Interview

The 30-Second Spoken Pitch
"In a BST I can use the values to decide where the LCA is. I start at the root. If both p and q are smaller than the current node, they are both in the left subtree, so I go left. If both are larger, I go right. Otherwise they split at this node, either one on each side or one of them equal to the node, so this node is the lowest common ancestor and I return it. That follows a single path, so time is O of h and space is O of one. This is much simpler than the general binary tree version, which has to search both subtrees."
Next TopicConstruct Bst from Preorder Traversal