Trees and binary search trees

Learning outcomes

Classify binary trees, trace recursive and iterative traversals, and explain how BST shape controls performance.

10.1 Tree vocabulary

A tree is a connected acyclic structure. In a rooted tree, each non-root node has one parent; nodes may have children. A leaf has no children. The depth of a node is the number of edges from the root. In this book, the height of a nonempty tree is the maximum number of edges from its root to a leaf; a leaf has height zero. Implementations may store node-count heights instead, provided their formulas remain consistent.

A binary tree gives each node at most a left and a right child. Full means every node has zero or two children. Complete means all levels except possibly the last are full, and the last fills left to right. Perfect means every internal node has two children and all leaves have the same depth. A skewed tree can have height n − 1.

10.2 Representation

A linked node contains a key, a left pointer and a right pointer. A zero-based array representation places the children of index i at 2i + 1 and 2i + 2, if those positions exist. The parent of a non-root index i is (i − 1)/2 using integer division. This is efficient for complete trees such as binary heaps, but sparse shapes can waste array positions.

10.3 Traversal orders

In recursive traversal, return immediately for a null pointer. Each real node is visited once, so time is Θ(n). Auxiliary call-stack space is O(h + 1), where h is the edge-count height of a nonempty tree. This includes the one-frame requirement for a leaf with h = 0. It can be O(n) for a skewed tree. Level-order traversal uses a queue whose size is proportional to the maximum width.

For iterative inorder, keep a stack and current pointer. Push current and move left until null; pop a node and visit it; then set current to its right child. Repeat while current is non-null or the stack is nonempty. The explicit stack preserves the same pending work as recursion.

10.4 Binary search tree operations

A BST maintains an ordering rule: all keys in a node's left subtree are smaller, and all keys in its right subtree are larger. The labs ignore duplicate keys. Other policies are possible, such as storing a frequency, but must be stated explicitly.

Search compares the requested key with the current key and descends into only one child. Insertion follows that path until it reaches an empty link, where it attaches a new node. Inorder traversal yields sorted keys because of the BST invariant, not merely because the tree is binary.

Deletion has three cases:

1. Leaf: remove its link from the parent.
2. One child: replace the node's link with its child.
3. Two children: copy the inorder successor's key (the minimum in the right subtree), then delete that successor from its original position. The successor has no left child.

If nodes store records rather than isolated keys, copy or transfer the associated payload consistently. If deleting the root, update the root pointer. Release each removed allocation exactly once.

10.5 Shape and complexity

Search, insertion and deletion follow paths of length O(h). Balanced height gives O(log n); a skewed BST gives O(n). Inserting sorted keys into an ordinary BST can produce a chain. A tree does not become balanced merely because it is a binary search tree.

A binary heap instead maintains a parent–child priority relation and a complete shape. It does not enforce the full BST ordering rule. A heap is suitable for priority queues; a BST is suitable for ordered search. AVL trees enforce balance explicitly in Chapter 14.

Practice

1. Write the preorder, inorder and postorder for root 8 with left child 3 and right child 10, where 3 has right child 6.
2. Insert 10, 20, 30 and 40 into an ordinary BST. What is its height?
3. Delete root 40 from Figure 10.1 using its inorder successor.
4. Explain why postorder is a natural order for freeing every node of a linked tree.
5. Give a tree that is full but not complete.

/* C11. binary search tree. Duplicate keys are ignored. */
#include <assert.h>
#include <stdbool.h>
#include <stddef.h>
#include <stdio.h>
#include <stdlib.h>

typedef struct Node { int key; struct Node *left, *right; } Node;
static bool insert(Node **root, int key)
{
    while (*root != NULL) {
        if (key == (*root)->key) return true;
        root = key < (*root)->key ? &(*root)->left : &(*root)->right;
    }
    Node *node = malloc(sizeof *node);
    if (node == NULL) return false;
    *node = (Node){key, NULL, NULL}; *root = node;
    return true;
}
static bool contains(const Node *root, int key)
{
    while (root != NULL) {
        if (key == root->key) return true;
        root = key < root->key ? root->left : root->right;
    }
    return false;
}
/* Collect traversals; caller provides capacity at least the number of nodes. */
static void inorder(const Node *r, int out[], size_t *n)
{
    if (r == NULL) return;
    inorder(r->left, out, n); out[(*n)++] = r->key; inorder(r->right, out, n);
}
static void preorder(const Node *r, int out[], size_t *n)
{
    if (r == NULL) return;
    out[(*n)++] = r->key; preorder(r->left, out, n); preorder(r->right, out, n);
}
static void postorder(const Node *r, int out[], size_t *n)
{
    if (r == NULL) return;
    postorder(r->left, out, n); postorder(r->right, out, n); out[(*n)++] = r->key;
}
static void destroy(Node *root)
{
    if (root == NULL) return;
    destroy(root->left); destroy(root->right); free(root);
}
static void show(const char *label, const int out[], const int expected[], size_t n)
{
    printf("%s:", label);
    for (size_t i = 0; i < n; ++i) { assert(out[i] == expected[i]); printf(" %d", out[i]); }
    putchar('\n');
}
int main(void)
{
    Node *root = NULL;
    int keys[] = {40, 20, 60, 10, 30, 50, 70};
    int in[] = {10, 20, 30, 40, 50, 60, 70};
    int pre[] = {40, 20, 10, 30, 60, 50, 70};
    int post[] = {10, 30, 20, 50, 70, 60, 40};
    int out[7]; size_t n = 0;
    assert(!contains(root, 40)); inorder(root, out, &n); assert(n == 0);
    for (size_t i = 0; i < 7; ++i)
        if (!insert(&root, keys[i])) { destroy(root); return EXIT_FAILURE; }
    assert(insert(&root, 40)); assert(contains(root, 50)); assert(!contains(root, 55));
    inorder(root, out, &n); assert(n == 7); show("Inorder", out, in, n);
    n = 0; preorder(root, out, &n); assert(n == 7); show("Preorder", out, pre, n);
    n = 0; postorder(root, out, &n); assert(n == 7); show("Postorder", out, post, n);
    destroy(root); root = NULL; destroy(root);
    assert(insert(&root, 1)); n = 0;
    inorder(root, out, &n); assert(n == 1 && out[0] == 1);
    assert(insert(&root, 2) && insert(&root, 3)); n = 0;
    inorder(root, out, &n); assert(n == 3 && out[0] == 1 && out[2] == 3);
    destroy(root);
    puts("BST tests passed");
    return EXIT_SUCCESS;
}