Search in a Binary Search Tree solution and explanation
Google
9 more videos on this problem
Search in a Binary Search Tree | Leetcode #700Techdose · 6:15 · 15K views
Search in a Binary Search Tree | LeetCode 700 | C++, Java, Python | BSTKnowledge Center · 15:32 · 3K views
Search in a Binary Search Tree | Leetcode 700 | Binary Search Tree | Day-14Ayushi Sharma · 11:38 · 2K views
Search in a Binary Search Tree - LeetCode #700 - Python, JavaScript, Java, C++CodingNinja · 6:12 · 2K views
Search in a Binary Search Tree - LeetCode 700 - Python (Recursive and Iterative!) #leetcodeDeepti Talesra · 8:12 · 1K views
Leetcode - Search in a Binary Search Tree (Python)Timothy H Chang · 2:00 · 491 views
Leetcode 700 Search in a Binary Search Tree Java SolutionHackerHeap · 3:52 · 294 views
How To Solve Search In A Binary Search Tree (LeetCode 700)Becoming A Better Dev (with David) · 4:34 · 252 views
LeetCode 700. Search in a Binary Search Tree | pythonEric Lee · 4:09 · 238 views
Search in a Binary Search Tree | Java | LeetCode - Easy - 700 | The Code MateThe Code Mate · 6:26 · 234 views
The problem
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:
- The number of nodes in the tree is in the range
[1, 5000]. 1 <= Node.val <= 107rootis a binary search tree.1 <= val <= 107
Approach overview
Problem 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.
Approach 1: Recursive Approach
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.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def searchBST(self, root: TreeNode, val: int) -> TreeNode:
if not root or root.val == val:
return root
if val < root.val:
return self.searchBST(root.left, val)
return self.searchBST(root.right, val)class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode() {}
TreeNode(int val) { this.val = val; }
TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}
class Solution {
public TreeNode searchBST(TreeNode root, int val) {
if (root == null || root.val == val) {
return root;
}
if (val < root.val) {
return searchBST(root.left, val);
}
return searchBST(root.right, val);
}
}class TreeNode {
public:
int val;
TreeNode *left;
TreeNode *right;
TreeNode() : val(0), left(nullptr), right(nullptr) {}
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
class Solution {
public:
TreeNode* searchBST(TreeNode* root, int val) {
if (!root || root->val == val) {
return root;
}
if (val < root->val) {
return searchBST(root->left, val);
}
return searchBST(root->right, val);
}
};function TreeNode(val, left = null, right = null) {
this.val = val;
this.left = left;
this.right = right;
}
var searchBST = function(root, val) {
if (!root || root.val === val) {
return root;
}
if (val < root.val) {
return searchBST(root.left, val);
}
return searchBST(root.right, val);
};#include <stdio.h>
#include <stdlib.h>
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
};
struct TreeNode* searchBST(struct TreeNode* root, int val) {
if (root == NULL || root->val == val) {
return root;
}
if (val < root->val) {
return searchBST(root->left, val);
}
return searchBST(root->right, val);
}public class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
this.val = val;
this.left = left;
this.right = right;
}
}
public class Solution {
public TreeNode SearchBST(TreeNode root, int val) {
if (root == null || root.val == val) {
return root;
}
if (val < root.val) {
return SearchBST(root.left, val);
}
return SearchBST(root.right, val);
}
}This Python function searchBST follows a recursive pattern to search for the node. If it finds the node with val, it returns that subtree; otherwise traverses left or right based on the value comparison.
Time Complexity: O(h), h being the height of the tree.
Space Complexity: O(h) for the recursion stack.
Approach 2: Iterative Approach
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.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def searchBST(self, root: TreeNode, val: int) -> TreeNode:
while root and root.val != val:
root = root.left if val < root.val else root.right
return rootclass TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode() {}
TreeNode(int val) { this.val = val; }
TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}
class Solution {
public TreeNode searchBST(TreeNode root, int val) {
while (root != null && root.val != val) {
root = val < root.val ? root.left : root.right;
}
return root;
}
}class TreeNode {
public:
int val;
TreeNode *left;
TreeNode *right;
TreeNode() : val(0), left(nullptr), right(nullptr) {}
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
class Solution {
public:
TreeNode* searchBST(TreeNode* root, int val) {
while (root != nullptr && root->val != val) {
if (val < root->val) {
root = root->left;
} else {
root = root->right;
}
}
return root;
}
};function TreeNode(val, left = null, right = null) {
this.val = val;
this.left = left;
this.right = right;
}
var searchBST = function(root, val) {
while (root && root.val !== val) {
root = val < root.val ? root.left : root.right;
}
return root;
};#include <stdio.h>
#include <stdlib.h>
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
};
struct TreeNode* searchBST(struct TreeNode* root, int val) {
while (root != NULL && root->val != val) {
if (val < root->val) {
root = root->left;
} else {
root = root->right;
}
}
return root;
}public class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
this.val = val;
this.left = left;
this.right = right;
}
}
public class Solution {
public TreeNode SearchBST(TreeNode root, int val) {
while (root != null && root.val != val) {
root = val < root.val ? root.left : root.right;
}
return root;
}
}The Python iteration involves a simple while loop to traverse the tree, going left or right at each node according to the BST properties, efficiently locating the target node.
Time Complexity: O(h) as we only examine part of the tree on each operation.
Space Complexity: O(1) since we use constant space.
Approach 3: Recursion
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.
/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function searchBST(root: TreeNode | null, val: number): TreeNode | null {
if (root === null || root.val === val) {
return root;
}
return root.val > val ? searchBST(root.left, val) : searchBST(root.right, val);
}/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func searchBST(root *TreeNode, val int) *TreeNode {
if root == nil || root.Val == val {
return root
}
if root.Val > val {
return searchBST(root.Left, val)
}
return searchBST(root.Right, val)
}Complexity comparison
| Approach | Complexity |
|---|---|
| Recursive Approach | Time Complexity: O(h), h being the height of the tree. |
| Iterative Approach | Time Complexity: O(h) as we only examine part of the tree on each operation. |
| Recursion | – |
Complexity analysis
| 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 |
Frequently asked questions
Is Search in a Binary Search Tree easy or hard?
Search in a Binary Search Tree is classified as an Easy problem. The core requirement is understanding the BST ordering rule and using it to avoid scanning the entire tree. Once the property is applied correctly, the implementation is straightforward.
How to solve Search in a Binary Search Tree in O(n)?
A general binary tree search that checks every node would take O(n) time. However, because the structure is a Binary Search Tree, you can do better by comparing the target with the current node and moving left or right. This reduces the search to O(h), typically O(log n) for balanced trees.
Search in a Binary Search Tree Python or Java solution?
Python and Java solutions follow the same logic: compare the target with the current node and move left or right accordingly. Python implementations often use recursion for brevity, while Java solutions commonly use iterative loops to avoid recursion overhead.
What is the best approach for Search in a Binary Search Tree?
The optimal approach uses the Binary Search Tree property to move left or right depending on the target value. Both recursive and iterative methods achieve O(h) time complexity, where h is the tree height. The iterative version is often preferred because it uses O(1) extra space while recursion uses O(h) stack space.
Is Search in a Binary Search Tree asked at Google/Amazon/Meta?
BST search is a foundational tree problem and frequently appears in interviews at companies like Amazon, Google, Meta, and Microsoft. It is often used as a warm‑up question before more complex BST operations such as insert, delete, or lowest common ancestor.
What data structure is used in Search in a Binary Search Tree?
The problem uses a Binary Search Tree, which is a specialized form of a binary tree where left subtree values are smaller and right subtree values are larger than the current node. This ordering property enables efficient search operations similar to binary search on arrays.
What is the time complexity of Search in a Binary Search Tree?
Searching in a Binary Search Tree takes O(h) time, where h is the height of the tree. In a balanced BST this becomes O(log n). In the worst case, when the tree is skewed like a linked list, the complexity degrades to O(n).