Trees

Introduction

A tree is a non-linear, hierarchical data structure. It consists of nodes connected by edges, with one node designated as the root. Each non-root node has exactly one parent, and can have zero or more children.

Terminology

• Root — topmost node.
• Leaf — node with no children.
• Parent / Child — direct ancestor / descendant.
• Siblings — nodes sharing the same parent.
• Depth of a node — number of edges from root to node.
• Height of a tree — longest path from root to any leaf.
• Subtree — a node together with all its descendants.

Binary Tree

A binary tree is a tree where every node has at most two children, called left and right.

struct TreeNode {
    int data;
    struct TreeNode *left, *right;
};

Types of Binary Trees

• Full — every node has 0 or 2 children.
• Complete — all levels filled except possibly the last, which is filled left to right.
• Perfect — all internal nodes have 2 children and all leaves are on the same level.
• Balanced — left and right subtree heights differ by at most one for every node.

Tree Traversals

Three standard depth-first traversals for binary trees:

• Inorder (LNR): left subtree, node, right subtree.
• Preorder (NLR): node, left, right.
• Postorder (LRN): left, right, node.
• Level-order (BFS): visit level by level using a queue.

void inorder(Node* r) {
    if (!r) return;
    inorder(r->left);
    printf("%d ", r->data);
    inorder(r->right);
}

Binary Search Tree (BST)

A BST is a binary tree with the BST property: for every node, values in the left subtree are less, and values in the right subtree are greater. This gives O(log n) search, insert, and delete on a balanced tree.

Node* search(Node* root, int key) {
    if (!root || root->data == key) return root;
    if (key < root->data) return search(root->left, key);
    return search(root->right, key);
}

BST Insertion and Deletion

Insertion walks down the tree comparing keys and attaches the new node at the first empty slot. Deletion has three cases: leaf (remove directly), one child (bypass), two children (replace with inorder successor).

AVL Tree

An AVL tree is a self-balancing BST where the balance factor (height of left minus height of right subtree) of every node is -1, 0, or +1. After insert or delete, the tree is rebalanced with single or double rotations (LL, RR, LR, RL). All operations are O(log n) worst case.

Applications

1. File systems (directory hierarchy).
2. Databases (B-trees, B+-trees for indexes).
3. Expression trees.
4. Huffman coding trees for compression.
5. Syntax trees in compilers.
6. Decision trees in machine learning.

Summary

Trees capture hierarchical relationships and allow efficient search, sort, and navigation. BSTs give O(log n) operations when balanced; AVL and red-black trees guarantee balance automatically.

Important Questions

1. Define tree and explain terms: root, leaf, depth, height.
2. What is a binary tree? List its types.
3. Explain inorder, preorder, and postorder traversals with an example.
4. Define BST. Write an algorithm to search in a BST.
5. Insert the keys 50, 30, 70, 20, 40 into an empty BST and show the tree.
6. Delete a node with two children from a BST. Explain the algorithm.
7. What is an AVL tree? Explain rotations.
8. List applications of trees.