You are given the root of a binary search tree (BST) and an integer val.
Find the node in the BST that the node's value equals val and return the subtree rooted with that node. If such a node does not exist, return null.
Example 1:
Input: root = [4,2,7,1,3], val = 2 Output: [2,1,3]
Example 2:
Input: root = [4,2,7,1,3], val = 5 Output: []
Constraints:
[1, 5000].1 <= Node.val <= 107root is a binary search tree.1 <= val <= 107Problem Overview: Given the root of a Binary Search Tree (BST) and a target value, return the node whose value equals the target. If the value does not exist, return null. The key constraint is that the input tree follows BST ordering rules: all values in the left subtree are smaller than the node, and all values in the right subtree are larger.
This ordering property allows you to avoid scanning the entire binary tree. Instead of exploring both children like a regular tree search, you move only in the direction where the target could exist.
Approach 1: Recursive BST Search (Time: O(h), Space: O(h))
This approach uses recursion to follow the BST property. Start at the root and compare the current node's value with the target. If the values match, return the current node. If the target is smaller, recursively search the left subtree; if larger, search the right subtree.
The key insight: because the structure is a tree that obeys BST ordering, half of the remaining nodes are eliminated at every decision point. The recursion continues until the node is found or a null pointer is reached. The time complexity is O(h), where h is the height of the tree (O(log n) for balanced trees, O(n) in the worst case). Space complexity is also O(h) due to the recursion call stack.
This version is compact and easy to read. Many interview candidates start with this because it closely mirrors the definition of BST search.
Approach 2: Iterative BST Search (Time: O(h), Space: O(1))
The iterative approach performs the same comparisons but avoids recursion. Maintain a pointer starting at the root. While the pointer is not null, compare its value with the target. If equal, return the node. If the target is smaller, move to node.left; otherwise move to node.right.
This approach walks down the tree exactly once, following the only valid path where the target could exist. Because no recursion stack is used, the extra space drops to O(1). The time complexity remains O(h), which becomes O(log n) for balanced BSTs and O(n) in a skewed tree.
Iterative search is often preferred in production systems because it avoids recursion overhead and stack limits. The logic is straightforward: repeatedly compare and move left or right until the value is found.
Recommended for interviews: Both approaches demonstrate understanding of BST properties, but interviewers usually expect the iterative or recursive O(h) BST traversal rather than a full tree scan. Showing the recursive version first proves you understand the BST decision rule, while the iterative version demonstrates awareness of space optimization and practical implementation tradeoffs.
This approach uses the recursive traversal of the BST properties. It checks if the current node's value is equal to the target value. If it is, it returns the subtree rooted at the current node. If the target value is less than the current node, it recurses into the left subtree; if greater, it recurses into the right subtree. This method leverages the BST's inherent properties to narrow down the search.
This C code defines a recursive function searchBST that starts from the root of the tree. It checks if the current node is NULL or matches the target val. If it matches, it returns the node. If the target is smaller, it recurses into the left subtree; otherwise, it goes to the right subtree.
Time Complexity: O(h) where h is the height of the tree, as we traverse from the root to a leaf.
Space Complexity: O(h) due to the recursion stack.
In this approach, we use an iterative solution instead of recursion to save stack space. Starting from the root, we use a loop to traverse the tree. At each node, we check if it matches the target value. If it matches, we return the node; if not, we decide to move to the left or right child based on the BST property. The absence of a matching node returns null.
This code converts the recursive search logic into an iterative one by using a while loop. It repeatedly narrows down the search area based on the value comparison until it finds the value or reaches a NULL node.
Time Complexity: O(h) where h is tree height.
Space Complexity: O(1) since we're only using a few extra pointers.
We check if the current node is null or if the current node's value equals the target value. If so, we return the current node.
Otherwise, if the current node's value is greater than the target value, we recursively search the left subtree; otherwise, we recursively search the right subtree.
The time complexity is O(n), and the space complexity is O(n). Here, n is the number of nodes in the binary tree.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Recursive Approach | Time Complexity: O(h) where h is the height of the tree, as we traverse from the root to a leaf. |
| Iterative Approach | Time Complexity: O(h) where h is tree height. |
| Recursion | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive BST Search | O(h) | O(h) | When you want concise code and recursion is acceptable |
| Iterative BST Search | O(h) | O(1) | Preferred for memory efficiency and production implementations |
L40. Search in a Binary Search Tree | BST | C++ | Java • take U forward • 218,736 views views
Watch 9 more video solutions →Practice Search in a Binary Search Tree with our built-in code editor and test cases.
Practice on FleetCode