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

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 binary search tree is a binary tree in which, for every node, all values in the left subtree are smaller and all values in the right subtree are larger. Inorder traversal of a BST gives the values in sorted order.

• Insertion: search for the key; insert the new node where the search ends (at a NULL link).
• Deletion — three cases: (1) leaf node: just remove it; (2) one child: link the parent to that child; (3) two children: replace the node with its inorder successor (smallest in the right subtree) or predecessor, then delete that node.
• Search, insert and delete take O(h) time: O(log n) for a balanced tree, O(n) for a skewed one.