Skip to content
Tutorials Center
My learning

Topics

Lesson 86 of 135 ยท Data Structures in C

Binary Search Trees

Build a binary search tree in C - insertion, search, in-order and level-order traversals, the three deletion cases, freeing the tree, and why balance matters.

A linked list gives every node one successor, so finding a value means walking the chain, one node at a time. A binary tree gives every node up to two children, a left one and a right one. Add one ordering rule and you get a binary search tree (BST): everything in a node's left subtree is smaller than the node, and everything in its right subtree is larger. Now each comparison throws away a whole half of the remaining tree, the same idea as binary search in a sorted array.

A balanced BST with a million keys finds any of them in about 20 comparisons, and unlike a sorted array it accepts insertions and deletions without shifting anything. In this lesson you'll build one in C: insertion, search, the four standard traversals, deletion (the tricky part), freeing, and a string-keyed version that counts words. You'll also see the BST's weak spot, balance, and what real libraries do about it.

Tree vocabulary

TEXT
              50          โ† root (depth 0)
            /    \
          30      70      โ† children of 50
         /  \       \
       20    40      80   โ† 20, 40 and 80 are leaves (no children)
  • The root is the top node; every other node has exactly one parent.
  • A node with no children is a leaf.
  • A node plus everything below it forms a subtree. The left subtree of 50 is {30, 20, 40}.
  • The height of a tree is the number of nodes on its longest root-to-leaf path. The tree above has height 3. (Some books count edges instead, giving 2; just be consistent.)

The BST rule holds at every node: 20 and 40 are less than 50, and also on the correct sides of 30. This lesson's trees reject duplicate keys; if you need duplicates, store a count in the node (as the word counter below does) instead of inserting the key again.

A tree node is a struct with two child pointers, and the tree itself is a pointer to the root (NULL for an empty tree):

C
struct tree_node {
    int key;
    struct tree_node *left;    /* keys smaller than key */
    struct tree_node *right;   /* keys larger than key */
};

To search, start at the root and go left or right depending on the comparison until you either find the key or fall off the tree (reach NULL). Insertion is the same walk; when you fall off, that empty spot is exactly where the new key belongs. Trees are recursive by nature (each child is the root of a smaller tree), so recursive functions are natural, but the walk itself is easy to write as a loop. The insert below uses the same pointer-to-pointer trick as the linked list lesson: link points at the child pointer that will receive the new node.

C Insert, search, min, max and height

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with scanf or fgets), it gets the next line from this box.

The second 40 is rejected as a duplicate. Finding 60 takes 3 comparisons (50 โ†’ 70 โ†’ 60), and 55 is reported missing after 3 comparisons too, because the search falls off below 60. The minimum is always the leftmost node and the maximum the rightmost, with no comparisons needed. tree_height and tree_free are recursive: each handles one node and lets the recursion handle the subtrees. Freeing must visit the children before the parent, because once the parent is freed its child pointers can't be read anymore.

Note: Recursion depth equals tree height. For a balanced tree that's tiny (about 40 levels for a trillion nodes), but a degenerate tree shaped like a list can be as tall as it has nodes, and a recursive function on it can overflow the stack. You'll see such a tree at the end of this lesson.

Traversals

Traversing a tree means visiting every node once. With a list there's only one sensible order; with a tree there are several, each useful for something different:

Order Visits Typical use
In-order left subtree, node, right subtree Prints a BST's keys sorted
Pre-order node, left, right Copying or saving a tree so it can be rebuilt in the same shape
Post-order left, right, node Freeing a tree, evaluating expression trees
Level-order row by row, top to bottom Printing by depth, shortest paths; uses a queue

The first three are depth-first and fall out naturally from recursion: the only difference is where the "visit" line sits relative to the two recursive calls. Level-order is breadth-first and uses the queue you built in Stacks and Queues. This example also prints the tree sideways, which is a handy debugging aid:

C Four traversals of the same tree

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with scanf or fgets), it gets the next line from this box.

The traversal lines are:

TEXT
in-order:    20 30 35 40 50 60 70 80
pre-order:   50 30 20 40 35 70 60 80
post-order:  20 35 40 30 60 80 70 50
level-order: 50 30 70 20 40 60 80 35

In-order is sorted, as promised: a BST is effectively a sorted list you can update cheaply. Pre-order starts with the root, so inserting keys in pre-order rebuilds this exact shape. Post-order ends with the root, which is why freeing uses it.

This insert shows the other common recursive style: it returns the (possibly new) root of the subtree, and the caller stores it, node->left = insert(node->left, key). It needs no double pointers, and the same style makes deletion much easier, as you're about to see.

Deleting a node

