Search in a Binary Search Tree

Search in a Binary Search Tree

What is this problem about?

The Search in a Binary Search Tree interview question asks you to find a node in a BST with a given target value and return the subtree rooted at that node. If the target is not found, return null. This leverages the BST property: all left subtree values are less than the root, and all right subtree values are greater.

Why is this asked in interviews?

Apple, Microsoft, Meta, Amazon, Google, Bloomberg, and Adobe ask this problem because it is the foundational BST operation. Every BST-based problem (insertion, deletion, validation, range search) builds on this basic search. It tests understanding of the BST invariant and recursive/iterative traversal — both of which appear throughout database indexing, ordered map implementations, and autocomplete systems.

Algorithmic pattern used

Two clean patterns: recursive and iterative. Recursive: if root is null or root.val == target, return root. If target < root.val, recurse left. If target > root.val, recurse right. Iterative: while node is not null, compare node.val with target. Move left or right accordingly. Return the node when found, or null when the pointer goes out of bounds.

Example explanation

BST:

    8
   / \
  3   10
 / \    \
1   6    14
   / \   /
  4   7 13

Search for 6:

• 8: 6 < 8 → go left.
• 3: 6 > 3 → go right.
• 6: match! Return subtree rooted at 6.

Search for 5:

• 8 → left. 3 → right. 6 → left. 4 → right. Null → return null.

Common mistakes candidates make

• Not using the BST property and doing a full DFS/BFS instead — O(n) when O(log n) is achievable.
• Returning True/False instead of the subtree node — the problem asks for the subtree, not just existence.
• Incorrectly implementing the comparison direction (< vs >).
• Not handling a null root at the start (empty tree case).

Interview preparation tip

For the Search in a Binary Search Tree coding problem, the BST interview pattern is core. Practice both recursive and iterative implementations — interviewers at Apple and Adobe sometimes ask specifically for the iterative version to avoid stack overflow on deep trees. The iterative version is O(h) time and O(1) space (no call stack), making it preferable for very deep BSTs in production settings.