Search in a Binary Search Tree

Given the root of a binary search tree and an integer val, return the subtree rooted at the node whose value equals val. If no such node exists, return null (an empty tree).

The tree is given/returned in level-order (breadth-first), using null for missing children.

Hints

· Stuck? Reveal one nudge at a time.

In a BST, compare val to the node to decide the direction.

Smaller means the target is in the left subtree; larger means the right.

Walk straight down until you match or hit null — O(height).

Common doubts

The BST invariant guarantees the value can only be on one side, so exploring both wastes the ordering and makes it O(n).

The subtree rooted at the matching node, so callers can keep working within it.

On a degenerate (chain-like) BST the height is O(n); balancing keeps it O(log n).

Interview follow-ups

· What an interviewer asks next.

Search the same way; the null slot where the search ends is exactly where the new node goes.

Do the same descent but remember the best candidate seen so far on the correct side.

Fun facts

BST search is binary search on a tree — the same halving, but following pointers instead of array indices.
The path the search takes is exactly where an insert of that value would land.

Asked at

AmazonMicrosoft

Frequently Sometimes Occasionally

Example 1

Input: root = [4, 2, 7, 1, 3], val = 2
Output: [2, 1, 3]
2 is the left child of the root; return its whole subtree.

Example 2

Input: root = [4, 2, 7, 1, 3], val = 5
Output: []
5 is not in the tree.

Constraints

- The number of nodes is in the range [1, 5000] - 1 <= Node.val <= 10^7 - root is a valid BST - 1 <= val <= 10^7

In a BST, each node tells you which way to go: if val is smaller than the current node, the target can only be in the left subtree; if larger, only the right. So searching is a single walk from the root downward — O(height), versus O(n) for a blind scan.

Prerequisites

Before you start

· Concepts used directly in the solution.

BST invariant. Left subtree < node < right subtree, at every node.

Compare and descend. One comparison decides the direction.

Clarifying questions

Questions to ask first

· Signals seniority before you write a line of code.

Setup

“What do you return?”

The whole subtree rooted at the matching node (not just the value).

“What if val isn't present?”

Return null.

The ideal opening — say it like this

Because it's a BST, I compare val to the current node and go left if smaller, right if larger.

I stop when I find the value or fall off the tree — an O(height) walk.

Understand the problem

Worked example — BST [4, 2, 7, 1, 3], val = 2

        4
       / \
      2   7
     / \
    1   3
4 vs 2 -> go left -> 2 == 2 -> return subtree [2, 1, 3]

Key observations

1Aha

The comparison picks the side

Smaller than the node ⇒ only the left subtree can contain it; larger ⇒ only the right.

2Aha

One root-to-node walk

You never backtrack — search is a straight descent.

3Aha

O(height)

Balanced ⇒ O(log n); a skewed BST degrades to O(n).

Brute force vs optimal

	Recursive descent	Iterative descent
Idea	Recurse into the correct child	Loop, moving to the correct child
Time	O(height)	O(height)
Space	O(height)	O(1)

Both are O(height); the iterative version uses O(1) space. Full code is in the Approaches selector below.

Summary

Key takeaway

Compare val to the node and descend left (smaller) or right (larger) until you match or hit null. O(height) time, O(1) space iteratively.

while node:
    if val == node.val: return node
    node = node.left if val < node.val else node.right
return null