Complete Notes on Trees

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

Complete Notes on Trees

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

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

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:
  3. Extract two min nodes
  4. Create parent with sum
  5. Insert parent
  6. 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

Last updated: Nov 12, 2025

Complete Notes on Trees

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

Complete Notes on Trees

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

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

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:
  3. Extract two min nodes
  4. Create parent with sum
  5. Insert parent
  6. 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

Last updated: Nov 12, 2025