Search in a Binary Search Tree
Return the subtree rooted at the node holding a given value in a binary search tree, walking a single path from the root by comparing at each node.
Problem Understanding
Search in a Binary Search Tree (LeetCode 700): 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 it. If no such node exists, return null.
Examples: root = [4, 2, 7, 1, 3], val = 2 → [2, 1, 3]; the same tree with val = 5 → null.
The Intuition: Binary Search on a Tree
A BST keeps smaller values to the left and larger values to the right of every node, the same order a sorted array has.
- Start at the root.
- Compare. Equal: found. Smaller: the value can only be in the left subtree. Larger: only in the right.
- Repeat until you find it or step onto an empty child.
It is Introduction to Binary Search with the halving built into the tree. Insert into a Binary Search Tree walks exactly the same path and attaches a node where this search would return null.
Interactive Walkthrough
SEARCH 2 · OUTLINE = PATH WALKED
START AT ROOT
val
2
Nodes visited
1
Returned
:
Search for 2, starting at the root 4
Next
2 < 4: if 2 is in the tree, it is in the left subtree. Go left to 2
BST
val
The node the search is on is filled and the path behind it outlined. Every node off the path was skipped thanks to the BST order. Try Example 2 to see the search fall off the tree, and Root to see the whole tree returned.
Dry Run Table
Input: root = [4, 2, 7, 1, 3], val = 2.
| Node | Compare | Next |
|---|---|---|
| 4 | 2 < 4 | left, to 2 |
| 2 | 2 = 2 | found |
Answer: the subtree [2, 1, 3], after visiting 2 of the 5 nodes.
The Solution Template
An iterative walk that stops on the match or on null, and returns wherever it stopped.
Search in a Binary Search Tree Code
1var searchBST = function(root, val) {2 let node = root;3 while (node && node.val !== val) {4 if (val < node.val) {5 node = node.left;6 } else {7 node = node.right;8 }9 }10 return node;11};
Edge Cases & Common Mistakes
- Value at the root: the loop never runs and the whole tree is returned.
- Value missing: return null, not the last node visited.
- Searching both subtrees: a plain DFS works but is O(n); the BST order lets you skip one side at every node.
- Returning the value instead of the node: LeetCode wants the subtree, so return the node itself.
Summary
Walk down from the root, going left for smaller values and right for larger ones, and return the node where the value matches, or null. O(h) time, O(1) space.
More practice: DSA interview questions with answers · patterns cheat sheet