---

PART 1: INTRODUCTION TO TREES

1.1 What is a Tree?

A tree is a hierarchical data structure consisting of nodes connected by edges. Unlike arrays, linked lists, stacks, and queues which are linear, trees are non-linear data structures.

Formal Definition: A tree is a finite set of one or more nodes such that:

1. There is a specially designated node called the root

2. The remaining nodes are partitioned into n ≥ 0 disjoint sets, each of which is a tree (called subtrees)

Real-life Examples:

• Family tree (ancestors/descendants)

• Organizational chart

• File system directories

• HTML DOM structure

---

1.2 Basic Tree Terminologies

Term	Definition	Example
Node	Each data element in a tree	A, B, C in diagram
Root	Topmost node with no parent	Node A
Parent	Node that has children	A is parent of B, C
Child	Node directly below another	B, C are children of A
Siblings	Nodes with same parent	B and C are siblings
Leaf	Node with no children	D, E, F, G
Internal Node	Node with at least one child	A, B, C
Degree of Node	Number of children	A has degree 2
Degree of Tree	Maximum degree among all nodes	Tree degree = 3
Edge	Connection between two nodes	Line between A-B
Path	Sequence of edges from source to destination	A→B→D
Path Length	Number of edges in path	A to D length = 2
Height of Node	Longest path from node to leaf	Height of B = 1
Height of Tree	Height of root node	Tree height = 2
Depth of Node	Path length from root to node	Depth of D = 2
Level	Root at level 0, children at level 1, etc.
Subtree	Any node with its descendants

Diagram Example:

        A (Root, Level 0)
       / \
      B   C (Level 1)
     / \   \
    D   E   F (Level 2)
       /
      G (Level 3)

Terminology Applied:
- Root: A
- Leaves: D, G, F
- Internal nodes: A, B, C, E
- Parent of G: E
- Children of B: D, E
- Siblings: D and E are siblings
- Height of tree: 3 (path A→B→E→G)
- Depth of G: 3
- Degree of node B: 2
- Degree of tree: 2 (maximum children any node has)

---

1.3 Types of Trees

Trees are classified based on various properties:

Based on Degree:

1. Binary Tree - Maximum degree 2

2. Ternary Tree - Maximum degree 3

3. N-ary Tree - Maximum degree N

Based on Balancing:

1. Binary Search Tree (BST) - Ordered but may be unbalanced

2. AVL Tree - Self-balancing BST

3. Red-Black Tree - Approximately balanced BST

Based on Special Properties:

1. Threaded Binary Tree - Uses NULL pointers for threading

2. B Tree - Multi-way balanced tree for disks

3. B+ Tree - Variant of B Tree with data only at leaves

4. Heap - Complete binary tree for priority queue

---

PART 2: LINKED LISTS (Prerequisite for Trees)

2.1 Introduction to Linked Lists

A linked list is a linear data structure where elements are stored in nodes, and each node points to the next node.

Comparison with Arrays:

Feature	Array	Linked List
Memory allocation	Contiguous	Non-contiguous
Access time	O(1) random access	O(n) sequential access
Insertion/Deletion	O(n) - shifting needed	O(1) at head, O(n) at position
Memory utilization	Wastage if fixed size	Dynamic, no wastage
Cache performance	Better (locality)	Poorer

2.2 Types of Linked Lists

2.2.1 Singly Linked List

Each node has data and a pointer to the next node.

Node Structure:

struct Node {
    int data;
    struct Node* next;
};

Diagram:

[data|next] → [data|next] → [data|next] → NULL

2.2.2 Doubly Linked List

Each node has data, pointer to next, and pointer to previous.

Node Structure:

struct Node {
    int data;
    struct Node* prev;
    struct Node* next;
};

Diagram:

NULL ← [prev|data|next] ↔ [prev|data|next] ↔ [prev|data|next] → NULL

2.2.3 Circular Linked List

Last node points back to first node.

Diagram:

[data|next] → [data|next] → [data|next]
  ↑___________________________________|

2.3 Singly Linked List Operations with Algorithms

2.3.1 Creating a Node

