☕ DSA Java Articles

Topics › Binary Search Trees › Concepts

Search in BST

Easy TUF ID 108 SDE

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

You are given the root of a binary search tree (BST) and an integer val. Return the node whose value equals val; the subtree rooted at that node is the answer. If no node has that value, return null.

In a BST, for every node, all values in its left subtree are smaller than the node’s value and all values in its right subtree are larger. Values are distinct.

Constraints (LeetCode 700): 1 to 5000 nodes, node values and val in [1, 10^7]. The Java file also tests an empty tree, negative values, Integer.MIN_VALUE and Integer.MAX_VALUE, and a 100000-node tree.

Example 1

        4
       / \
      2   7
     / \
    1   3

val = 2  ->  answer is the subtree   2
                                    / \
                                   1   3

Example 2

same tree, val = 5  ->  answer = null

5 > 4 sends the search right to 7; 5 < 7 sends it left, where there is no node. If 5 existed, that empty spot is the only place it could be.

Approach 1: Brute force, search the whole tree

Intuition. Ignore the ordering and treat the tree as an ordinary binary tree: check the current node, then search the left subtree, then the right subtree. This works for any binary tree, which makes it a useful reference, but it can visit every node even though the BST property would let us skip most of them.

Algorithm.

  1. If the node is null or holds val, return it.
  2. Search the left subtree; if something was found, return it.
  3. Otherwise return the result of searching the right subtree.
static TreeNode bruteForce(TreeNode root, int val) {
    if (root == null || root.val == val) return root;
    TreeNode found = bruteForce(root.left, val);
    return found != null ? found : bruteForce(root.right, val);
}

Complexity. Time O(n): in the worst case (value absent, or in the last subtree explored) every node is checked. Space O(h) for the recursion.

Approach 2: Use the ordering, recursively

Intuition. This is binary search on a tree. Compare val with the current node. If they are equal we are done. If val is smaller, it cannot be in the right subtree, because every value there is larger than the node’s value, which is already larger than val. So the entire right subtree can be discarded without looking at it. Symmetrically, if val is larger, discard the left subtree. Each comparison moves one level down, so the search follows a single root-to-leaf path.

Algorithm.

  1. If the node is null or holds val, return it.
  2. If val < node.val, search the left subtree; otherwise search 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), one node per level. Space O(h) for the recursion. For a balanced tree h is about log2 n, so a 100000-node tree needs about 17 comparisons. For a degenerate tree, for example one built by inserting keys in sorted order, h = n and the search is linear again.

Approach 3: Optimal, the same path as a loop

Intuition. The recursive call in Approach 2 is the last thing the method does (a tail call), and it only needs the next node. Java does not optimise tail calls, so each level still costs a stack frame, but we can turn the recursion into a loop that keeps only the current node. The logic is identical: step left or right until we either hit val or fall off the tree.

Algorithm.

  1. cur = root.
  2. While cur is not null and cur.val != val: move to cur.left if val < cur.val, else to cur.right.
  3. Return cur, which is the matching node or null.
static TreeNode iterative(TreeNode root, int val) {
    TreeNode cur = root;
    while (cur != null && cur.val != val) {
        cur = val < cur.val ? cur.left : cur.right;      // discard the half that cannot hold val
    }
    return cur;
}

Dry run on both examples:

val cur comparison next cur
2 4 2 < 4 2
2 2 equal stop, return node 2
5 4 5 > 4 7
5 7 5 < 7 null
5 null   stop, return null

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

Edge cases and pitfalls