Lowest Common Ancestor of a Binary Search Tree

Problem Description

Given a binary search tree (BST), find the lowest common ancestor (LCA) node of two given nodes p and q in the BST.

According to the definition of LCA: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”

Examples

Constraints

• The number of nodes in the tree is in the range [2, 10⁵].
• -10⁹ ≤ Node.val ≤ 10⁹
• All Node.val are unique.
• p and q will exist in the BST.
• p != q

Leveraging BST Properties to Find the Split Point

In a standard binary tree, finding the LCA requires traversing the entire tree to look for p and q. In a Binary Search Tree (BST), we can exploit the ordering property: for any node, all left descendants are smaller, and all right descendants are larger.

Start at the root. Compare p and q values against the root:

• If both p and q are smaller than the root, the LCA must be in the left subtree.
• If both p and q are larger than the root, the LCA must be in the right subtree.
• If they lie on opposite sides (one is smaller, one is larger), or if one of them is equal to the root, the current node is the split point, which is the Lowest Common Ancestor.

This reduces the search to a simple path traversal.

Solution 1: Iterative BST Traversal

Traverse down the tree by comparing values, updating the current node until you reach the split point.

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        TreeNode curr = root;
        while (curr != null) {
            if (p.val < curr.val && q.val < curr.val) {
                curr = curr.left;             // both are in the left subtree
            } else if (p.val > curr.val && q.val > curr.val) {
                curr = curr.right;            // both are in the right subtree
            } else {
                return curr;                  // split point found: this is the LCA
            }
        }
        return null;
    }
}

class Solution:
    def lowestCommonAncestor(
        self, root: TreeNode, p: TreeNode, q: TreeNode
    ) -> TreeNode:
        curr = root
        while curr:
            if p.val < curr.val and q.val < curr.val:
                curr = curr.left  # both are in the left subtree
            elif p.val > curr.val and q.val > curr.val:
                curr = curr.right  # both are in the right subtree
            else:
                return curr  # split point found: this is the LCA
        return None

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        TreeNode* curr = root;
        while (curr) {
            if (p->val < curr->val && q->val < curr->val) {
                curr = curr->left;             // both are in the left subtree
            } else if (p->val > curr->val && q->val > curr->val) {
                curr = curr->right;            // both are in the right subtree
            } else {
                return curr;                  // split point found: this is the LCA
            }
        }
        return nullptr;
    }
};

Complexity Analysis:

• Time Complexity: O(h) where h is the tree height. We traverse one path from root to leaf in the worst case. For a balanced BST, this is O(log n); for a skewed BST, this is O(n).
• Space Complexity: O(1) auxiliary space as we only use a pointer variable.

Where it breaks: If the input tree violates the BST properties (e.g. it is a standard binary tree that is not sorted), this logic fails completely. For general binary trees, you must use backtracking depth-first search (LeetCode 236).

Common Mistakes

• Writing a complex DFS that traverses the entire tree. While a general binary tree LCA solution works on a BST, it runs in O(n) time and misses the opportunity to optimize to O(h) with O(1) space.
• Forgetting that a node can be an ancestor of itself. If p is the parent of q, the split check p.val > curr.val && q.val > curr.val will evaluate to false when curr == p. The algorithm correctly returns p immediately.
• Null checks inside the loop when not needed. Since the problem constraints guarantee that p and q exist in the tree, curr will never reach null before finding the LCA.

Frequently Asked Questions

Does the order of p and q matter in the input? No. The conditions check p.val < curr.val && q.val < curr.val, which is commutative. The comparison evaluates correctly regardless of whether p is smaller or larger than q.

What if the BST contains duplicate values? The constraints state that all node values are unique. If duplicates were present, the definition of BST direction splits becomes ambiguous.

What does this problem test in interviews? It tests your ability to identify and exploit the properties of specific data structures (BST ordering rules) to optimize search algorithms.

← All Problems