Search in a Binary Search Tree - Video Solutions

Problem Overview: Given the root of a Binary Search Tree (BST) and a target value, return the node whose value equals the target. If the value does not exist, return null. The key constraint is that the input tree follows BST ordering rules: all values in the left subtree are smaller than the node, and all values in the right subtree are larger.

This ordering property allows you to avoid scanning the entire binary tree. Instead of exploring both children like a regular tree search, you move only in the direction where the target could exist.

Approach 1: Recursive BST Search (Time: O(h), Space: O(h))

This approach uses recursion to follow the BST property. Start at the root and compare the current node's value with the target. If the values match, return the current node. If the target is smaller, recursively search the left subtree; if larger, search the right subtree.

The key insight: because the structure is a tree that obeys BST ordering, half of the remaining nodes are eliminated at every decision point. The recursion continues until the node is found or a null pointer is reached. The time complexity is O(h), where h is the height of the tree (O(log n) for balanced trees, O(n) in the worst case). Space complexity is also O(h) due to the recursion call stack.

This version is compact and easy to read. Many interview candidates start with this because it closely mirrors the definition of BST search.

Approach 2: Iterative BST Search (Time: O(h), Space: O(1))

The iterative approach performs the same comparisons but avoids recursion. Maintain a pointer starting at the root. While the pointer is not null, compare its value with the target. If equal, return the node. If the target is smaller, move to node.left; otherwise move to node.right.

This approach walks down the tree exactly once, following the only valid path where the target could exist. Because no recursion stack is used, the extra space drops to O(1). The time complexity remains O(h), which becomes O(log n) for balanced BSTs and O(n) in a skewed tree.

Iterative search is often preferred in production systems because it avoids recursion overhead and stack limits. The logic is straightforward: repeatedly compare and move left or right until the value is found.

Recommended for interviews: Both approaches demonstrate understanding of BST properties, but interviewers usually expect the iterative or recursive O(h) BST traversal rather than a full tree scan. Showing the recursive version first proves you understand the BST decision rule, while the iterative version demonstrates awareness of space optimization and practical implementation tradeoffs.