Scale Engineer

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
TreeBinary TreeBinary 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 <= 107
  • root is a binary search tree.
  • 1 <= val <= 107

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.
/** * 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) {        TreeNode current = root;        while (current != null && current.val != val) {            if (val < current.val) {                current = current.left;            } else {                current = current.right;            }        }        return current;    }}

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.

Solutions

/** * 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 ); } }

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 →

Next problem