Search in a Binary Search Tree

Description

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.

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

Approach 1: Iterative BST Search ($O(H)$ Time, $O(1)$ Space)

Intuition

Leverage the fundamental Binary Search Tree property: all values in the left subtree are strictly smaller than root.val, and all values in the right subtree are strictly larger than root.val:

1. Traverse down the tree using a pointer curr initialized to root.
2. While curr is not null and curr.val != val:
   • If val < curr.val, shift to the left child (curr = curr.left).
   • If val > curr.val, shift to the right child (curr = curr.right).
3. Return curr (which will either point to the target node or null if not found).

class Solution {
    public TreeNode searchBST(TreeNode root, int val) {
        TreeNode curr = root;
 
        while (curr != null && curr.val != val) {
            if (val < curr.val) {
                curr = curr.left;
            } else {
                curr = curr.right;
            }
        }
 
        return curr;
    }
}
 

Complexity

• Time Complexity: $O(H)$ — Bounded by the height $H$ of the BST ($O(\log N)$ for a balanced tree, $O(N)$ worst-case for a skewed tree).
• Space Complexity: $O(1)$ — Iterates through pointers using constant auxiliary space.

---

Approach 2: Recursive DFS ($O(H)$ Time, $O(H)$ Space)

Intuition

Express the binary search decisions recursively:

1. Base Case: If root == null or root.val == val, return root.
2. Left Branch: If val < root.val, recursively search the left subtree searchBST(root.left, val).
3. Right Branch: If val > root.val, recursively search the right subtree searchBST(root.right, val).

class Solution {
    public TreeNode searchBST(TreeNode root, int val) {
        if (root == null || root.val == val) {
            return root;
        }
 
        return val < root.val ? searchBST(root.left, val) : searchBST(root.right, val);
    }
}
 

Complexity

• Time Complexity: $O(H)$ — Visits at most one node per tree level up to tree height $H$.
• Space Complexity: $O(H)$ — Recursion call stack requires space equal to tree height $H$ ($O(\log N)$ balanced, $O(N)$ skewed).

---

Easy Memory Rule

“Target smaller than node? Go Left $\to$ Target larger than node? Go Right $\to$ Match or null? Return Node!”