Search in a Binary Search Tree: Using the BST Property

You are given the root of a binary search tree and a value val. Find the node whose value equals val and return the subtree rooted at that node. If no such node exists, return None. This is LeetCode 700: Search in a Binary Search Tree, and it is one of the cleanest introductions to how BSTs actually work in practice.

Why this problem matters

Searching a BST is the most fundamental operation you can perform on this data structure. Every other BST problem - insertion, deletion, validation, finding the kth smallest element - builds on the same core mechanic: compare the target value to the current node, then decide whether to go left or right.

The beauty of a BST is that you never need to look at the entire tree. At each node, the BST property guarantees that all values in the left subtree are smaller and all values in the right subtree are larger. So a single comparison tells you which half of the remaining tree to explore. This is essentially binary search, but on a tree structure instead of an array.

If you can write this problem confidently, you already have the skeleton for dozens of other BST problems. The pattern is always the same: compare, decide left or right, recurse or iterate. The only thing that changes is what you do when you find the node (or do not find it).

Recursive approach

The recursive solution maps directly to the BST property. At each node, you have three possible outcomes: the value matches (return this node), the value is smaller (search left), or the value is larger (search right). If you hit a null node, the value does not exist in the tree.

def search_bst(root, val):
    if root is None:
        return None
    if val == root.val:
        return root
    if val < root.val:
        return search_bst(root.left, val)
    return search_bst(root.right, val)

That is the entire solution. Each recursive call moves one level deeper into the tree, and because you always pick exactly one child to explore, you never backtrack. The recursion stops when you either find the target or reach a null pointer.

Notice that you return the result of the recursive call directly. This is important. When the target is found three levels deep, the return value bubbles all the way back up the call stack to the original caller. You are not just checking whether the value exists - you are returning the entire subtree rooted at that node.

Iterative approach

The recursive solution is clean, but you can also write this iteratively with a simple while loop. Since each call in the recursive version is a tail call (the recursive call is the last thing the function does), it translates naturally to iteration.

def search_bst(root, val):
    node = root
    while node is not None:
        if val == node.val:
            return node
        if val < node.val:
            node = node.left
        else:
            node = node.right
    return None

The iterative version does exactly the same work. You start at the root and walk down the tree, picking left or right at each step. When you find the node, you return it. If you fall off the bottom of the tree (node becomes None), the value is not in the BST.

The advantage of the iterative approach is that it uses O(1) space. There is no call stack growing with each level of the tree. For a balanced BST this does not matter much since the stack depth would only be O(log n), but for a skewed tree with millions of nodes, avoiding recursion can prevent a stack overflow.

Complexity analysis

Here, h is the height of the tree. In the best case, the tree is balanced and h = O(log n), where n is the number of nodes. Each comparison cuts the remaining search space roughly in half, just like binary search on a sorted array.

In the worst case, the tree is completely skewed (every node has only one child, forming a straight line). Then h = O(n) and the search degrades to a linear scan. This is why balanced BST variants like AVL trees and red-black trees exist - they guarantee O(log n) height.

For this LeetCode problem, both approaches are equally valid. The iterative version has slightly better space complexity, but the recursive version is easier to write and reason about. Choose whichever feels more natural to you.

Edge cases to watch for

• Empty tree (root is None): return None immediately. The base case in both solutions handles this.
• Value not found: you walk all the way down to a null node and return None. No special handling needed.
• Single node tree: if the root's value matches, return the root. Otherwise return None. The general logic covers this.
• Root is the target: the very first comparison catches this. You return the entire tree as-is.
• Target is a leaf node: the search reaches the leaf, finds a match, and returns it. Since a leaf has no children, the returned subtree is just that single node.

The building blocks

This problem is built on one core concept: the BST search property.

In a binary search tree, every node acts as a decision point. If the value you are looking for is smaller than the current node, it can only exist in the left subtree. If it is larger, it can only exist in the right subtree. This is the same principle behind binary search on a sorted array, just applied to a tree structure.

The recursive skeleton looks like this:

def bst_search(node, target):
    if node is None:
        return None
    if target == node.val:
        return node
    if target < node.val:
        return bst_search(node.left, target)
    return bst_search(node.right, target)

This exact pattern reappears in BST insertion (search for the right spot, then attach the new node), BST deletion (search for the node, then handle removal), and problems like finding the closest value in a BST or checking if a path exists. Once you internalize the "compare and pick a side" mechanic, all of these problems become variations on the same theme.

From understanding to recall

Right now, the recursive and iterative solutions probably feel obvious. Compare the value, go left or right, done. But the gap between "this makes sense" and "I can write this in 30 seconds during an interview" is real. Under pressure, you might second-guess whether to go left when the value is smaller or larger, or forget to handle the null case, or accidentally search both subtrees instead of just one.

Spaced repetition closes that gap. You practice writing the solution from scratch at increasing intervals. After a few reps, the BST search pattern becomes automatic. And because this pattern is the foundation for nearly every other BST problem, the investment pays off across dozens of questions.

Related posts

• Validate Binary Search Tree - Uses the BST property in reverse, checking that every node satisfies the ordering constraint
• Kth Smallest Element in a BST - Combines BST search with inorder traversal to find elements by rank
• Convert Sorted Array to Binary Search Tree - Builds a balanced BST from scratch, the inverse of searching one