---
title: "700. Search in a Binary Search Tree"
url: "https://laigary.com/interview/coding/700-search-in-a-binary-search-tree"
type: "note"
section: "coding"
date: "2023-01-29"
updated: "2026-07-28"
tags: ["Tree", "Binary Search Tree", "Binary Search"]
---

# 700. Search in a Binary Search Tree

[700\. Search in a Binary Search Tree](https://leetcode.com/problems/search-in-a-binary-search-tree/)

在一棵 BST 裡找出值等於 `val` 的節點，回傳以它為根的子樹；找不到就回傳 `None`。

這題是 BST 家族最小的一塊 —— 把它想清楚，[701 插入](/interview/coding/701-insert-into-a-binary-search-tree)、[450 刪除](/interview/coding/450-delete-node-in-a-bst)、[235 LCA](/interview/coding/235-lowest-common-ancestor-of-a-binary-search-tree) 都是在同一條「往下走」的路徑上多做一件事。

## 思路

### 先看普通的樹

如果題目只說「樹」，沒有排序的保證，那就只能每個節點都問一次：從根開始，不是答案就左右子樹都去找。$O(n)$，沒得商量。

### BST 讓你每次砍掉一半

BST 的性質是「左子樹的值全部小於自己，右子樹全部大於自己」。所以在任何一個節點上比較一次，就知道答案只可能在哪一邊 —— **另一邊整棵直接丟掉，連看都不用看。**

這就是**二分搜尋**，只是資料結構從陣列換成了樹：

| | 陣列的二分搜尋 | BST |
|---|---|---|
| 中點怎麼來 | `(lo + hi) // 2` 算出來 | 樹的結構天生就給你 |
| 一次比較之後 | 捨棄一半的索引區間 | 捨棄一整棵子樹 |
| 一次比較的成本 | $O(1)$ | $O(1)$ |
| 總步數 | $O(\log n)$ | $O(h)$ |

差別在最後一行：陣列的二分保證 $O(\log n)$，因為中點是算出來的、必定對半分；**BST 只能保證 $O(h)$**，而樹可能長歪。如果依序插入 1、2、3…，整棵樹會變成一條鏈，$h = n$，搜尋就退化成 $O(n)$。

**所以「BST 搜尋是 $O(\log n)$」這句話其實只在樹平衡時成立。** 這也是 AVL、紅黑樹這些自平衡結構存在的理由。

## 解題方向

### 一、當成普通的樹搜尋

```python
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def searchBST(self, root: TreeNode, val: int) -> TreeNode:
        if not root or root.val == val:
            return root
        return self.searchBST(root.left, val) or self.searchBST(root.right, val)
```

`if not root or root.val == val: return root` 一行處理掉兩個終止條件 —— 找不到時 `root` 就是 `None`，剛好也是要回傳的東西。

`or` 的短路特性正好對應「左邊找到就不用再找右邊」。

### 二、利用 BST 的性質

```python
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def searchBST(self, root: TreeNode, val: int) -> TreeNode:
        if not root or root.val == val:
            return root
        if root.val > val:
            return self.searchBST(root.left, val)
        elif root.val <= val:
            return self.searchBST(root.right, val)
```

差別只有一件事：不再兩邊都遞迴，而是**先比較再決定往哪一邊**。

`elif root.val <= val` 裡的等號其實走不到 —— `root.val == val` 在第一行就被攔下來了，所以到這裡一定是 `root.val < val`。寫 `<=` 不會錯，但寫成 `else` 或 `<` 更能表達「剩下的情況只有一種」。

### 三、改寫成迴圈

上面那版是**尾遞迴** —— 遞迴呼叫的結果直接回傳，沒有任何後續處理。這種形狀一定可以改成迴圈，空間從 $O(h)$ 降到 $O(1)$：

```python
class Solution:
    def searchBST(self, root: TreeNode, val: int) -> TreeNode:
        node = root
        while node and node.val != val:
            node = node.left if val < node.val else node.right
        return node
```

迴圈跳出時，`node` 要嘛是找到的節點、要嘛是 `None`，剛好就是答案。

**「只往下走一條路」的 BST 題都可以這樣寫** —— [235](/interview/coding/235-lowest-common-ancestor-of-a-binary-search-tree) 的迭代版是同一個手法。反過來說，需要「回頭處理另一邊」的樹題（例如 [236](/interview/coding/236-lowest-common-ancestor-of-a-binary-tree) 的後序回報）就沒辦法，那時候堆疊是必要的。

## 補充

**BST 家族的共同骨架**都是「比較 → 往一邊走」，差別在走到底之後做什麼：

| 題目 | 走到底之後 |
|---|---|
| 700 | 回傳節點 |
| [701. Insert into a BST](/interview/coding/701-insert-into-a-binary-search-tree) | 在空位掛上新節點 |
| [450. Delete Node in a BST](/interview/coding/450-delete-node-in-a-bst) | 刪掉並用後繼節點補位 |
| [235. LCA of a BST](/interview/coding/235-lowest-common-ancestor-of-a-binary-search-tree) | 走到分岔點就停 |
| [270. Closest BST Value](/interview/coding/270-closest-binary-search-tree-value) | 一路記錄最接近的值 |

**另一條線是中序遍歷**：BST 的中序走訪剛好是由小到大的排序結果，[98. Validate BST](/interview/coding/98-validate-binary-search-tree)、[230. Kth Smallest in a BST](/interview/coding/230-kth-smallest-element-in-a-bst)、[173. BST Iterator](/interview/coding/173-binary-search-tree-iterator) 都是靠這個性質。整理見 [Tree 遍歷模板](/interview/coding/tree-traversal-template)。

## 複雜度

$n$ 是節點數、$h$ 是樹高。

| 解法 | 時間 | 空間 |
|---|---|---|
| 一、普通樹搜尋 | $O(n)$ | $O(h)$ 遞迴堆疊 |
| 二、BST 遞迴 | $O(h)$ | $O(h)$ 遞迴堆疊 |
| 三、BST 迴圈 | $O(h)$ | $O(1)$ |

平衡時 $h = O(\log n)$；退化成一條鏈時 $h = n$，解法二三就跟解法一一樣慢了 —— 但即使如此，解法二三依然不會比解法一差。