AlgoMaster Logo

Search in a Binary Search Tree

easyFrequency6 min readUpdated June 23, 2026

Understanding the Problem

We have a binary search tree and a target value, and we need to find the node whose value matches the target. If we find it, we return that node (which effectively returns the entire subtree rooted at it). If no match exists, we return null.

The detail that matters is that this is a binary search tree, not just any binary tree. In a BST, for every node, all values in its left subtree are smaller and all values in its right subtree are larger. This ordering property is what makes binary search possible on a tree. Instead of checking every node, we can decide at each step which direction to go, eliminating one entire subtree each time.

That ordering is what lets us do better than visiting every node.

Key Constraints:

  • 1 <= number of nodes <= 5000 -- The tree is small, so even a full O(n) traversal runs fast. The BST structure lets us avoid most of that work.
  • root is a binary search tree -- This guarantees the ordering property that lets us prune one subtree at every step.
  • 1 <= Node.val <= 10^7 and 1 <= val <= 10^7 -- All values are positive integers in the same range, so no overflow or negative-value handling is needed. The comparisons val < root.val fit comfortably in a 32-bit integer.

Approach 1: Brute Force (DFS on Entire Tree)

Intuition

Ignore the BST property entirely and treat this as a regular binary tree. We visit every node using DFS, and when we find a node whose value matches val, we return it. If we exhaust the tree without a match, we return null.

This is the approach for a generic binary tree, where no ordering exists to guide the search. It works on a BST too, but it ignores the structure we were given.

Algorithm

  1. Start at the root.
  2. If the current node is null, return null.
  3. If the current node's value equals val, return the current node.
  4. Recursively search the left subtree. If the result is not null, return it.
  5. Recursively search the right subtree. Return whatever it gives back.

Example Walkthrough

1Start: call searchBST(4, 2). Check node 4: val(2) != 4. Recurse left
4current2137
1/3

Code

The brute force visits both subtrees at every node. In a BST, when val is less than the current node's value, it cannot be in the right subtree. The next approach uses that ordering to pick a single direction at each step.

Approach 2: BST-Guided Recursive Search

Intuition

Instead of searching both subtrees, we compare val to the current node's value and pick one direction:

  • If val equals the node's value, we found it. Return the node.
  • If val is less than the node's value, the target can only be in the left subtree, since everything to the right is larger.
  • If val is greater than the node's value, the target can only be in the right subtree.

This is binary search applied to a tree instead of an array. At each step we discard one entire subtree, which cuts the work from O(n) to O(h), the height of the tree (O(log n) when the tree is balanced).

Algorithm

  1. If the current node is null, return null (target not found).
  2. If the current node's value equals val, return the current node.
  3. If val is less than the current node's value, recursively search the left subtree.
  4. If val is greater than the current node's value, recursively search the right subtree.

Example Walkthrough

1Start: call searchBST(4, 2). Compare val(2) with node(4)
4current2137
1/4

Code

This recursive version uses O(h) space on the call stack. Because each recursive call is the last action the function takes, we can replace it with a loop and remove the stack entirely.

Approach 3: BST-Guided Iterative Search

Intuition

The recursive solution is tail-recursive: each recursive call is the last action before the function returns, and its result is returned unchanged. That means no work waits on the call stack, so we can convert it into a while loop. Instead of recursing, we move a pointer to the next node to examine.

The iterative version runs the same comparison-and-branch logic without building a call stack, which brings space down to O(1) regardless of how deep the tree is.

Algorithm

  1. Set a pointer current to the root.
  2. While current is not null:
    • If current.val equals val, return current.
    • If val is less than current.val, move current to current.left.
    • Otherwise, move current to current.right.
  3. If the loop ends (current became null), return null.

Example Walkthrough

1Initialize: current = root (node 4). Compare val(2) with current(4)
4current2137
1/4

Code