☕ DSA Java Articles

Topics › Binary Search Trees › Concepts

Search in a Binary Search Tree

Easy TUF ID 2780 A2Z

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

You are given the root of a binary search tree and an integer val. Return the node whose key equals val; the caller then holds the whole subtree rooted at that node. If no node has that key, return null.

Recall the BST property: for every node, all keys in its left subtree are smaller than the node’s key and all keys in its right subtree are larger. Keys are distinct.

Constraints: up to 5000 nodes; keys and val fit in an int.

Example 1

        4
       / \
      2   7          val = 2
     / \
    1   3            answer = the subtree [2, 1, 3]

2 is the left child of the root, and its subtree contains 1 and 3.

Example 2

same tree, val = 5   answer = null

5 is larger than 4 and smaller than 7, so it could only be the left child of 7, and that slot is empty.

Approach 1: Brute force, search every node

Intuition. Ignore the ordering and treat the input as a plain binary tree: check the current node, then search the left subtree, then the right subtree. This is correct for any binary tree, which is exactly why it is wasteful here. It can visit every node even though the ordering already says where val must be.

Algorithm.

  1. If the node is null, return null.
  2. If its key equals val, return the node.
  3. Search the left subtree; if that found something, return it.
  4. Otherwise return whatever the search of the right subtree returns.
static TreeNode bruteForce(TreeNode root, int val) {
    if (root == null) return null;
    if (root.val == val) return root;
    TreeNode inLeft = bruteForce(root.left, val);
    if (inLeft != null) return inLeft;
    return bruteForce(root.right, val);
}

Complexity. Time O(n): when val is absent, every node is visited. Space O(h) for the recursion stack, where h is the height of the tree.

Approach 2: Recursive descent using the BST property

Intuition. Compare val with the current key. If they are equal, we are done. If val is smaller, it cannot be in the right subtree, because every key there is larger than the current key, which is already larger than val. Only the left subtree can contain it. Symmetrically, if val is larger, only the right subtree can. One comparison discards an entire subtree, so the search follows a single root-to-leaf path. This is binary search on a sorted array in a different shape: the current node plays the role of the middle element, and its subtrees are the two halves.

Algorithm.

  1. If the node is null or holds val, return the node. This single line handles both “not found” and “found”.
  2. If val < node.val, return the search of the left subtree; otherwise return the search of the right subtree.
static TreeNode recursive(TreeNode root, int val) {
    if (root == null || root.val == val) return root;
    return val < root.val ? recursive(root.left, val) : recursive(root.right, val);
}

Complexity. Time O(h): at most one node per level. Space O(h) for the recursion stack. The height is about log2 n for a balanced tree but can be n for a chain, which is the worst case for both time and stack depth.

Approach 3: Optimal, iterative descent

Intuition. In Approach 2 the recursive call is the last thing each call does, and its result is returned unchanged. Nothing has to be remembered on the way back up, so the call can be replaced by moving a pointer cur down the same path in a loop. The comparisons are identical; only the call stack disappears.

Algorithm.

  1. Set cur = root.
  2. While cur is not null and cur.val != val, move cur to its left child if val < cur.val, otherwise to its right child.
  3. Return cur. It is either the matching node or null because the walk fell off the tree.
static TreeNode optimal(TreeNode root, int val) {
    TreeNode cur = root;
    while (cur != null && cur.val != val) {
        cur = val < cur.val ? cur.left : cur.right;   // val can only live on one side
    }
    return cur;                                       // the matching node, or null if we fell off
}

Dry run on Example 1 (val = 2):

step cur comparison move
1 4 2 < 4 go left
2 2 2 == 2 stop, return node 2

and on Example 2 (val = 5):

step cur comparison move
1 4 5 > 4 go right
2 7 5 < 7 go left
3 null none stop, return null

Complexity. Time O(h), Space O(1).

Java does not optimise tail calls, so on a degenerate tree shaped like a long chain the recursive version uses one stack frame per level and can overflow for very deep trees, while the loop cannot. The test file runs both on a 2000-node chain; at that depth recursion is still fine, but the loop is the version to rely on in general.

Why discarding a subtree is safe

It is worth being precise about why Approaches 2 and 3 never miss the key. Suppose val < cur.val. Every key in the right subtree of cur is greater than cur.val by the BST property, and cur.val > val, so every key there is greater than val. None of them can equal val. The same reasoning applies on the other side. So at every step the key, if it exists at all, is in the subtree we move into. When cur becomes null that subtree is empty, which proves val is absent.

A useful by-product: the null slot where an unsuccessful search ends is precisely the position where val would be inserted. Insertion into a BST is this search plus one assignment.

Edge cases and pitfalls