Search in a Binary Search Tree

Easy

#0654Time: O(H), where H is the height of the tree. Similar to the recursive approach, this is O(log N) for a balanced tree and O(N) for a skewed tree.Space: O(1). This is the main advantage over the recursive approach. We only use a single pointer to traverse the tree, so the space used is constant regardless of the tree's size or structure.

Data structures

Tree Binary Tree Binary Search Tree

Prompt

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 <= 10⁷
root is a binary search tree.
1 <= val <= 10⁷

Approaches

3 approaches with complexity analysis and trade-offs.

This is an iterative version of the optimized BST search. It uses a loop instead of recursion to traverse the tree, which eliminates the recursion call stack overhead and reduces space complexity to a constant.

Algorithm

Initialize a current pointer to the root.
Loop as long as current is not null and current.val is not equal to val.
Inside the loop, if val is less than current.val, update current to current.left.
Otherwise (if val is greater than current.val), update current to current.right.
After the loop, return the current pointer.

Walkthrough

We initialize a pointer, current, to the root of the tree. We then enter a loop that continues as long as current is not null. Inside the loop, we compare val with current.val.

If val is equal to current.val, we've found the node and break the loop.
If val is less than current.val, we know the target must be in the left subtree, so we update current to current.left.
If val is greater than current.val, we update current to current.right. The loop effectively traverses a single path from the root down towards the potential location of the node. When the loop terminates, current will either point to the found node or be null if the value doesn't exist in the tree. We then return current.

1/**2 * Definition for a binary tree node.3 * public class TreeNode {4 *     int val;5 *     TreeNode left;6 *     TreeNode right;7 *     TreeNode() {}8 *     TreeNode(int val) { this.val = val; }9 *     TreeNode(int val, TreeNode left, TreeNode right) {10 *         this.val = val;11 *         this.left = left;12 *         this.right = right;13 *     }14 * }15 */16class Solution {17    public TreeNode searchBST(TreeNode root, int val) {18        TreeNode current = root;19        while (current != null && current.val != val) {20            if (val < current.val) {21                current = current.left;22            } else {23                current = current.right;24            }25        }26        return current;27    }28}

Complexity

Time

O(H), where H is the height of the tree. Similar to the recursive approach, this is O(log N) for a balanced tree and O(N) for a skewed tree.

Space

O(1). This is the main advantage over the recursive approach. We only use a single pointer to traverse the tree, so the space used is constant regardless of the tree's size or structure.

Trade-offs

Pros

Most efficient in terms of space complexity (O(1)).
Avoids potential stack overflow errors for very deep trees.
Generally faster in practice due to no function call overhead.

Cons

The code might be slightly less intuitive for some developers compared to the direct recursive translation of the search logic.

This approach treats the Binary Search Tree as a regular binary tree and performs a standard traversal (like pre-order) to visit every node. It doesn't leverage the inherent ordering property of a BST.

Algorithm

If the current node is null, return null.
If the current node's value equals val, return the current node.
Recursively search in the left subtree. If the node is found there, return the result.
If not found in the left subtree, recursively search in the right subtree and return its result.

Walkthrough

The algorithm starts at the root and recursively explores the entire tree. At each node, it checks if the node's value matches the target value val. If a match is found, the node is returned immediately. If the current node is not a match, the search continues in the left subtree, and if not found there, it proceeds to the right subtree. If the entire tree is traversed without finding the value, null is returned. This method is exhaustive and guarantees finding the node if it exists, but it's inefficient as it misses the optimization opportunity provided by the BST structure.

