💬 Discord
Sign In
NeetCode #421LC-235MediumTreesBlind 75NC 150NC 250
← Back to All Problems

#421 · #235 · Lowest Common Ancestor of a Binary Search Tree(二叉搜索树的最近公共祖先)

📌 Problem Statement & Constraints

Given a binary search tree and two nodes p and q, return their lowest common ancestor (LCA). Constraints: the number of nodes is in [2, 10^5]; all values are distinct; both nodes exist in the tree.

💡 Core Algorithmic Approaches

  1. In a BST, the LCA is the first node whose value lies between p.val and q.val (inclusive).
  2. Start at the root: if both values are smaller, go left; if both are larger, go right.
  3. Otherwise the current node splits the two, so it is the LCA.
  4. The iterative form is O(1) space and avoids recursion entirely.

💻 Benchmark Python3 Implementation

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


# Recursive variant
class Solution2:
    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
        if p.val < root.val and q.val < root.val:
            return self.lowestCommonAncestor(root.left, p, q)
        if p.val > root.val and q.val > root.val:
            return self.lowestCommonAncestor(root.right, p, q)
        return root

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(h): the search descends one level at a time, where h is the tree height.
💾 Space Complexity
O(1) for the iterative version; O(h) for the recursion.

⚠️ Interview Pitfalls & Follow-ups

  • Using the general binary-tree LCA algorithm: it works but is O(n) instead of O(h); the BST ordering is what makes the fast version possible.
  • Comparing with <= on one side and < on the other inconsistently: since values are distinct, either strict form works, but be consistent.
  • Returning the child instead of the current node: the LCA is the node where the paths diverge, which is the current node.
  • Assuming p and q are always in different subtrees: one may be an ancestor of the other, in which case the ancestor is the LCA -- and the else branch returns it correctly.