#700

Easy

auto_awesomeBinary-tree traversal and state tracking

LeetCode Problem Workspace

Search in a Binary Search Tree

Locate a target value in a binary search tree and return the subtree rooted at that node using efficient tree traversal techniques.

tree binary search tree binary tree

Problem Statement

Given the root of a binary search tree and an integer val, locate the node whose value equals val. Return the subtree rooted at that node if it exists.

If the node with value val does not exist, return null. Use binary-search tree properties to guide traversal and minimize unnecessary checks, ensuring correctness for trees up to 5000 nodes with values ranging from 1 to 10^7.

Examples

Example 1

Input: root = [4,2,7,1,3], val = 2

Output: [2,1,3]

Example details omitted.

Example 2

Input: root = [4,2,7,1,3], val = 5

Output: []

Example details omitted.

Constraints

The number of nodes in the tree is in the range [1, 5000].
1 <= Node.val <= 107
root is a binary search tree.
1 <= val <= 107

Solution Approach

Recursive Search Leveraging BST Properties

Compare val with the current node's value. If val is smaller, recurse on the left subtree; if larger, recurse on the right subtree. Return the current node when a match is found. This approach naturally stops traversing unnecessary paths.

Iterative Traversal for Space Efficiency

Use a while loop starting from the root, moving left or right depending on comparisons with val. This avoids stack overhead from recursion and keeps space complexity at O(1), while maintaining the correctness of BST-guided search.

Return Subtree Once Found

Once the target node is located, immediately return it as the root of the desired subtree. No further traversal is needed beyond this node, which prevents unnecessary computation and aligns with BST traversal expectations.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time 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.

What Interviewers Usually Probe

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

Common Pitfalls or Variants

Common pitfalls

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

Follow-up variants

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

FAQ

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.

terminal

Solution

Solution 1: Recursion

We check if the current node is null or if the current node's value equals the target value. If so, we return the current node.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

# 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)
        )

Continue Practicing

#701 insert into a binary search tree #703 kth largest element in a stream #669 trim a binary search tree