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.

Because the tree is a valid BST, 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


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

Complexity: O(n) time, O(h) recursion space. With n ≤ 5000 it passes, but it ignores the fact that 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. The tree’s branches play 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


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

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

graph TD
    A[4] --> B[2]
    A --> C[7]
    B --> D[1]
    B --> E[3]

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, since each call does nothing after the recursive return. It unrolls into a simple loop with a moving pointer, so there is no call stack and 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


def searchBST(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 uses the least space and is the preferred solution.

Common pitfalls

• Searching both subtrees “to be safe”: this degrades O(h) to O(n) and ignores the BST invariant. Values are distinct and ordered, so one side is always 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, because smaller values live left. An inverted branch often 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). 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 O(1) space.