Binary Search Trees: How to Implement Efficient Search Using Binary Search Trees?

In daily data lookup, we often encounter the problem of “how to quickly find the target”. For example, finding a contact in an address book or a word in a dictionary. If the data is unordered, we may need to check each item one by one, which is inefficient. If the data is ordered, although binary search (O(log n)) can be used, it requires prior sorting. Is there a data structure that can maintain order while keeping insertion and lookup efficient? The answer is the Binary Search Tree (BST).

1. What is a Binary Search Tree?¶

A binary search tree is a special type of binary tree where each node has the following characteristics:
- Each node has at most left and right child nodes (left subtree and right subtree).
- For any node, all values in the left subtree are less than the node’s value.
- All values in the right subtree are greater than the node’s value.

For example, we can construct a simple binary search tree:

Here, the root node is 5. All values in the left subtree (2, 3, 4) are less than 5, and all values in the right subtree (6, 7, 8) are greater than 5. Each child node also follows the same rule, e.g., 3’s left subtree is 2 (<3), and right subtree is 4 (>3); 7’s left subtree is 6 (<7), and right subtree is 8 (>7).

2. Why Can Binary Search Trees Achieve Efficient Lookup?¶

Ordinary array lookup (unordered) requires checking each element one by one, with a time complexity of O(n). An ordered array can use binary search (O(log n)), but inserting new elements requires shifting a large amount of data. In contrast, binary search trees exclude half of the nodes with each comparison, resulting in a stable lookup efficiency of O(log n).

Why can half the nodes be excluded? Because after each comparison, the target value is either less than, greater than, or equal to the current node’s value. If it is less, we only need to continue searching in the left subtree; if it is greater, we continue in the right subtree. This is similar to looking up a word in an alphabetically sorted dictionary: you first flip to the middle page, compare the first letter, and then go to either the left or right half, rather than flipping through each page one by one.

3. The Lookup Process of a Binary Search Tree (Core)¶

The process of finding a target value is intuitive and can be implemented using the “compare and recursively narrow down the range” approach:

Start from the root node, compare the target value with the current node’s value.
If the target value equals the current node’s value: the target is found, return the current node.
If the target value is less than the current node’s value: the target must be in the left subtree, recursively search the left subtree.
If the target value is greater than the current node’s value: the target must be in the right subtree, recursively search the right subtree.
If the subtree is empty (i.e., the target is not found), return null or indicate “not found”.

Example: Looking up the target value 4¶

Assume we have the binary search tree:

Step 1: Start from the root node 5. The target 4 < 5 → enter the left subtree (rooted at 3).
Step 2: Current node is 3. The target 4 > 3 → enter the right subtree (rooted at 4).
Step 3: Current node is 4. The target 4 = 4 → found, return 4.

In this process, we only check 3 nodes (5→3→4), which is much more efficient than traversing all 7 nodes!

4. How to Implement Lookup in Code?¶

1. Recursive Implementation (Intuitive and Easy to Understand)¶

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

def search_bst(root, target):
    # Base case: node is null or target is found
    if root is None or root.val == target:
        return root
    # Target is smaller, search left subtree
    elif target < root.val:
        return search_bst(root.left, target)
    # Target is larger, search right subtree
    else:
        return search_bst(root.right, target)

2. Iterative Implementation (Using Loops Instead of Recursion)¶

def search_bst_iterative(root, target):
    current = root
    while current is not None:
        if current.val == target:
            return current
        elif target < current.val:
            current = current.left
        else:
            current = current.right
    return None  # Not found

5. Summary¶

Binary search trees achieve efficient lookup (O(log n)) by excluding half of the nodes with each comparison, thanks to their “left smaller, right larger” structure. The core steps are: start from the root node, compare the target value with the current node, and recursively narrow down to the left/right subtree.

It’s important to note that if the binary search tree is “unbalanced” (e.g., all nodes are in the left subtree, degrading into a linked list), the lookup efficiency will degenerate to O(n). However, with balancing techniques (such as red-black trees or AVL trees, which we will learn later), the efficiency can be stably maintained at O(log n).

Next time you encounter a scenario requiring fast lookup, consider the “rule-based narrowing” idea of binary search trees—it’s like installing a “navigation system” for data structures, making lookup efficient and ordered!