What is the most efficient way to search in a binary search tree?

Use BST properties to traverse left or right depending on comparisons, avoiding unnecessary full-tree traversal.

How do I return the subtree rooted at the target node?

Once the target node is found, simply return that node; all its descendants are automatically included.

Can I use iteration instead of recursion for this problem?

Yes, iterative traversal using a loop is space-efficient and maintains the same correctness as recursion.

What should I return if the value does not exist in the BST?

Return null to indicate that no matching node exists, as per problem requirements.

Does this problem follow a specific pattern?

Yes, it follows binary-tree traversal and state tracking, leveraging BST comparisons for efficient search.

#700

Easy

auto_awesome二分·树·traversal

LeetCode 题解工作台

二叉搜索树中的搜索

给定二叉搜索树（BST）的根节点 root 和一个整数值 val 。你需要在 BST 中找到节点值等于 val 的节点。返回以该节点为根的子树。如果节点不存在，则返回 null 。示例 1: 输入： root = [4,2,7,1,3], val = 2 输出： [2,1,3] 示例 2: …

树二叉搜索树二叉树

题目描述

给定二叉搜索树（BST）的根节点 root 和一个整数值 val。

你需要在 BST 中找到节点值等于 val 的节点。返回以该节点为根的子树。如果节点不存在，则返回 null 。

示例 1:

输入：root = [4,2,7,1,3], val = 2
输出：[2,1,3]

示例 2:

输入：root = [4,2,7,1,3], val = 5
输出：[]

提示：

树中节点数在 [1, 5000] 范围内
1 <= Node.val <= 10⁷
root 是二叉搜索树
1 <= val <= 10⁷

lightbulb

解题思路

方法一：递归

我们判断当前节点是否为空或者当前节点的值是否等于目标值，如果是则返回当前节点。

否则，如果当前节点的值大于目标值，则递归搜索左子树，否则递归搜索右子树。

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 是二叉树的节点数。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

# 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: Optional[TreeNode], val: int) -> Optional[TreeNode]:
        if root is None or root.val == val:
            return root
        return (
            self.searchBST(root.left, val)
            if root.val > val
            else self.searchBST(root.right, val)
        )

speed

复杂度分析

指标	值
时间	complexity is O(h), where h is the height of the tree, because traversal follows a single path guided by BST properties. Space complexity is O(h) for recursion due to call stack or O(1) for iterative traversal, making this approach scalable for large BSTs.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Candidate identifies BST traversal and early termination as core optimization.
question_mark
Candidate correctly distinguishes recursive vs iterative trade-offs for space efficiency.
question_mark
Candidate returns the subtree immediately without unnecessary full-tree traversal.

warning

常见陷阱

外企场景

error
Not following BST left/right guidance, leading to full-tree traversal.
error
Failing to return null when the value is not found, causing incorrect outputs.
error
Confusing subtree return with node value only, missing the full subtree structure.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Search in a BST and return only the path to the target node.
arrow_right_alt
Search in a BST where duplicates may exist, returning the first encountered node.
arrow_right_alt
Modify search to return the parent of the target node instead of the subtree.

help

常见问题

外企场景

继续练习

#701 二叉搜索树中的插入操作 #703 数据流中的第 K 大元素 #669 修剪二叉搜索树