Unit 2 · Lesson 418 minAcademic review pending

The ordering rule that makes search fast

A BST is a binary tree with one extra rule: left is always smaller, right is always bigger. That single rule turns search into a guessing game you can win in a handful of moves.

Choose explanation

After this lesson

You should be able to

State the BST property precisely.
Write a recursive search function and trace it on a small tree.
Explain why search cost depends on height, not on the number of nodes.

Try it before you read

Try it live

bst.c0 node(s)

Empty tree — insert a value to begin.

The rule, stated precisely

A binary search tree adds one requirement on top of Lesson 1's plain binary tree: for every node, every value in its left subtree is smaller, and every value in its right subtree is bigger. Not just the immediate children — the entire subtree, at every depth.

That single rule is what makes Lesson 3's inorder traversal come out sorted, and it is what makes the search below possible at all.

Search as a guessing game

You have played the higher-lower number guessing game: someone picks a number, you guess, they say higher or lower, and you narrow in. Searching a BST is exactly that game, except the tree has already pre-computed every comparison you would ever need — each node is a guess someone already made, with the answer routing you left or right.

Compare the target to the current node. Equal means found. Smaller means the answer, if it exists, must be in the left subtree — the entire right subtree is eliminated in one comparison. Bigger eliminates the entire left subtree the same way. Hit NULL and the value is not there.

One comparison, one elimination, every step

struct Node *search(struct Node *node, int target)
{
    if (node == NULL || node->data == target)
        return node;

    if (target < node->data)
        return search(node->left, target);
    else
        return search(node->right, target);
}

Why height, not size, sets the cost

Each comparison eliminates one entire subtree, so the number of comparisons search needs is at most the height of the tree — not the number of nodes in it. On a tree shaped like a wide, shallow triangle, a million nodes might only be twenty levels deep, meaning search takes roughly twenty comparisons, not a million.

This is the entire reason a BST beats Unit I's linear list for lookups: a list has no shortcuts, so search there costs the full length every time. A balanced tree turns that same cost from proportional-to-size into proportional-to-the-logarithm-of-size — Lesson 8 exists because that promise breaks the moment the tree stops being balanced.

Try it yourself

Rewrite search as an iterative function using a while loop instead of recursion, matching the style of Unit I's linked-list traversal.

Need a hint?

Walk a plain pointer down the tree, reassigning it to left or right each time, and stop on NULL or a match.

Check the worked solution

Both versions do the identical work — same comparisons, same path — because recursion here is just the call stack doing the walking for you. The iterative version makes that walking explicit with your own pointer, which is exactly the recursion-to-loop translation from CS105ES.

struct Node *search_iterative(struct Node *node, int target)
{
    while (node != NULL && node->data != target) {
        node = (target < node->data) ? node->left : node->right;
    }
    return node;
}

Quick check

A BST holds one million nodes but is perfectly balanced, about 20 levels deep. Roughly how many comparisons does a search need in the worst case?

Select an answer to check your thinking.

Why this lesson exists

Syllabus mapping

Binary Search Trees (BST) · BST Operations- Searching · BST ADT

Maps to course outcomes CO1, CO2, CO4.