Complete Notes on Trees

With C Code, Diagrams, Traversal, BST, AVL, B-Tree, Heaps, Huffman & More

---

1. Basic Terminology

Term	Definition
Node	Element in tree
Root	Top node
Parent	Node with children
Child	Node below parent
Leaf	Node with no children
Height	Longest path from root to leaf
Level	Distance from root
Degree	Number of children
Subtree	Tree rooted at a child

---

2. Binary Tree

Each node has at most 2 children.

Types of Binary Trees

Type	Definition
Strictly Binary	Every node has 0 or 2 children
Complete Binary	All levels filled except last, last filled left to right
Full Binary	Every node has 0 or 2 children
Perfect Binary	All levels completely filled

---

Representation

A. Array (Complete Binary Tree)

Index:  1   2   3   4   5   6   7
      [10, 20, 30, 40, 50, 60, 70]

• Left child of i → 2*i
• Right child → 2*i + 1
• Parent → i/2

B. Linked (Pointer)

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

---

3. Binary Search Tree (BST)

Left child < Parent < Right child

       50
      /  \
    30    70
   /  \   / \
  20  40 60  80

---

BST Operations

1. Search

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

2. Insert

struct Node* insert(struct Node* root, int key) {
    if (root == NULL) {
        struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
        newNode->data = key;
        newNode->left = newNode->right = NULL;
        return newNode;
    }
    if (key < root->data)
        root->left = insert(root->left, key);
    else if (key > root->data)
        root->right = insert(root->right, key);
    return root;
}

3. Delete

struct Node* minValueNode(struct Node* node) {
    struct Node* current = node;
    while (current && current->left != NULL)
        current = current->left;
    return current;
}

struct Node* deleteNode(struct Node* root, int key) {
    if (root == NULL) return root;
    
    if (key < root->data)
        root->left = deleteNode(root->left, key);
    else if (key > root->data)
        root->right = deleteNode(root->right, key);
    else {
        if (root->left == NULL) {
            struct Node* temp = root->right;
            free(root);
            return temp;
        } else if (root->right == NULL) {
            struct Node* temp = root->left;
            free(root);
            return temp;
        }
        struct Node* temp = minValueNode(root->right);
        root->data = temp->data;
        root->right = deleteNode(root->right, temp->data);
    }
    return root;
}

4. Inorder Traversal (Sorted Order)

void inorder(struct Node* root) {
    if (root != NULL) {
        inorder(root->left);
        printf("%d ", root->data);
        inorder(root->right);
    }
}

---

4. Tree Traversals

Order	Visit Pattern	Use
Inorder	L → Root → R	BST → Sorted
Preorder	Root → L → R	Copy, prefix
Postorder	L → R → Root	Delete, postfix

void preorder(struct Node* root) {
    if (root) {
        printf("%d ", root->data);
        preorder(root->left);
        preorder(root->right);
    }
}

void postorder(struct Node* root) {
    if (root) {
        postorder(root->left);
        postorder(root->right);
        printf("%d ", root->data);
    }
}

---

5. Construct Tree from Traversals

Inorder + Preorder or Inorder + Postorder

Example

• Inorder: 4 2 5 1 3
• Preorder: 1 2 4 5 3

Tree:

    1
   / \
  2   3
 / \
4   5

Algorithm

1. First of preorder = root
2. Find root in inorder → split left/right
3. Recurse on left/right subtrees

---

6. Threaded Binary Tree

Replace NULL pointers with threads to inorder successor/predecessor

Node Structure

struct ThreadedNode {
    int data;
    struct ThreadedNode *left, *right;
    int lthread, rthread;  // 1 = thread, 0 = child
};

Inorder Traversal (No Recursion/Stack)

void inorderThreaded(struct ThreadedNode* root) {
    struct ThreadedNode* curr = root;
    while (curr->lthread == 0) curr = curr->left;
    
    while (curr != NULL) {
        printf("%d ", curr->data);
        if (curr->rthread == 1)
            curr = curr->right;
        else {
            curr = curr->right;
            while (curr && curr->lthread == 0)
                curr = curr->left;
        }
    }
}

Space: O(1) auxiliary
Time: O(n)

---

7. Huffman Coding (Using Binary Tree)

Variable-length prefix codes for compression

Steps

1. Build min-heap of characters by frequency
2. Repeatedly:
   • Extract two min nodes
   • Create parent with sum
   • Insert parent
3. Traverse tree → assign codes

Example

Char	Freq
a	5
b	9
c	12
d	13
e	16
f	45

Huffman Tree → Codes: f:0, c:100, d:101, a:1100, b:1101, e:111

---

8. Extended Binary Tree (2-3 Tree)

Used in B-Tree representation
Internal nodes have 2 or 3 children

---

9. AVL Tree (Balanced BST)

Height-balanced: |height(left) - height(right)| ≤ 1

Rotations

Type	When
LL	Left-Left → Right Rotate
RR	Right-Right → Left Rotate
LR	Left-Right → Left then Right
RL	Right-Left → Right then Left

int height(struct Node* n) {
    return n ? n->height : 0;
}

int balanceFactor(struct Node* n) {
    return height(n->left) - height(n->right);
}

struct Node* rightRotate(struct Node* y) {
    struct Node* x = y->left;
    struct Node* T2 = x->right;
    x->right = y;
    y->left = T2;
    y->height = 1 + max(height(y->left), height(y->right));
    x->height = 1 + max(height(x->left), height(x->right));
    return x;
}

Insert/Delete: O(log n)

---

10. B-Tree

Self-balancing, multi-way search tree

Properties (Order m)

• Every node ≤ m children
• Non-leaf ≥ ⌈m/2⌉ children
• All leaves at same level

Use

• Databases, File Systems

---

11. Binary Heap (Recap)

Complete binary tree with heap property

Type	Property
Max-Heap	Parent ≥ Child
Min-Heap	Parent ≤ Child

Operations

Op	Time
Insert	O(log n)
Extract	O(log n)
Heapify	O(n)

Used in Priority Queue, Heap Sort

---

12. Summary Table

Tree	Balance	Height	Insert	Search	Use
BST	No	O(n) worst	O(log n) avg	O(log n)	Simple search
AVL	Yes	O(log n)	O(log n)	O(log n)	Strict balance
B-Tree	Yes	O(log n)	O(log n)	O(log n)	Disk
Heap	Partial	O(log n)	O(log n)	O(n)	Priority

---

13. Tree Traversal Orders

Tree	Inorder	Preorder	Postorder
BST	Sorted	Root first	Leaf first
General	L-Root-R	Root-L-R	L-R-Root

---

14. Practice Problems

1. Construct BST from preorder
2. Check if tree is height-balanced
3. Convert BST to threaded tree
4. Implement AVL insert with rotation
5. Huffman coding for string
6. B-Tree insert/delete
7. Boundary traversal of binary tree
8. Morris traversal (inorder without stack)

---

15. Key Takeaways

Concept	Insight
BST	Fast search if balanced
AVL	Always O(log n)
Heap	Priority queue
Threaded	O(1) space traversal
Huffman	Optimal compression
B-Tree	Disk-friendly
Traversal	Inorder = sorted in BST

---

End of Notes