Search in a Binary Search Tree
The key idea
A binary search tree keeps every left subtree smaller than its node and every right subtree larger. So at each node you compare the target with the node value and walk into exactly one child: left if the target is smaller, right if it is larger. You never look at the other side, which turns the search into a single root-to-leaf path of length equal to the tree height.
Problem
You are given the root of a binary search tree (BST) and an integer val. Find the node in the BST whose value equals val and return the subtree rooted at that node. If such a node does not exist, return null. A binary search tree has the property that, 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.
Constraints
- The number of nodes in the tree is in the range [1, 5000].
- 1 <= Node.val <= 10^7
- root is a binary search tree.
- 1 <= val <= 10^7
Examples
Input: root = [4,2,7,1,3], val = 2
Output: [2,1,3]
Input: root = [4,2,7,1,3], val = 5
Output: []
Complexity
Time: O(h) Space: O(h)
See the full solution
- ✓Full worked approach
- ✓Reference code in 5 languages
- ✓Problem-solving tips
- ✓Step-by-step animated visualization
More Binary Search problems
- Binary SearchEASY
- Capacity To Ship Packages Within D DaysMEDIUM
- Find First and Last Position of Element in Sorted ArrayMEDIUM
- Find in Mountain ArrayHARD
- Find K Closest ElementsMEDIUM
- Find Minimum in Rotated Sorted ArrayMEDIUM
- Find Peak ElementMEDIUM
- First Bad VersionEASY
- Guess Number Higher or LowerEASY
- Koko Eating BananasMEDIUM
- Lowest Common Ancestor of a Binary Search TreeMEDIUM
- Median of Two Sorted ArraysHARD