700. Search in a Binary Search Tree - Detailed Explanation

Given the root of a binary search tree and a target value, return the subtree rooted at the node holding that value, or null if no node holds it. The point of the question is whether you use the ordering invariant. A candidate who searches every node has answered a different question.

This problem opens the binary search tree section of LeetCode 75.

Examples

Constraints

• The number of nodes is in the range 1 to 5,000, so the tree is never empty.
• Node values and the target are between 1 and 10,000,000.
• The tree is guaranteed to be a valid binary search tree.

Which pattern this problem belongs to

This is the binary search pattern applied to a tree rather than an array. The invariant that makes binary search work on a sorted array is the same one that makes it work here: at every step you can discard half of what remains. In an array you discard by moving an index, and in a binary search tree you discard by following one child pointer.

The binary search tree invariant is that every value in a node's left subtree is smaller than the node, and every value in its right subtree is larger. That single property is what turns a linear scan into a descent.

Approach

Compare the target with the current node. If they match, return the node. If the target is smaller, the invariant guarantees it cannot be in the right subtree, so move left. If it is larger, move right. Stop when you fall off the tree, which means the value is absent.

Each step moves down one level, so the work is proportional to the height h, not the node count n. For a balanced tree that is O(log n). For a tree degenerate into a single chain it is O(n), and saying so unprompted is what separates a complete answer from a partial one. The problem does not promise balance, only validity.

The iterative version is preferable in an interview. It is the same logic as a loop rather than recursion, which removes the stack entirely and brings space to O(1).

Python code

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def search_bst(root, val):
    """Iterative descent. O(h) time, O(1) space."""
    node = root
    while node is not None and node.val != val:
        node = node.left if val < node.val else node.right
    return node

def search_bst_recursive(root, val):
    """Same logic, O(h) stack."""
    if root is None or root.val == val:
        return root
    if val < root.val:
        return search_bst_recursive(root.left, val)
    return search_bst_recursive(root.right, val)

Java code

public TreeNode searchBST(TreeNode root, int val) {
    TreeNode node = root;
    while (node != null && node.val != val) {
        node = val < node.val ? node.left : node.right;
    }
    return node;
}

Complexity

Common mistakes

• Searching both subtrees. Recursing left and right ignores the invariant and turns an O(h) descent into an O(n) traversal. This is the error the question exists to catch.
• Returning a boolean or the value. The question asks for the subtree rooted at the match, so return the node itself.
• Claiming O(log n) without qualification. That holds only for a balanced tree, and nothing here guarantees balance. Say O(h) and then explain when h is logarithmic.
• Handling the null root as a special case. The loop condition already covers it, so no extra branch is needed.

Related problems

• Insert into a Binary Search Tree, which descends the same way and then attaches a node where the search fell off.
• Delete Node in a BST, which descends the same way and is harder only because of the two-child case.
• Validate Binary Search Tree, which checks the invariant this question relies on.

How to Prepare

• Write the iterative version by default. It is shorter, it uses no stack, and it demonstrates you understand the descent rather than just the recursion.
• State the balance caveat before being asked. O(h) with an explanation of when h is log n is a complete complexity answer. O(log n) alone is not.
• Group the family. The binary search tree questions share one invariant, and Grokking the Coding Interview teaches them together, with the shorter summary in the most common LeetCode patterns.