Search in a Binary Search Tree

Search in a Binary Search Tree : 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.

Approach 1: Iterative:

import java.util.Stack;

class Solution {
    public TreeNode searchBST(TreeNode root, int x) {
        if (root == null)
            return null;

        Stack stack = new Stack<>();
        stack.push(root);

        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();

            if (node.val == x) {
                return node;
            }

            // Since stack is LIFO, push right child first
            if (node.right != null) {
                stack.push(node.right);
            }
            if (node.left != null) {
                stack.push(node.left);
            }
        }

        return null;
    }
}

Time Complexity: O(n) and Space Complexity: O(n)

Other Approach to search in BST

The "Search in a Binary Search Tree" problem is a classic problem in computer science. The objective is to search for a node with a given value in a Binary Search Tree (BST). In a BST, for every node, all values in the left subtree are smaller, and all values in the right subtree are larger. This property allows for efficient search operations.

The problem can be solved in O(log n) time on average if the tree is balanced, where n is the number of nodes. If the tree is unbalanced, the time complexity can degrade to O(n).

Given the root of a Binary Search Tree (BST) and a value `val`, return the node in the BST that contains the value `val`. If the node does not exist in the tree, return `null`.

The tree node structure is defined as above. The task is to search for the node with value `val` in the BST and return it.

Approach

To search for a value in a Binary Search Tree, we can use the following steps:

• If the root is null, return null (the tree is empty).
• If the value of the current node is equal to the target value, return the current node.
• If the value is smaller than the current node’s value, search the left subtree (since all values in the left subtree are smaller).
• If the value is larger than the current node’s value, search the right subtree (since all values in the right subtree are larger).

By utilizing the binary search property of the tree, we can efficiently search for the target node by narrowing down the search space to either the left or right subtree at each step.

Algorithm

The algorithm follows these steps:

1. If the current node is null, return null (base case).
2. If the value of the current node matches the target value, return the current node.
3. If the target value is smaller than the current node’s value, recursively search in the left subtree.
4. If the target value is larger than the current node’s value, recursively search in the right subtree.

This algorithm works by leveraging the properties of the Binary Search Tree, ensuring that at each step, we are reducing the search space by half.

Example

Consider the following Binary Search Tree:

               4
              / \
             2   7
            / \   \
           1   3   9
        

Suppose we want to search for the value `3`. Starting at the root (value 4), we compare `3` with `4`. Since `3` is smaller than `4`, we move to the left child (value 2). Next, we compare `3` with `2`. Since `3` is larger than `2`, we move to the right child (value 3), where we find the value `3`. Therefore, the node with value `3` is returned.

Code Implementation

Below is the implementation of the algorithm to search for a value in a Binary Search Tree: