Search in a Binary Search Tree

Link: LeetCode - Search in a Binary Search Tree

Problem Statement

Given the root of a binary search tree (BST) and an integer value, return the subtree rooted with the node that has the given value. If such a node does not exist, return null.

Intuition

A Binary Search Tree (BST) follows these properties:

Left subtree contains values less than the node.
Right subtree contains values greater than the node.

So at each node:

If val == root.val, return that node.
If val < root.val, search in the left subtree.
If val > root.val, search in the right subtree.

Approach: Recursive Traversal

Use recursion based on the comparison between val and the current node’s value.

Java Code

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

        // Recursive Case
        if (val < root.val) {
            return searchBST(root.left, val);  // Search left subtree
        } else {
            return searchBST(root.right, val); // Search right subtree
        }
    }
}

Time and Space Complexity

Time Complexity: O(h)
Where h is the height of the tree.
- For a balanced BST: O(log n)
- For a skewed BST: O(n)
Space Complexity: O(h)
Due to recursion stack.

Dry Run

Input Tree:

val = 2

Start at root (4): 2 < 4 → move left
Node = 2 → match found → return subtree

Output:

    2
   / \
  1   3

Conclusion

This problem demonstrates how efficiently we can search in a BST using its properties. Recursive traversal ensures we skip irrelevant subtrees and keep the solution optimal.