Search in a Binary Search Tree

Problem

You are given the root of a binary search tree (BST) and an integer val. Find the node whose value equals val and return the subtree rooted at that node. If no node has that value, return None.

Recall the BST property: for every node, all values in its left subtree are smaller than the node’s value, and all values in its right subtree are larger. All values in the tree are distinct.

Examples

Example 1

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

Node 2 is the root’s left child; the returned subtree is node 2 with children 1 and 3.

Example 2

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

5 is not in the tree (we’d go left from 7, which has no left child), so the answer is None.

Example 3

Input: root = [8,3,10,1,6], val = 8
Output: [8,3,10,1,6]

The target is the root itself, so the whole tree is returned.

Constraints

• The number of nodes is in the range [1, 5000].
• 1 <= Node.val <= 10^7, all values unique.
• 1 <= val <= 10^7
• The tree is guaranteed to be a valid BST.

The BST guarantee is the whole point: the expected solution visits one node per level, not every node.

Think about it first

TL;DR

Binary search down the tree — O(h) time (O(log n) balanced, O(n) worst), O(1) space iteratively.

Approach 1 — Brute force: search every node

Ignore the BST property and scan the whole tree with a plain DFS, as if it were an arbitrary binary tree.

# 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

from typing import Optional


class Solution:
    def searchBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
        if root is None:
            return None
        if root.val == val:
            return root
        found_left = self.searchBST(root.left, val)
        if found_left:
            return found_left
        return self.searchBST(root.right, val)

Complexity: O(n) time, O(h) recursion space. With n ≤ 5000 it passes, but it throws away the one guarantee the problem hands you — the tree is sorted — turning a logarithmic search into a linear one.

Approach 2 — Recursive binary search

The insight: the BST invariant means a single comparison at any node eliminates an entire subtree — the same halving idea as binary search on a sorted array, with the tree’s branches playing the role of the array’s halves.

# 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

from typing import Optional


class Solution:
    def searchBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
        if root is None or root.val == val:
            return root
        if val < root.val:
            return self.searchBST(root.left, val)
        return self.searchBST(root.right, val)

Walkthrough on Example 1 (root = [4,2,7,1,3], val = 2):

1. At 4: 2 < 4 → go left. (The entire right subtree, rooted at 7, is never touched.)
2. At 2: 2 == 2 → return this node, i.e. the subtree [2,1,3].

Complexity: O(h) time — one node per level on the path down. O(h) recursion space. For a balanced BST h = O(log n); for a degenerate chain h = O(n).

Approach 3 — Iterative descent

The insight: the recursion above is tail recursion — each call does nothing after the recursive return — so it unrolls into a simple loop with a moving pointer. No stack, O(1) extra space.

# 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

from typing import Optional


class Solution:
    def searchBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
        node = root
        while node is not None and node.val != val:
            node = node.left if val < node.val else node.right
        return node

Walkthrough on Example 2 (root = [4,2,7,1,3], val = 5):

1. At 4: 5 > 4 → step right to 7.
2. At 7: 5 < 7 → step left, which is None.
3. Loop exits with node = None → return None.

Complexity: O(h) time, O(1) space — the iterative version strictly dominates on space and is the one to reach for.

Common pitfalls

• Searching both subtrees “to be safe”: that silently degrades O(h) to O(n) and signals you don’t trust (or understand) the BST invariant. Values are distinct and ordered — one side is always provably empty of the target.
• Returning the value or a boolean instead of the node: the problem wants the subtree root (a TreeNode), and None — not -1 or False — on a miss.
• Flipping the comparison: val < node.val goes left (smaller values live left). An inverted branch usually still passes the “target is root” tests, so trace one miss by hand.
• Assuming O(log n): guaranteed only for balanced trees; a sorted-insertion BST is a linked list and the search is O(n). Say “O(h)” in interviews.

Pattern takeaway

In a BST, one comparison per node discards a whole subtree — every classic BST operation (search, insert, delete, floor/ceiling, closest value) is this same guided descent, costing O(h). And whenever a tree recursion is tail-recursive — “recurse into exactly one child and return its answer” — rewrite it as a while loop with a pointer for free O(1) space.