1/**2 * Definition for a binary tree node.3 * public class TreeNode {4 *     int val;5 *     TreeNode left;6 *     TreeNode right;7 *     TreeNode() {}8 *     TreeNode(int val) { this.val = val; }9 *     TreeNode(int val, TreeNode left, TreeNode right) {10 *         this.val = val;11 *         this.left = left;12 *         this.right = right;13 *     }14 * }15 */16class Solution {17    public TreeNode searchBST(TreeNode root, int val) {18        if (root == null) {19            return null;20        }21        if (root.val == val) {22            return root;23        }24        25        // Search in the left subtree26        TreeNode leftResult = searchBST(root.left, val);27        if (leftResult != null) {28            return leftResult;29        }30        31        // If not in the left, search in the right subtree32        return searchBST(root.right, val);33    }34}

Complexity

Time

O(N), where N is the number of nodes in the tree. In the worst-case scenario, we might have to visit every node to find the value or determine it's not present.

Space

O(H), where H is the height of the tree, due to the recursion call stack. In the worst case of a skewed tree, H can be equal to N, leading to O(N) space complexity.

Trade-offs

Pros

Simple to understand and implement.
Guaranteed to work for any binary tree, not just a BST.

Cons

Inefficient as it does not utilize the properties of a BST.
Visits unnecessary nodes, leading to a slower runtime compared to optimized approaches.

This approach takes full advantage of the Binary Search Tree property: values in the left subtree are smaller, and values in the right subtree are larger than the current node's value. This allows us to eliminate half of the remaining tree at each step.

Algorithm

If the root is null or root.val is equal to val, return the root.
If val is less than root.val, recursively search in the left subtree: return searchBST(root.left, val).
If val is greater than root.val, recursively search in the right subtree: return searchBST(root.right, val).

Walkthrough

The search starts at the root. We compare the target value val with the current node's value.

If val is equal to the node's value, we've found our target and return the node.
If val is less than the node's value, we know the target, if it exists, must be in the left subtree. So, we recursively call the search function on the left child.
If val is greater than the node's value, the target must be in the right subtree. We then recursively call the search function on the right child.
If we reach a null node, it means the value is not in the tree, and we return null.

1/**2 * Definition for a binary tree node.3 * public class TreeNode {4 *     int val;5 *     TreeNode left;6 *     TreeNode right;7 *     TreeNode() {}8 *     TreeNode(int val) { this.val = val; }9 *     TreeNode(int val, TreeNode left, TreeNode right) {10 *         this.val = val;11 *         this.left = left;12 *         this.right = right;13 *     }14 * }15 */16class Solution {17    public TreeNode searchBST(TreeNode root, int val) {18        if (root == null || root.val == val) {19            return root;20        }21        22        if (val < root.val) {23            return searchBST(root.left, val);24        } else {25            return searchBST(root.right, val);26        }27    }28}

Complexity

Time

O(H), where H is the height of the tree. For a balanced BST, H ≈ log(N), making the complexity O(log N). For a skewed tree, H = N, leading to a worst-case complexity of O(N).

Space

O(H) due to the recursion call stack. For a balanced BST, this is O(log N). For a skewed tree, it's O(N).

Trade-offs

Pros

Much more efficient than a brute-force search for balanced trees.
The logic is clean and directly reflects the definition of a BST search.

Cons

The space complexity can be O(N) in the worst case of a skewed tree.
Recursive calls can have a slight overhead compared to an iterative solution.

Solutions

Solution

1/** * Definition for a binary tree node. * public 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 ; } return root . val < val ? searchBST ( root . right , val ) : searchBST ( root . left , val ); } }

1# Definition for a binary tree node. # 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 root is None or root . val == val : return root return ( self . searchBST ( root . right , val ) if root . val < val else self . searchBST ( root . left , val ) )

1/** * Definition for a binary tree node. * struct TreeNode { * 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 ; return root -> val < val ? searchBST ( root -> right , val ) : searchBST ( root -> left , val ); } };

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem

Solution

1/** * Definition for a binary tree node. * public 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 ; } return root . val < val ? searchBST ( root . right , val ) : searchBST ( root . left , val ); } }

1# Definition for a binary tree node. # 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 root is None or root . val == val : return root return ( self . searchBST ( root . right , val ) if root . val < val else self . searchBST ( root . left , val ) )

1/** * Definition for a binary tree node. * struct TreeNode { * 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 ; return root -> val < val ? searchBST ( root -> right , val ) : searchBST ( root -> left , val ); } };

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.