DSA problem
Search in a Binary Search Tree
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 a strong ordering property: for every node, all values in its left subtree are strictly less than the node's value, and all values in its right subtree are strictly greater. This invariant lets you discard half of the remaining tree at every step rather than visiting every node, just like binary search on a sorted array.
A recursive solution is natural: if the current node is null or its value matches, return it; otherwise descend left when val < node.val and right when val > node.val. While clean, recursion incurs a function-call stack proportional to the tree's height, which can grow to O(n) in a skewed tree.
The optimal approach replaces recursion with an iterative loop. Walk a single pointer from the root, comparing val against node.val and following the appropriate child until either you find the match or you walk off the bottom. This runs in O(h) time, where h is the height of the tree (O(log n) when balanced, O(n) in the worst case), and uses O(1) extra space.
Examples
root = [4,2,7,1,3], val = 2[2,1,3]root = [4,2,7,1,3], val = 5[]root = [8,3,10,1,6,null,14,null,null,4,7,13], val = 6[6,4,7]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
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.