struct Node* createNode(int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

Time Complexity: O(1)

2.3.2 Traversal

Algorithm:

Step 1: Set current = head
Step 2: While current != NULL
    Step 2.1: Print current.data
    Step 2.2: Set current = current.next
Step 3: End

Time Complexity: O(n)

2.3.3 Insertion at Beginning

Algorithm:

Step 1: Create newNode with given data
Step 2: Set newNode.next = head
Step 3: Set head = newNode

Time Complexity: O(1)

Example:

Before: head → [10] → [20] → NULL
Insert 5 at beginning:
Step 1: [5|next]
Step 2: [5] → [10] → [20] → NULL
Step 3: head → [5] → [10] → [20] → NULL

2.3.4 Insertion at End

Algorithm:

Step 1: Create newNode with given data
Step 2: If head == NULL
            head = newNode
            return
Step 3: Set current = head
Step 4: While current.next != NULL
            current = current.next
Step 5: Set current.next = newNode

Time Complexity: O(n)

Example:

Before: head → [10] → [20] → NULL
Insert 30 at end:
current goes to 20
20.next = newNode(30)
Result: head → [10] → [20] → [30] → NULL

2.3.5 Insertion at Position

Algorithm:

Step 1: Create newNode with given data
Step 2: If position == 1
            newNode.next = head
            head = newNode
            return
Step 3: Set current = head
Step 4: For i = 1 to position-2
            current = current.next
            if current == NULL
                print "Invalid position"
                return
Step 5: newNode.next = current.next
Step 6: current.next = newNode

Time Complexity: O(n)

2.3.6 Deletion from Beginning

Algorithm:

Step 1: If head == NULL
            print "List empty"
            return
Step 2: Set temp = head
Step 3: Set head = head.next
Step 4: free(temp)

Time Complexity: O(1)

2.3.7 Deletion from End

Algorithm:

Step 1: If head == NULL
            print "List empty"
            return
Step 2: If head.next == NULL
            free(head)
            head = NULL
            return
Step 3: Set current = head
Step 4: While current.next.next != NULL
            current = current.next
Step 5: free(current.next)
Step 6: Set current.next = NULL

Time Complexity: O(n)

2.3.8 Deletion by Value

Algorithm:

Step 1: If head == NULL
            print "List empty"
            return
Step 2: If head.data == key
            temp = head
            head = head.next
            free(temp)
            return
Step 3: Set current = head
Step 4: While current.next != NULL AND current.next.data != key
            current = current.next
Step 5: If current.next == NULL
            print "Key not found"
            return
Step 6: temp = current.next
Step 7: current.next = temp.next
Step 8: free(temp)

Time Complexity: O(n)

2.3.9 Search

Algorithm:

Step 1: Set current = head, position = 1
Step 2: While current != NULL
            if current.data == key
                return position
            current = current.next
            position++
Step 3: return -1 (not found)

Time Complexity: O(n)

2.4 Complexity Analysis Summary

Operation	Singly Linked List	Doubly Linked List	Array
Access by index	O(n)	O(n)	O(1)
Insert at beginning	O(1)	O(1)	O(n)
Insert at end	O(n)	O(1) with tail	O(1) amortized
Insert at position	O(n)	O(n)	O(n)
Delete from beginning	O(1)	O(1)	O(n)
Delete from end	O(n)	O(1) with tail	O(1)
Delete by value	O(n)	O(n)	O(n)
Search	O(n)	O(n)	O(n) linear / O(log n) sorted

---

PART 3: BINARY TREE

3.1 Definition

A binary tree is a tree data structure in which each node has at most two children, referred to as the left child and right child.

Recursive Definition: A binary tree is either:

1. Empty, OR

2. Consists of a root node with two disjoint binary trees called left subtree and right subtree

Node Structure:

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

3.2 Properties of Binary Trees

1. Maximum nodes at level i: 2ⁱ (where i ≥ 0, root at level 0)

2. Maximum nodes in tree of height h: 2ʰ⁺¹ - 1

3. Minimum height of tree with n nodes: ⌈log₂(n+1)⌉ - 1

4. Maximum height of tree with n nodes: n - 1 (skewed tree)

5. Number of leaf nodes: n₀ = n₂ + 1 (where n₂ = nodes with 2 children)

3.3 Types of Binary Trees

3.3.1 Full Binary Tree (Strict Binary Tree)

A binary tree where every node has either 0 or 2 children.

Example:

        A
       / \
      B   C
     / \
    D   E

Properties:

• Number of leaf nodes = number of internal nodes + 1

• Total nodes = 2L - 1 (where L = number of leaves)

3.3.2 Complete Binary Tree

A binary tree where all levels except possibly the last are completely filled, and all nodes in the last level are as far left as possible.

Example:

        A
       / \
      B   C
     / \ /
    D  E F

Properties:

• Can be stored efficiently in an array

• For node at index i:

  • Left child at 2i+1

  • Right child at 2i+2

  • Parent at floor((i-1)/2)

3.3.3 Perfect Binary Tree

A binary tree where all internal nodes have two children and all leaves are at the same level.

Example:

        A
       / \
      B   C
     / \ / \
    D  E F  G

Properties:

• All levels completely filled

• If height = h, total nodes = 2ʰ⁺¹ - 1

• Number of leaf nodes = 2ʰ

3.3.4 Balanced Binary Tree

A binary tree where the height of left and right subtrees of every node differ by at most 1.

Example:

        A
       / \
      B   C
     / \   \
    D   E   F

(AVL tree is a balanced binary tree)

3.3.5 Skewed Binary Tree

A binary tree where every node has only one child (left or right).

Left Skewed:

    A
   /
  B
 /
C

Right Skewed:

A
 \
  B
   \
    C

3.4 Binary Tree Traversals

3.4.1 Depth-First Traversals (DFS)

Inorder Traversal (LNR): Left → Node → Right

Recursive Algorithm:

inorder(node):
    if node == NULL: return
    inorder(node.left)
    print node.data
    inorder(node.right)

Iterative Algorithm (using stack):

inorder_iterative(root):
    stack = empty
    current = root
    
    while current != NULL OR stack not empty:
        while current != NULL:
            stack.push(current)
            current = current.left
        
        current = stack.pop()
        print current.data
        current = current.right

Example:

        A
       / \
      B   C
     / \   \
    D   E   F

Inorder: D → B → E → A → C → F

Preorder Traversal (NLR): Node → Left → Right

Recursive Algorithm:

preorder(node):
    if node == NULL: return
    print node.data
    preorder(node.left)
    preorder(node.right)

Iterative Algorithm:

preorder_iterative(root):
    if root == NULL: return
    stack.push(root)
    
    while stack not empty:
        current = stack.pop()
        print current.data
        
        if current.right: stack.push(current.right)
        if current.left: stack.push(current.left)

Example:

Preorder: A → B → D → E → C → F

Postorder Traversal (LRN): Left → Right → Node

Recursive Algorithm:

postorder(node):
    if node == NULL: return
    postorder(node.left)
    postorder(node.right)
    print node.data

Iterative Algorithm (using two stacks):

postorder_iterative(root):
    if root == NULL: return
    stack1.push(root)
    stack2 = empty
    
    while stack1 not empty:
        current = stack1.pop()
        stack2.push(current)
        
        if current.left: stack1.push(current.left)
        if current.right: stack1.push(current.right)
    
    while stack2 not empty:
        print stack2.pop().data

Example:

Postorder: D → E → B → F → C → A

3.4.2 Breadth-First Traversal (Level Order)

Algorithm (using queue):

level_order(root):
    if root == NULL: return
    queue.enqueue(root)
    
    while queue not empty:
        current = queue.dequeue()
        print current.data
        
        if current.left: queue.enqueue(current.left)
        if current.right: queue.enqueue(current.right)

Example:

Level Order: A → B → C → D → E → F

3.4.3 Traversal Comparison Table

Traversal	Order	Application
Inorder	Left-Root-Right	Gives sorted order in BST
Preorder	Root-Left-Right	Tree copying, prefix expressions
Postorder	Left-Right-Root	Tree deletion, postfix expressions
Level Order	Level by level	Finding height, BFS

Time Complexity: O(n) for all traversals Space Complexity: O(h) for DFS (h = height), O(w) for BFS (w = max width)

3.5 Binary Tree Operations

3.5.1 Creating a Binary Tree

struct Node* createNode(int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

3.5.2 Insertion in Binary Tree

In a general binary tree (not BST), we typically insert at the first available position using level order.

void insert(struct Node* root, int data) {
    if (root == NULL) {
        root = createNode(data);
        return;
    }
    
    queue.enqueue(root);
    
    while (!queue.isEmpty()) {
        struct Node* temp = queue.dequeue();
        
        if (temp->left == NULL) {
            temp->left = createNode(data);
            return;
        } else {
            queue.enqueue(temp->left);
        }
        
        if (temp->right == NULL) {
            temp->right = createNode(data);
            return;
        } else {
            queue.enqueue(temp->right);
        }
    }
}

Time Complexity: O(n)

3.5.3 Searching in Binary Tree

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

Time Complexity: O(n)

3.5.4 Finding Height of Tree

int height(struct Node* root) {
    if (root == NULL) return -1; // -1 for edges, 0 for nodes count
    
    int leftHeight = height(root->left);
    int rightHeight = height(root->right);
    
    return max(leftHeight, rightHeight) + 1;
}

Time Complexity: O(n)

3.5.5 Counting Nodes

int countNodes(struct Node* root) {
    if (root == NULL) return 0;
    return 1 + countNodes(root->left) + countNodes(root->right);
}

Time Complexity: O(n)

3.5.6 Counting Leaf Nodes

int countLeaves(struct Node* root) {
    if (root == NULL) return 0;
    if (root->left == NULL && root->right == NULL) return 1;
    
    return countLeaves(root->left) + countLeaves(root->right);
}

Time Complexity: O(n)

3.6 Applications of Binary Trees

Application	How Binary Tree is Used
Expression Trees	Represent arithmetic expressions with operators as internal nodes and operands as leaves
Huffman Coding	Binary trees for data compression
Binary Search Trees	Efficient searching, insertion, deletion
Heap Data Structure	Complete binary tree for priority queues
Syntax Trees	Compilers use syntax trees for parsing
Decision Trees	Machine learning algorithms
File Systems	Directory structure representation
Game Trees	AI in games (chess, tic-tac-toe)

---

PART 4: BINARY SEARCH TREE (BST)

4.1 Definition

A Binary Search Tree (BST) is a binary tree that satisfies the following properties for every node:

1. All nodes in the left subtree have values less than the node's value

2. All nodes in the right subtree have values greater than the node's value

3. Both left and right subtrees are also BSTs

Example:

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

Why BST?

• Provides O(log n) average case for search, insert, delete

• Inorder traversal gives sorted order

4.2 BST Operations

4.2.1 Search

Algorithm (Recursive):

search(root, key):
    if root == NULL OR root.data == key:
        return root
    if key < root.data:
        return search(root.left, key)
    else:
        return search(root.right, key)

Algorithm (Iterative):

search_iterative(root, key):
    current = root
    while current != NULL AND current.data != key:
        if key < current.data:
            current = current.left
        else:
            current = current.right
    return current

Time Complexity: O(h) where h is height

• Best/Average: O(log n)

• Worst: O(n) for skewed tree

4.2.2 Insertion

Algorithm (Recursive):

insert(root, key):
    if root == NULL:
        return createNode(key)
    
    if key < root.data:
        root.left = insert(root.left, key)
    else if key > root.data:
        root.right = insert(root.right, key)
    // If equal, do nothing (no duplicates)
    
    return root

Algorithm (Iterative):

insert_iterative(root, key):
    newNode = createNode(key)
    
    if root == NULL:
        return newNode
    
    current = root
    parent = NULL
    
    while current != NULL:
        parent = current
        if key < current.data:
            current = current.left
        else if key > current.data:
            current = current.right
        else:
            free(newNode)  // duplicate
            return root
    
    if key < parent.data:
        parent.left = newNode
    else:
        parent.right = newNode
    
    return root

Time Complexity: O(h)

Example Insertion: Insert 25 into:

        50
       /  \
     30    70
    /  \
   20  40

Result:

        50
       /  \
     30    70
    /  \
   20  40
      /
     25

4.2.3 Deletion

Three Cases:

Case 1: Node has no children (leaf)

• Simply remove the node

Case 2: Node has one child

• Replace node with its child

Case 3: Node has two children

• Find inorder successor (smallest in right subtree) OR inorder predecessor (largest in left subtree)

• Copy successor's value to node

• Delete the successor (which will be Case 1 or 2)

Algorithm:

delete(root, key):
    if root == NULL:
        return NULL
    
    if key < root.data:
        root.left = delete(root.left, key)
    else if key > root.data:
        root.right = delete(root.right, key)
    else:
        // Case 1: No child
        if root.left == NULL AND root.right == NULL:
            free(root)
            return NULL
        
        // Case 2: One child
        if root.left == NULL:
            temp = root.right
            free(root)
            return temp
        if root.right == NULL:
            temp = root.left
            free(root)
            return temp
        
        // Case 3: Two children
        temp = findMin(root.right)  // inorder successor
        root.data = temp.data
        root.right = delete(root.right, temp.data)
    
    return root

findMin(root):
    while root.left != NULL:
        root = root.left
    return root

Time Complexity: O(h)

Example Deletions:

Delete 20 (leaf):

Before:           After:
    50               50
   /  \             /  \
 30    70    →    30    70
/  \              /  \
20 40            40   ?

Delete 30 (one child):

Before:           After:
    50               50
   /  \             /  \
 30    70    →    40    70
  \               
  40              

Delete 50 (two children):

Before:           After (using successor 60):
    50               60
   /  \             /  \
 30    70    →    30    70
      /  \             /  \
     60  80           65  80
       \
       65

4.2.4 Finding Minimum and Maximum

Minimum:

findMin(root):
    if root == NULL: return NULL
    while root.left != NULL:
        root = root.left
    return root

Maximum:

findMax(root):
    if root == NULL: return NULL
    while root.right != NULL:
        root = root.right
    return root

Time Complexity: O(h)

4.2.5 Finding Inorder Successor and Predecessor

Inorder Successor (next node in inorder traversal):

successor(root, node):
    if node.right != NULL:
        return findMin(node.right)
    
    successor = NULL
    while root != NULL:
        if node.data < root.data:
            successor = root
            root = root.left
        else if node.data > root.data:
            root = root.right
        else:
            break
    return successor

Time Complexity: O(h)

4.3 BST Complexity Analysis

Operation	Average Case	Worst Case
Search	O(log n)	O(n)
Insert	O(log n)	O(n)
Delete	O(log n)	O(n)
Find Min/Max	O(log n)	O(n)
Successor/Predecessor	O(log n)	O(n)

Space Complexity: O(n) for storing n nodes

4.4 Advantages and Disadvantages of BST

Advantages:

• Simple to implement

• Inorder traversal gives sorted order

• Better than linear search for dynamic data

Disadvantages:

• No balance guarantee → can become O(n) worst case

• Performance depends on insertion order

• Skewed trees degrade to linked lists

---

PART 5: THREADED BINARY TREE

5.1 Need for Threaded Binary Tree

Problems with regular binary tree:

• Many NULL pointers (approximately n+1 NULL pointers for n nodes)

• Traversal requires stack (recursion overhead)

• Cannot easily find successor/predecessor

Solution: Replace NULL pointers with threads (pointers) to other nodes

5.2 Definition

A Threaded Binary Tree is a binary tree where NULL pointers are replaced with threads that point to other nodes in inorder sequence.

Types of Threading:

1. Single Threaded: Only right NULL pointers replaced with inorder successor

2. Double Threaded: Both left and right NULL pointers replaced (left points to inorder predecessor, right to inorder successor)

5.3 Node Structure

struct ThreadedNode {
    int data;
    struct ThreadedNode* left;
    struct ThreadedNode* right;
    int leftThread;   // 1 if left is thread, 0 if child
    int rightThread;  // 1 if right is thread, 0 if child
};

5.4 Threaded Binary Tree Example

Original Tree:

        A
       / \
      B   C
     / \   \
    D   E   F

Inorder traversal: D, B, E, A, C, F

Threaded Tree (Inorder):

        A
       / \
      B   C
     / \   \
    D→B E→A F→?
       /     \
      ?       ?

Threads:

• D's right NULL → points to B (successor)

• E's right NULL → points to A (successor)

• B's left NULL? Could point to head node or NULL

• F's right NULL → points to NULL or head

5.5 Operations on Threaded Binary Tree

5.5.1 Finding Inorder Successor

findSuccessor(node):
    if node.rightThread == 1:
        return node.right  // thread to successor
    else:
        // has right child, find leftmost in right subtree
        current = node.right
        while current.leftThread == 0:
            current = current.left
        return current

Time Complexity: O(h) worst case, often O(1)

5.5.2 Inorder Traversal (Non-recursive)

inorder_threaded(root):
    // Find leftmost node
    current = root
    while current.leftThread == 0:
        current = current.left
    
    // Traverse using threads
    while current != NULL:
        print current.data
        current = findSuccessor(current)

Time Complexity: O(n) Space Complexity: O(1) - no stack needed!

5.5.3 Insertion in Threaded Binary Tree

Inserting a new node requires updating threads:

Case 1: Insert as left child

• New node's left becomes old node's left

• New node's right becomes old node (as thread)

• Old node's left becomes new node (as child)

Case 2: Insert as right child

• New node's right becomes old node's right

• New node's left becomes old node (as thread)

• Old node's right becomes new node (as child)

5.6 Advantages and Disadvantages

Advantages:

• No stack required for traversal

• Memory utilization of NULL pointers

• Faster traversal

• Easy to find successor/predecessor

Disadvantages:

• Complex insertion/deletion (threads need updating)

• Extra space for thread flags

• More complex implementation

---

PART 6: AVL TREE (SELF-BALANCING BST)

6.1 Definition

AVL Tree (named after Adelson-Velsky and Landis) is a self-balancing binary search tree where the heights of left and right subtrees of every node differ by at most 1.

Balance Factor:

Balance Factor = height(left subtree) - height(right subtree)

Allowed Balance Factors: -1, 0, 1

6.2 Why AVL Tree?

• Regular BST can become skewed → O(n) operations

• AVL maintains height O(log n) always

• Guarantees log n time for all operations

Comparison:

Tree	Height (n=1,000,000)	Search Time
BST (worst)	999,999	~1,000,000 comparisons
AVL	≈ 28	28 comparisons

6.3 AVL Tree Rotations

When balance factor becomes ±2, rotation is performed to restore balance.

6.3.1 LL Rotation (Right Rotation)

When: Insertion in left subtree of left child (Left-Left case)

Situation:

• Node A has BF = +2

• Left child B has BF = +1

Diagram:

Before:          After:
    A              B
   /              / \
  B              C   A
 /
C

Algorithm:

rightRotate(A):
    B = A.left
    T2 = B.right
    
    // Perform rotation
    B.right = A
    A.left = T2
    
    // Update heights
    updateHeight(A)
    updateHeight(B)
    
    return B  // New root

Example:

    50                  40
   /                   /  \
  40        →        30    50
 /
30

6.3.2 RR Rotation (Left Rotation)

When: Insertion in right subtree of right child (Right-Right case)

Situation:

• Node A has BF = -2

• Right child B has BF = -1

Diagram:

Before:        After:
  A                B
   \              / \
    B            A   C
     \
      C

Algorithm:

leftRotate(A):
    B = A.right
    T2 = B.left
    
    // Perform rotation
    B.left = A
    A.right = T2
    
    // Update heights
    updateHeight(A)
    updateHeight(B)
    
    return B

Example:

30                   40
  \                 /  \
   40      →      30    50
    \
     50

6.3.3 LR Rotation (Left-Right Rotation)

When: Insertion in right subtree of left child (Left-Right case)

Situation:

• Node A has BF = +2

• Left child B has BF = -1

Steps:

1. Left rotate at B

2. Right rotate at A

Diagram:

Step 1: Left rotate at B     Step 2: Right rotate at A
    A                           A                       C
   /                           /                       / \
  B            →               C           →         B   A
   \                         /
    C                       B

Algorithm:

leftRightRotate(A):
    A.left = leftRotate(A.left)
    return rightRotate(A)

Example:

    50                    50                    45
   /                      /                     / \
  30          →          45          →        30   50
    \                    /
     45                 30

6.3.4 RL Rotation (Right-Left Rotation)

When: Insertion in left subtree of right child (Right-Left case)

Situation:

• Node A has BF = -2

• Right child B has BF = +1

Steps:

1. Right rotate at B

2. Left rotate at A

Diagram:

Step 1: Right rotate at B    Step 2: Left rotate at A
  A                           A                       C
   \                           \                     / \
    B            →               C         →       A   B
   /                             \
  C                               B

Algorithm:

rightLeftRotate(A):
    A.right = rightRotate(A.right)
    return leftRotate(A)

Example:

30                        30                      40
  \                         \                     / \
   50           →            40         →      30   50
  /                            \
40                             50

6.4 AVL Tree Operations

6.4.1 Insertion

Algorithm:

insert(root, key):
    // Step 1: Perform normal BST insertion
    if root == NULL:
        return createNode(key)
    
    if key < root.data:
        root.left = insert(root.left, key)
    else if key > root.data:
        root.right = insert(root.right, key)
    else:
        return root  // No duplicates
    
    // Step 2: Update height of current node
    root.height = 1 + max(height(root.left), height(root.right))
    
    // Step 3: Get balance factor
    balance = getBalance(root)
    
    // Step 4: If unbalanced, perform rotations
    
    // Left Left Case
    if balance > 1 and key < root.left.data:
        return rightRotate(root)
    
    // Right Right Case
    if balance < -1 and key > root.right.data:
        return leftRotate(root)
    
    // Left Right Case
    if balance > 1 and key > root.left.data:
        root.left = leftRotate(root.left)
        return rightRotate(root)
    
    // Right Left Case
    if balance < -1 and key < root.right.data:
        root.right = rightRotate(root.right)
        return leftRotate(root)
    
    return root

Time Complexity: O(log n)

6.4.2 Deletion

Algorithm:

delete(root, key):
    // Step 1: Perform normal BST deletion
    if root == NULL:
        return root
    
    if key < root.data:
        root.left = delete(root.left, key)
    else if key > root.data:
        root.right = delete(root.right, key)
    else:
        // Node with only one child or no child
        if root.left == NULL or root.right == NULL:
            temp = root.left ? root.left : root.right
            
            if temp == NULL:  // No child
                temp = root
                root = NULL
            else:  // One child
                *root = *temp  // Copy contents
            free(temp)
        else:
            // Two children: get inorder successor
            temp = findMin(root.right)
            root.data = temp.data
            root.right = delete(root.right, temp.data)
    
    if root == NULL:
        return root
    
    // Step 2: Update height
    root.height = 1 + max(height(root.left), height(root.right))
    
    // Step 3: Get balance factor
    balance = getBalance(root)
    
    // Step 4: Balance the tree
    
    // Left Left Case
    if balance > 1 and getBalance(root.left) >= 0:
        return rightRotate(root)
    
    // Left Right Case
    if balance > 1 and getBalance(root.left) < 0:
        root.left = leftRotate(root.left)
        return rightRotate(root)
    
    // Right Right Case
    if balance < -1 and getBalance(root.right) <= 0:
        return leftRotate(root)
    
    // Right Left Case
    if balance < -1 and getBalance(root.right) > 0:
        root.right = rightRotate(root.right)
        return leftRotate(root)
    
    return root

Time Complexity: O(log n)

6.4.3 Search

Same as BST search - O(log n)

6.5 AVL Tree Complexity Analysis

Operation	Time Complexity	Space Complexity
Search	O(log n)	O(1)
Insert	O(log n)	O(log n) recursion
Delete	O(log n)	O(log n) recursion

6.6 AVL vs BST Comparison

Feature	BST	AVL
Balance	Not required	Strictly balanced
Height	O(n) worst case	O(log n) always
Search	O(n) worst	O(log n)
Insert	O(n) worst	O(log n) with rotations
Delete	O(n) worst	O(log n) with rotations
Rotations	None	Required
Implementation	Simple	Complex
Memory	Data + 2 pointers	+ balance factor

---

PART 7: B-TREE

7.1 Introduction

B-Tree is a self-balancing tree data structure that maintains sorted data and allows searches, sequential access, insertions, and deletions in logarithmic time. It is designed to work well on magnetic disks or other direct-access secondary storage devices.

Why B-Tree?

• Binary trees have high height → many disk accesses

• B-Tree has high fanout (many children per node) → shorter tree

• Each node corresponds to a disk block → fewer disk I/Os

7.2 Definition

A B-Tree of order m has the following properties:

1. All leaves are at the same level

2. Each node (except root) has at least ⌈m/2⌉ children

3. Each node has at most m children

4. Each internal node with k children contains k-1 keys

5. Keys in a node are stored in ascending order

6. Root has at least 2 children if it's not a leaf

Node Structure:

[Key1, Key2, ..., Key(k-1)]
 /     |     |          \
Child1 Child2 Child3 ... Childk

7.3 B-Tree of Order 5 Example

                 [30, 60]
                /    |    \
          [10,20] [40,50] [70,80,90]

Properties:

• Order m = 5

• Max keys per node = 4

• Min keys per node (except root) = 2

• Max children = 5

• Min children = 3

7.4 B-Tree Operations

7.4.1 Search

Algorithm:

search(root, key):
    i = 0
    while i < root.n and key > root.key[i]:
        i++
    
    if i < root.n and key == root.key[i]:
        return (root, i)  // Found
    
    if root.leaf:
        return NULL  // Not found
    
    // Recursively search in appropriate child
    return search(root.child[i], key)

Time Complexity: O(log n) where n is number of keys

7.4.2 Insertion

Algorithm:

insert(root, key):
    if root is full:
        create newRoot
        split root and move median up
        insert into appropriate child
    
    else:
        insertNonFull(root, key)

insertNonFull(node, key):
    i = node.n - 1
    
    if node.leaf:
        // Find position and insert
        while i >= 0 and key < node.key[i]:
            node.key[i+1] = node.key[i]
            i--
        node.key[i+1] = key
        node.n++
    else:
        // Find child to insert into
        while i >= 0 and key < node.key[i]:
            i--
        i++
        
        if node.child[i].n == MAX_KEYS:
            splitChild(node, i)
            if key > node.key[i]:
                i++
        
        insertNonFull(node.child[i], key)

Split Operation:

splitChild(parent, index):
    child = parent.child[index]
    newChild = createNode()
    
    // Move second half of keys to newChild
    // Move median key up to parent
    // Adjust child pointers

Time Complexity: O(log n)

7.4.3 Deletion

Three Main Cases:

Case 1: Key in leaf node

• If leaf has > min keys: simply delete

• If leaf has min keys:

  • Borrow from sibling (if sibling has extra)

  • Merge with sibling (if both at min)

Case 2: Key in internal node

• Replace with predecessor/successor from leaf

• Delete predecessor/successor from leaf (now Case 1)

Case 3: During deletion, if child has min keys:

• Borrow from sibling or merge

Algorithm Outline:

delete(root, key):
    if root == NULL: return
    
    // Find node containing key
    // Handle based on cases above
    // Merge if necessary
    // Update tree if root becomes empty

Time Complexity: O(log n)

7.5 B-Tree Order Selection

Order m is chosen based on disk block size:

• Larger m → shorter tree → fewer disk accesses

• But larger nodes require more processing

Typical order: 100-200 for database applications

7.6 Applications of B-Tree

1. Database Indexes (MySQL, Oracle, PostgreSQL)

2. File Systems (NTFS, HFS+, ext4)

3. Directory structures in operating systems

4. Multilevel indexing for large datasets

---

PART 8: B+ TREE

8.1 Definition

B+ Tree is a variation of B-Tree where:

1. All keys are stored at the leaf level

2. Internal nodes contain only keys (routers) to guide search

3. Leaf nodes are linked together for sequential access

4. All leaf nodes are at the same level

8.2 Structure

        [50, 70]                    ← Internal nodes (only keys)
       /    |    \
   [30]   [60]   [80, 90]           ← Internal nodes
   /  \   /  \   /  |  \
[10,20] [40] [55] [65] [75] [85,95] ← Leaf nodes with data
  |      |    |    |    |     |
  ↓      ↓    ↓    ↓    ↓     ↓
 data  data data data data  data
 10↔20↔40↔50↔55↔60↔65↔70↔75↔80↔85↔90  ← Linked leaves

8.3 Properties

1. Internal nodes store only keys (no data pointers)

2. Leaf nodes store all keys + data pointers

3. Leaf nodes are linked (singly or doubly) for sequential access

4. All leaves at same level

5. Each node (except root) has at least ⌈m/2⌉ children

6. Each node has at most m children

8.4 B-Tree vs B+ Tree Comparison

Feature	B-Tree	B+ Tree
Data pointers	All nodes	Only leaf nodes
Internal nodes	Store keys + data	Store only keys
Leaf nodes	Store keys + data	Store keys + data + sibling pointers
Redundant keys	No	Yes (keys repeated in internal nodes)
Search	May end at internal node	Always goes to leaf
Range queries	Slow (multiple traversals)	Fast (leaf links)
Sequential access	Not supported	Supported via linked leaves
Insertion	Complex	Easier
Deletion	Complex (internal node deletion)	Easier (always from leaf)
Height	Shorter	Slightly taller
Space utilization	No redundancy	Some redundancy
Disk I/O	May be more	Optimized

8.5 Operations on B+ Tree

8.5.1 Search

search(root, key):
    current = root
    while current is not leaf:
        find appropriate child pointer
        current = that child
    
    search leaf for key
    return data pointer if found, else NULL

8.5.2 Insertion

Similar to B-Tree but:

• Always insert into leaf node

• If leaf overflows, split and copy median up to parent (not move)

8.5.3 Deletion

Similar to B-Tree but:

• Always delete from leaf node

• If underflow, borrow from sibling or merge

• Update parent keys if necessary

8.6 Applications of B+ Tree

1. Database indexing (most modern databases)

2. File systems (for large file indexing)

3. Multimedia indexing

4. Data warehousing

5. Range queries where sequential access needed

---

PART 9: COMPLEXITY ANALYSIS SUMMARY

Time Complexities Comparison

Data Structure	Search	Insert	Delete	Space
Binary Tree	O(n)	O(n)	O(n)	O(n)
BST (avg)	O(log n)	O(log n)	O(log n)	O(n)
BST (worst)	O(n)	O(n)	O(n)	O(n)
AVL Tree	O(log n)	O(log n)	O(log n)	O(n)
B-Tree	O(log n)	O(log n)	O(log n)	O(n)
B+ Tree	O(log n)	O(log n)	O(log n)	O(n)

Space Complexities

Data Structure	Space per Node	Total Space
Binary Tree	Data + 2 pointers	O(n)
BST	Data + 2 pointers	O(n)
AVL	Data + 2 pointers + BF	O(n)
Threaded BT	Data + 2 pointers + 2 flags	O(n)
B-Tree	Multiple keys + multiple pointers	O(n)
B+ Tree	Multiple keys + multiple pointers	O(n)

---

PART 10: APPLICATIONS SUMMARY

Data Structure	Primary Applications
Binary Tree	Expression trees, Huffman coding, syntax trees
BST	Dictionary, symbol tables, priority queues
AVL Tree	When guaranteed O(log n) operations needed
Threaded BT	When stack memory is limited
B-Tree	Database indexes, file systems
B+ Tree	Modern databases, range queries, sequential access

---

QUICK REVISION TABLE

Topic	Key Points	Formula/Property
Tree Terminology	Root, leaf, internal node, height, depth	n₀ = n₂ + 1
Binary Tree	Max 2 children	Max nodes at level i = 2ⁱ
Full Binary Tree	0 or 2 children	Nodes = 2L - 1
Complete Binary Tree	All levels filled except last, left-aligned	Parent = (i-1)/2
Perfect Binary Tree	All internal nodes have 2 children, leaves at same level	Nodes = 2ʰ⁺¹ - 1
BST Property	left < root < right	Inorder gives sorted order
AVL Balance Factor		BF ∈ {-1,0,1}
AVL Rotations	LL, RR, LR, RL	4 types
B-Tree Order m	Max m children	Min children = ⌈m/2⌉
B+ Tree	Data only at leaves, leaves linked	Better for range queries