Unit 4: Trees

A tree is a finite set of nodes with one special node called the root, and the remaining nodes divided into disjoint subtrees.

A binary tree is a tree in which each node has at most two children: a left child and a right child.

• Strictly binary tree: every non-leaf node has exactly two children.
• Complete binary tree: all levels are full except possibly the last, which is filled from the left.
• Full (perfect) binary tree: every level is completely filled.
• Maximum nodes at level l = 2ˡ (root at level 0); maximum nodes in a tree of height h = 2ʰ − 1.

• Array (sequential) representation: root at index 1; for a node at index i, the left child is at 2i and the right child at 2i + 1; the parent is at i/2. Efficient for complete trees, wasteful for skewed trees.
• Linked representation: each node has three fields — left pointer, data, right pointer.

cstruct node {
    struct node *left;
    int data;
    struct node *right;
};

Traversal means visiting every node exactly once.

cvoid inorder(struct node *t) {
    if (t != NULL) {
        inorder(t->left);
        printf("%d ", t->data);
        inorder(t->right);
    }
}

Non-recursive traversal uses an explicit stack in place of recursion. Level-order traversal uses a queue.

• Binary search trees: fast search, insert and delete (O(log n) when balanced).
• Expression trees: represent arithmetic expressions; traversals give prefix, infix and postfix forms.
• Heaps: priority queues and heap sort.
• Huffman trees: data compression.
• B-trees and B+ trees: database and file indexes.
• Tries: dictionary and autocomplete; decision trees: machine learning; file system directories and the DOM of web pages.