Search in a Binary Search Tree

EASY

Description

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

Checkout 3 different approaches to solve Search in a Binary Search Tree. Click on different approaches to view the approach and algorithm in detail.

Iterative Search using BST Properties

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.

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 Analysis

Time Complexity: 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 Complexity: 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.

Pros and Cons

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.

Code Solutions

Checking out 3 solutions in different languages for Search in a Binary Search Tree. Click on different languages to view the code.

/** * 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 Solution

Watch the video walkthrough for Search in a Binary Search Tree

Data Structures:

TreeBinary TreeBinary Search Tree