Search in a Binary Search Tree
Easy · Trees · Tree · Binary Search Tree · Binary Tree
Problem
You are 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 (the node itself, with everything below it). If no such node exists, return None (shown as []).
Examples
Input: root = [8,3,10,1,6], val = 3 Output: [3,1,6]
Node 3 is found to the left of 8, and it brings its children 1 and 6.
Input: root = [8,3,10,1,6], val = 7 Output: []
The search goes 8 → 3 → 6 and then falls off: no node holds 7.
Input: root = [4,2,7], val = 4 Output: [4,2,7]
The root itself matches, so the whole tree is returned.
Constraints
- 1 <= number of nodes <= 5000
- 1 <= Node.val <= 10^7
- root is a valid binary search tree
- 1 <= val <= 10^7
Approaches
- Baseline: search every node — time O(n), space O(n)
Follow-up
The search costs one step per level, so its speed depends on the height: balanced trees keep it at O(log n), a chain makes it O(n). The use cases return the search path itself, and find the next larger value, a search for a value that may be missing.
Related problems
Start free on Cariara · Coding problems · System design studio
