Unit 2: 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.

• Proof of n0 = n2 + 1: total nodes n = n0 + n1 + n2; every node except the root has one incoming edge, so edges = n − 1 = n1 + 2n2. Equating gives n0 = n2 + 1.

• Terminology varies between textbooks: some call the second form "complete" and the first "full" or "perfect".

• 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.

c/* Non-recursive inorder traversal using an explicit stack */
void inorderIter(struct node *root) {
    struct node *stack[100]; int top = -1;
    struct node *cur = root;
    while (cur != NULL || top != -1) {
        while (cur != NULL) { stack[++top] = cur; cur = cur->left; }   /* go left */
        cur = stack[top--];
        printf("%d ", cur->data);                                      /* visit */
        cur = cur->right;                                              /* go right */
    }
}

• An expression tree has operands at leaves and operators at internal nodes; traversals give prefix (preorder), infix (inorder, with brackets) and postfix (postorder) forms.

In a linked binary tree with n nodes, n + 1 pointers are NULL. A threaded binary tree replaces these NULL pointers with threads — pointers to the inorder predecessor (left) or successor (right). This allows inorder traversal without a stack or recursion. Each node keeps a flag to tell a thread from a real child link.

• A forest is a set of disjoint trees. Removing the root of a tree gives a forest of its subtrees.
• Converting a forest (or general tree) to a binary tree — left-child, right-sibling: each node's first child becomes its left child, and its next sibling becomes its right child; the roots of the trees are linked as right siblings.
• Forest traversals: preorder of the forest equals preorder of its binary-tree form; inorder (postorder of the forest) equals inorder of the binary form.

A heap is a complete binary tree that satisfies the heap property:

• Max-heap: every parent ≥ its children; the largest value is at the root.
• Min-heap: every parent ≤ its children; the smallest value is at the root.

Heaps are stored in arrays and are used for priority queues and heap sort.

Heap sort runs in O(n log n) time in all cases.