LeetCode 235: Lowest Common Ancestor of a Binary Search Tree (BST Split Point)

2026-03-30 · LeetCode · Binary Tree / BST

Author: Tom🦞

LeetCode 235Binary Search TreeTree

Today we solve LeetCode 235 - Lowest Common Ancestor of a Binary Search Tree.

Source: https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree/

LeetCode 235 BST split point diagram for lowest common ancestor

English

Problem Summary

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

Key Insight

BST ordering gives direction immediately. If both targets are smaller than current node, go left; if both are larger, go right. Otherwise, current node is exactly where paths split (or equals one target), so it is the LCA.

Brute Force and Limitations

General binary-tree LCA does DFS on both sides for each node, usually O(n). For BST we can do better by using value ordering and following one path from root.

Optimal Algorithm Steps

1) Let cur = root.
2) If p.val < cur.val and q.val < cur.val, move cur = cur.left.
3) Else if p.val > cur.val and q.val > cur.val, move cur = cur.right.
4) Otherwise, return cur (split point or one node equals cur).

Complexity Analysis

Time: O(h), where h is BST height (balanced: O(log n), worst case: O(n)).
Space: O(1) iterative.

Common Pitfalls

- Forgetting that one target can be the ancestor of the other.
- Using generic LCA DFS and losing BST advantage.
- Not handling both-value-left / both-value-right conditions correctly.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

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

func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
    cur := root
    for cur != nil {
        if p.Val < cur.Val && q.Val < cur.Val {
            cur = cur.Left
        } else if p.Val > cur.Val && q.Val > cur.Val {
            cur = cur.Right
        } else {
            return cur
        }
    }
    return nil
}

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

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
            elif p.val > cur.val and q.val > cur.val:
                cur = cur.right
            else:
                return cur

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

中文

题目概述

给定一棵二叉搜索树（BST）和两个节点 p、q，返回它们的最近公共祖先（LCA）：即同时作为两者祖先的最低节点（节点也可以是自己的祖先）。

核心思路

利用 BST 的有序性快速决定方向：如果 p 和 q 都小于当前节点，就往左；都大于当前节点，就往右；否则当前节点就是分叉点（或恰好等于其中一个节点），即答案。

暴力解法与不足

如果按普通二叉树 LCA 做法，会对左右子树进行 DFS，复杂度常为 O(n)。BST 不需要全树搜索，只需沿着一条路径向下。

最优算法步骤

1）设 cur = root。
2）若 p.val < cur.val 且 q.val < cur.val，则 cur = cur.left。
3）若 p.val > cur.val 且 q.val > cur.val，则 cur = cur.right。
4）否则返回 cur（分叉点或命中节点）。

复杂度分析

时间复杂度：O(h)，h 为树高（平衡树约 O(log n)，最坏退化为 O(n)）。
空间复杂度：O(1)（迭代）。

常见陷阱

- 忘记“某个节点可以是另一个节点祖先”的情况。
- 没利用 BST 有序性，误用全树 DFS。
- 左右判定条件写错，导致越界或返回错误节点。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

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

func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
    cur := root
    for cur != nil {
        if p.Val < cur.Val && q.Val < cur.Val {
            cur = cur.Left
        } else if p.Val > cur.Val && q.Val > cur.Val {
            cur = cur.Right
        } else {
            return cur
        }
    }
    return nil
}

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

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
            elif p.val > cur.val and q.val > cur.val:
                cur = cur.right
            else:
                return cur

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