Module 4 · BST Pattern

Search in a Binary Search Tree

EasyProblem 10 of 24 6 min read ~12 min to solve LeetCode

TreeBSTBinary Search TreeSearchIteration

Asked atMicrosoftAmazonGoogleMetaBloomberg

Problem Statement

Given the root of a binary search tree and an integer val, find the node whose value equals val and return the subtree rooted at that node. If val does not exist in the tree, return null.

Input

A BST root and a target integer val.

Output

The node with value val, including its entire subtree, or null if the value is absent.

Constraints

•1 <= number of nodes <= 5000
•1 <= Node.val <= 10^7
•Each node value is unique
•1 <= val <= 10^7

Examples

Example 1

Input:

root = **[4,2,7,1,3]**, val = **2**

Output: **[2,1,3]**

Explanation: The value **2** is found as the left child of **4**, so the subtree rooted at **2** is returned.

Example 2

Input:

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

Output: **null**

Explanation: The search goes right from **4** toward **7**, then left to an empty child because **5 < 7**. The value is not present.

Learning Objectives

Use the BST ordering rule to discard one entire subtree at every step.
Write the iterative compare-and-branch template with O(1) extra space.
Explain why search time depends on tree height rather than node count in a balanced BST.
Recognise this operation as the building block for insert, delete, and LCA in a BST.

Intuition

Pattern Recognition

The signal is a lookup in a binary search tree. The reusable phrase is BST -> compare and branch. At each node, the target either equals the node, must be in the left subtree, or must be in the right subtree. You never need to scan both sides.

The common trap is treating the tree as a regular binary tree and doing DFS or BFS over every node. That ignores the sorted structure. Search is the smallest BST operation, but it is the building block for insertion, deletion, predecessor-successor questions, and BST lowest common ancestor.

Common mistakes

×Searching both subtrees as if the input were an arbitrary binary tree.
×Reversing the branch condition and going right when the target is smaller.
×Returning only the value instead of the subtree root required by the problem.
×Claiming O(log n) time without qualifying that a skewed BST can have height O(n).

Algorithm Explanation

Key idea

Keep a pointer at the current candidate node. If the target is smaller than current.val, all values in the right subtree are too large, so move left. If the target is larger, all values in the left subtree are too small, so move right. If the pointer becomes null, the target is absent.

Recursion walkthrough

Use the BST [5,3,8,2,4,7,9] and search for 7. Start at 5. Since 7 > 5, the answer cannot be in the left subtree [3,2,4], so branch right to 8. Since 7 < 8, branch left to 7. The value matches, so return the subtree rooted at 7.

If searching for 6 in the same tree, the path is 5 -> 8 -> 7. Since 6 < 7, the search moves left to null and stops. The algorithm never touches the unrelated nodes 2, 3, 4, or 9.

Algorithm

Set current = root.
While current is not null, compare val with current.val.
If they are equal, return current.
If val < current.val, move current to current.left.
Otherwise move current to current.right.
If the loop exits, return null.

Solutions

Solution: Iterative compare and branch

When to prefer this:

Use this by default. It is the simplest BST operation, avoids recursion stack space, and is the template you will reuse for insert and LCA.

Walk one downward path. Each comparison discards one subtree and moves to the only child that can still contain the target.

Step-by-step

Start current at root.
If current is null, the target is absent.
If current.val equals val, return current.
If val is smaller, move to current.left.
If val is larger, move to current.right.
Repeat until a match or an empty child is reached.

Time

O(h)

Space

O(1)

The search follows one root-to-leaf path: O(log n) in a balanced tree and O(n) in a skewed tree.

Java implementation

Loading…

Dry Run

Sample input

root = [5,3,8,2,4,7,9], val = 7. Track the single path chosen by BST ordering.

step	current node	comparison	branch	remaining candidate area
1	5	7 is greater than 5	go right	only the subtree rooted at 8 can contain 7
2	8	7 is less than 8	go left	only the subtree rooted at 7 can contain 7
3	7	7 equals 7	stop	return the subtree rooted at 7

Only one path is explored: 5 -> 8 -> 7. BST ordering eliminates every sibling subtree along the way.

Interview Tips

Make the branch rule explicit before coding. The interviewer wants to hear that the BST property lets you eliminate half of the remaining tree in a balanced shape. Also be precise about the return value: return the node, not a boolean and not just the integer value.

Likely follow-ups

How would you implement the same search recursively?
How would you find the closest value if the exact target is absent?
How does search performance change in an unbalanced BST?
How would a self-balancing tree preserve O(log n) search time?

Key Takeaways

BST search follows one downward path, not a full tree traversal.
At each node, compare the target and choose exactly one branch.
The complexity is O(h): O(log n) when balanced and O(n) when skewed.
This compare-and-branch loop is the foundation for later BST operations.

Reusable template: BST lookup: compare target with current value, discard the impossible subtree, and continue down the only viable branch.