Problem Overview

You are given the root of a Binary Search Tree (BST) and an integer val.
Your task is to find the node in the BST whose value equals val and return the subtree rooted at that node.
If such a node does not exist, return null.

A Binary Search Tree (BST) has the property that for every node:

• Values in the left subtree are smaller than the node’s value.
• Values in the right subtree are larger than the node’s value.

---

Example 1

Input:

root = [4,2,7,1,3], val = 2

Output:

[2,1,3]

Explanation:
The subtree rooted at node with value 2 is:

    2
   / \
  1   3

---

Example 2

Input:

root = [4,2,7,1,3], val = 5

Output:

[]

Explanation:
No node with value 5 exists in the tree, so return null.

---

Intuition

The Binary Search Tree (BST) structure allows efficient searching by eliminating half of the tree at each step, similar to binary search in arrays.

At each node:

• If val == node.val, return the current node.
• If val < node.val, the value must lie in the left subtree.
• If val > node.val, the value must lie in the right subtree.

This property gives us two possible approaches:

1. Recursive traversal (simpler and more intuitive).
2. Iterative traversal (avoids recursion stack).

---

Approach 1: Recursive Solution

Algorithm Steps

1. Base Case:
   • If the current node is null, return null (value not found).
2. If node.val == val, return node.
3. If val < node.val, recursively search in the left subtree.
4. If val > node.val, recursively search in the right subtree.

---

Java Code Implementation

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */

public class Solution {
    public TreeNode searchBST(TreeNode root, int val) {
        // Base case: node is null or value found
        if (root == null || root.val == val) {
            return root;
        }

        // If value is smaller, go left
        if (val < root.val) {
            return searchBST(root.left, val);
        }
        // Otherwise, go right
        else {
            return searchBST(root.right, val);
        }
    }
}

---

Approach 2: Iterative Solution

The iterative version avoids recursion and uses a simple while loop.

Algorithm Steps

1. Start from the root node.
2. While the current node is not null:
   • If val == node.val, return node.
   • If val < node.val, move to the left child.
   • Otherwise, move to the right child.
3. If we exit the loop, the node was not found → return null.

---

Java Code Implementation (Iterative)

public class Solution {
    public TreeNode searchBST(TreeNode root, int val) {
        TreeNode current = root;

        while (current != null) {
            if (current.val == val) {
                return current; // Found the node
            } else if (val < current.val) {
                current = current.left; // Go left
            } else {
                current = current.right; // Go right
            }
        }

        return null; // Value not found
    }
}

---

Complexity Analysis

Aspect	Analysis
Time Complexity	O(h), where h is the height of the tree. For balanced BST → O(log n), for skewed BST → O(n).
Space Complexity (Recursive)	O(h) due to recursive call stack.
Space Complexity (Iterative)	O(1) as no additional stack is used.

---

Example Dry Run

Input:

root = [4,2,7,1,3], val = 2

Tree structure:

       4
     /   \
    2     7
   / \
  1   3

Step-by-step:

1. Start at root (4). Since 2 < 4, move left.
2. At node (2). Found match → return node with value 2.

Output subtree:

   2
  / \
 1   3

---

Alternative Approach: Binary Search Analogy

Since the BST property mirrors binary search logic:

• Each comparison cuts down the search space by half.
• Hence, both algorithms (recursive and iterative) behave like binary search on a sorted list.

---

Key Takeaways

1. BST property allows skipping unnecessary subtrees, leading to efficient searches.
2. Recursive and iterative methods both achieve the same time complexity.
3. Iterative version is more memory-efficient (constant space).
4. This problem forms the foundation for more advanced BST problems like:
   • LeetCode 701 (Insert into BST)
   • LeetCode 450 (Delete Node in BST)