Deletion has three cases, depending on how many children the doomed node has:

  1. No children (a leaf): just remove it; its parent's pointer becomes NULL.
  2. One child: the child takes the node's place, like unlinking a list node.
  3. Two children: you can't give the parent two replacements. Instead, find the node's in-order successor, the smallest key in its right subtree (go right once, then left as far as possible). Copy that key into the node, then delete the successor from the right subtree. The successor never has a left child, so that second deletion is case 1 or 2.

Using the successor works because it's the next larger key: it's bigger than everything on the left and smaller than everything else on the right, so the BST rule still holds. (The in-order predecessor, the largest key on the left, works equally well.)

C Deleting with all three cases

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with scanf or fgets), it gets the next line from this box.

The keys stay sorted after every deletion. Deleting 60 lets its only child, 65, move up. Deleting the root 50 is case 3: its successor is the smallest key in the right subtree, 65, so the root becomes 65 (root=65 in the output) and the old 65 node is removed. Deleting a missing key leaves the tree unchanged, because the recursion simply reaches NULL.

A BST as a map: counting words

Trees really pay off as ordered maps: a key with a value attached, kept sorted. Here the keys are words compared with strcmp, and each node stores a count. An in-order walk then prints the words alphabetically for free, something a hash table can't do without sorting.

C Word counts in alphabetical order

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with scanf or fgets), it gets the next line from this box.

the appears 4 times, cat 3 times, and a twice because the input was lowercased first (A and a are different char values, so you must normalize them yourself; see Characters and ASCII). Each node owns its copy of the word, so freeing a node means freeing the string too.

The balance problem

Everything above assumed the tree is reasonably balanced, with a height near logโ‚‚(n). The BST rule alone doesn't guarantee that. Insert keys that are already sorted and every new key becomes the right child of the previous one: the "tree" degenerates into a linked list with extra pointers, and search becomes O(n).

C Sorted input ruins the shape

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with scanf or fgets), it gets the next line from this box.

Sorted insertion produces height 1023: a search for the largest key makes 1,023 comparisons. The scrambled order gives height 16: taller than the ideal 10, but only by a small factor, and every search stays fast. Because the degenerate tree is so deep, this example frees it with an iterative loop that rotates left children upward, so no recursion can overflow the stack.

Real-world code avoids the problem with self-balancing trees, which restructure themselves with small local rotations during insertion and deletion to keep the height O(log n):

  • AVL trees keep the heights of every node's two subtrees within 1 of each other. Lookups are very fast.
  • Red-black trees use a looser coloring rule, so insertions and deletions do less rebalancing. Linux's kernel (rbtree.h), C++'s std::map and Java's TreeMap use them.
  • B-trees give each node many keys and children; databases and file systems use them because they match disk and cache block sizes.

C's standard library has no tree type. POSIX offers tsearch/tfind/tdelete in <search.h>, and glibc implements them as a red-black tree, but most C projects either write their own or use a small library. If you don't need ordering, a hash table is usually simpler and faster.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Keys are inserted in this order: 40, 20, 60, 10, 30. What does an in-order traversal print?

    An in-order traversal of any binary search tree visits the keys in sorted order.
  2. 2. Which traversal should you use to free every node of a tree?

    After a parent is freed, its left and right pointers can't be read. Post-order handles both subtrees first.
  3. 3. You delete a node that has two children. Which key replaces it?

    The successor is larger than everything on the left and smaller than the rest of the right subtree, so the BST rule still holds. The in-order predecessor would also work.
  4. 4. What happens to a plain BST if you insert 1, 2, 3, ..., 1000 in that order?

    Each key is larger than all previous ones, so it always goes right. Self-balancing trees (AVL, red-black) exist to prevent this.
  5. 5. In the tree 50 / 30, 70 / 20, 40, 80, how many key comparisons does searching for 45 need before it concludes 45 is missing?

    45 is compared with 50 (go left), 30 (go right) and 40 (go right). The right child of 40 is NULL, so after 3 comparisons the search stops.

Summary

  • A binary search tree stores smaller keys in the left subtree and larger keys in the right subtree of every node.
  • Search and insert walk down from the root, one comparison per level; a new key goes where the search falls off the tree.
  • In-order traversal visits keys in sorted order; pre-order preserves shape; post-order frees safely; level-order uses a queue.
  • Deletion: remove a leaf, replace a one-child node with its child, and for two children copy in the in-order successor and delete that instead.
  • Recursive functions that return the new subtree root (node->left = insert(node->left, key)) keep insertion and deletion short.
  • Operations cost O(height). Sorted input makes a plain BST degenerate into a list; AVL and red-black trees rebalance to keep O(log n).

Next: Hash Tables, the structure behind dictionaries and sets, with average O(1) lookups.