National Institute of Electronics and Information Technology

Data Structures
Module 5-Tree Traversal
 Introduction to Tree Traversal
1. Tree traversal (also known as tree search and walking the tree) is the systematic process of visiting every
node in a tree data structure exactly once in a specific order. Unlike linear data structures such as arrays or
linked lists that have only one logical way of access, a tree provides multiple traversal orders because each
node may have multiple child links.
2. Traversals are essential to almost all tree operations — including searching, insertion, deletion, expression
evaluation, copying, and sorting — as they define the order in which the tree’s nodes are processed.
3. Tree Traversal Techniques: Tree traversal methods are broadly classified into two categories:
Category Traversal Type Core Idea
Depth-First Traversal (DFT) Preorder, Inorder, Goes as deep as possible down one branch before
Postorder backtracking
Breadth-First Traversal (BFT) Level Order Visits all nodes level by level, from top to bottom
4. Data Structures for Tree Traversal: Since a tree is
not linear, we need auxiliary data structures to keep
track of deferred nodes:
a. Stack (LIFO) → used for Depth-First Traversal
(Preorder, Inorder, Postorder)
b. Queue (FIFO) → used for Breadth-First
Traversal (Level Order)
c. Call Stack (Implicit) → used in recursive
traversals
Common variants of DFS: Preorder (NLR), Inorder (LNR), 5. Recursive vs Iterative:
Postorder (LRN) where a. Recursive traversal: Implicitly uses the call
N — Visit the current node stack.
L — Traverse the left subtree. b. Iterative traversal: Explicitly manages traversal
R — Traverse the right subtree. using a stack or queue for manual control.
2
 Depth-first search
1. In depth-first search (DFS), the search tree is deepened as much as possible before going to the next sibling.
To traverse binary trees with depth-first search, perform the following operations at each node:
a. If the current node is empty then return.
b. Execute the following three operations in a certain order:
N: Visit the current node.
L: Recursively traverse the current node's left subtree.
R: Recursively traverse the current node's right subtree.

Depth-first traversal (dotted path) of a binary tree:

Pre-order (node visited at position red ●): F, B, A, D, C, E, G, I, H;
In-order (node visited at position green ●): A, B, C, D, E, F, G, H, I;
Post-order (node visited at position blue ●): A, C, E, D, B, H, I, G, F.

2. The trace of a traversal is called a sequentialisation of the tree. The traversal trace is a list of each visited
node. Given a tree with distinct elements, either pre-order or post-order paired with in-order is sufficient to
describe the tree uniquely. However, pre-order with post-order leaves some ambiguity in the tree structure.
3. There are three methods at which position of the traversal relative to the node (in the figure: red, green, or
blue) the visit of the node shall take place.
a. The choice of exactly one color determines exactly one visit of a node as described below.
b. Visit at all three colors results in a threefold visit of the same node yielding the “all-order”
sequentialisation: F-B-A-A-A-B-D-C-C-C-D-E-E-E-D-B-F-G-G- I-H-H-H- I- I-G-F
3
 Preorder Traversal (NLR)
1. Preorder Traversal is the type of Depth First Traversal where nodes are visited in the order: Root, Left then
Right. It's named "preorder" because the "Visit" step occurs before traversing the left and right child nodes.
a. Visit the Current Node: Begin by visiting the current node, performing the visitation operation (such as
printing the node's value or performing an operation with the node's data).
b. Traverse the Left Subtree: Recursively traverse the left subtree, following the same steps starting from
step 1.
c. Traverse the Right Subtree: After fully traversing the left subtree, recursively traverse the right subtree,
following the same steps starting from step 1.
Preorder Traversal (NLR)
Order: Node → Left → Right
Use Case: Tree copying, prefix expression
generation.
Recursive Process:
1. Visit the current node
2. Traverse the left subtree recursively
3. Traverse the right subtree recursively
Iterative Process: Uses a stack; push right
child first so that left is processed first.

Note: The pre-order traversal is

a topologically sorted one, because a
parent node is processed before any of its
child nodes is done.

4
Preorder Traversal (NLR)

5
 Preorder Traversal (NLR)
Preorder (recursive) /* Recursive Traversals */
procedure PREORDER(node) void preorder(struct Node* root) {
if node == NULL then return if (root == NULL)
VISIT(node) return;
PREORDER([Link]) printf("%d ", root->data);
PREORDER([Link]) preorder(root->left);
end procedure preorder(root->right);
}
Iterative Preorder (stack) /* Iterative Traversals using Stack */
procedure PREORDER_ITERATIVE(root) void iterativePreorder(struct Node* root) {
if root == NULL then return struct Node* stack[100];
S = empty stack int top = -1;
PUSH(S, root) struct Node* temp;
while S is not empty if (root == NULL)
node = POP(S) return;
VISIT(node) stack[++top] = root;
if [Link] != NULL then PUSH(S, [Link]) // push right while (top >= 0) {
first temp = stack[top--];
if [Link] != NULL then PUSH(S, [Link]) // so left is printf("%d ", temp->data);
processed next if (temp->right != NULL)
end while stack[++top] = temp->right;
end procedure if (temp->left != NULL)
stack[++top] = temp->left;
}
}
6
 Post-Order Traversal (LRN)
1. Postorder Traversal is the type of Depth First Traversal where nodes are visited in the order: Left, Right then
Root. It's named "postorder" because the "Visit" step occurs after traversing the left and right child nodes.
a. Traverse the Left Subtree: Recursively traverse the left subtree.
b. Traverse the Right Subtree: Similarly, recursively traverse the right subtree.
c. Visit the Current Node: After fully traversing both left and right subtrees, visit the current node,
performing the visitation operation (such as printing the node's value or performing an operation with
the node's data).
Postorder Traversal (LRN)
Order: Left → Right → Node
Use Case: Tree deletion, postfix expression
generation.
Recursive Process:
1. Traverse left subtree recursively
2. Traverse right subtree recursively
3. Visit the current node
Iterative Process: Uses stack and pointer
tracking (to avoid re-processing right subtrees).

Note: Post-order traversal can be useful to get

postfix expression of a binary expression tree.

7
Post-Order Traversal (LRN)

8
 Post-Order Traversal (LRN)
Postorder (recursive) /* Recursive Traversals */
procedure POSTORDER(node) void postorder(struct Node* root) {
if node == NULL then return if (root == NULL) return;
POSTORDER([Link]) postorder(root->left);
POSTORDER([Link]) postorder(root->right);
VISIT(node) printf("%d ", root->data);
end procedure }
/* Iterative Traversals using Stack */
Iterative Postorder void iterativePostorder(struct Node* root) {
procedure POSTORDER_ITERATIVE(root) struct Node* stack[100];
S = empty stack int top = -1;
lastVisited = NULL struct Node* lastVisited = NULL, * curr, * peekNode;
current = root curr = root;
while current != NULL or S is not empty while (curr != NULL || top >= 0) {
if current != NULL if (curr != NULL) {
PUSH(S, current) stack[++top] = curr;
current = [Link] curr = curr->left;
else } else {
peekNode = TOP(S) peekNode = stack[top];
if [Link]!=NULL and lastVisited!=[Link] if(peekNode->right!=NULL && lastVisited!=peekNode-
current = [Link] >right)
else curr = peekNode->right;
VISIT(peekNode) else {
lastVisited = POP(S) printf("%d ", peekNode->data);
end if lastVisited = stack[top--];
end if }
end while }
end procedure }
}
9
 In-Order Traversal (LNR)
1. Inorder Traversal is the type of Depth First Traversal where nodes are visited in the order: Left, Root, Right.
It's named "inorder" because it traverses the nodes in a sequence where the "Visit" step occurs between the
left and right child nodes.
a. Visit the Left Subtree: Recursively traverse the left subtree until a leaf node or a node with no left child is
reached.
b. Visit the Current Node: Once at a node, perform the visitation operation (such as printing the node's
value or performing an operation with the node's data).
c. Traverse the Right Subtree: After visiting the current node, recursively traverse the right subtree,
following the same steps as the left subtree.
Inorder Traversal (LNR)
Order: Left → Node → Right
Use Case: Retrieving nodes in ascending order
in a Binary Search Tree.
Recursive Process:
1. Traverse the left subtree recursively
2. Visit the current node
3. Traverse the right subtree recursively
Iterative Process: Uses a stack to simulate
recursion, ensuring leftmost nodes are
processed first.

10
In-Order Traversal (LNR)

11
 In-Order Traversal (LNR)
Inorder (recursive) /* Recursive Traversals */
procedure INORDER(node) void inorder(struct Node* root) {
if node == NULL then return if (root == NULL)
INORDER([Link]) return;
VISIT(node) inorder(root->left);
INORDER([Link]) printf("%d ", root->data);
end procedure inorder(root->right);
}
Iterative Inorder (Stack) /* Iterative Traversals using Stack */
procedure INORDER_ITERATIVE(root) void iterativeInorder(struct Node* root) {
S = empty stack struct Node* stack[100];
current = root int top = -1;
while current != NULL or S is not empty struct Node* curr;
while current != NULL curr = root;
PUSH(S, current)
current = [Link] while (curr != NULL || top >= 0) {
end while while (curr != NULL) {
current = POP(S) stack[++top] = curr;
VISIT(current) curr = curr->left;
current = [Link] }
end while curr = stack[top--];
end procedure printf("%d ", curr->data);
curr = curr->right;
}
}
12
 Reverse Traversals
Reverse traversals: Reverse variants of the standard traversals simply flip the order in which the left and
right subtrees are visited.
1. Reverse pre-order traversal (NRL)
a. Order: Node, Right, Left (NRL)
b. Description: Instead of going left, then right, you visit the right subtree, then the left subtree.
i. Visit the current node.
ii. Recursively traverse the current node's right subtree.
iii. Recursively traverse the current node's left subtree.
2. Reverse in-order traversal (RNL)
a. Order: Right, Node, Left (RNL)
b. Description: For a binary search tree, this will produce the nodes in descending (reverse sorted)
order.
i. Recursively traverse the current node's right subtree.
ii. Visit the current node.
iii. Recursively traverse the current node's left subtree.
3. Reverse post-order traversal (RLN)
a. Order: Right, Left, Node (RLN)
b. Description: This traversal is essentially a mirror of the standard post-order, visiting the right
subtree before the left. It can be obtained by running a standard pre-order traversal and then
reversing the output.
i. Recursively traverse the current node's right subtree.
ii. Recursively traverse the current node's left subtree.
iii. Visit the current node.

13
 Reverse Traversals
Practical tips & pitfalls
1. Swap carefully: Reverse traversal == standard traversal with left and right swapped everywhere. Be
consistent.
2. Iterative push order matters: When using a stack, push the child that should be processed last first. Example:
a. For preorder NLR: push right, then left.
b. For reverse preorder NRL: push left, then right.
3. Reverse of preorder trick: To produce RLN quickly: do preorder (N L R) but collect nodes and then reverse the
output — this is simpler than implementing a single-stack postorder variant.
4. For BSTs: Reverse inorder (RNL) returns descending-sorted keys; standard inorder returns ascending-sorted
keys.
5. Diagrams: Always annotate left/right unambiguously; many errors come from swapped drawing conventions.
Traversal Notation Sequence
1 Preorder (Node, Left, Right) NLR 1, 2, 4, 5, 3, 6, 7
/ \ Reverse Preorder (Node, Right, Left) NRL 1, 3, 7, 6, 2, 5, 4
2 3 Inorder (Left, Node, Right) LNR 4, 2, 5, 1, 6, 3, 7
/\ /\ Reverse Inorder (Right, Node, Left) RNL 7, 3, 6, 1, 5, 2, 4
4 56 7 Postorder (Left, Right, Node) LRN 4, 5, 2, 6, 7, 3, 1
Reverse Postorder (Right, Left, Node) RLN 7, 6, 3, 5, 4, 2, 1

14
 Reverse Pre-Order Traversal (NRL)
Reverse PreOrder (recursive) /* Recursive Traversals */
procedure REVERSE_PREORDER(node) void reversePreorder(struct Node* root) {
if node == NULL then return if (root == NULL)
VISIT(node) return;
REVERSE_PREORDER([Link]) printf("%d ", root->data);
REVERSE_PREORDER([Link]) reversePreorder(root->right);
end procedure reversePreorder(root->left);
}
Iterative Reverse PreOrder (Stack) /* Iterative Traversals using Stack */
procedure REVERSE_PREORDER_ITERATIVE(root) void iterativeReversePreorder(struct Node *root) {
if root == NULL then return struct Node *stack[100], *temp;
int top;
S = empty stack top = -1;
PUSH(S, root) if (root == NULL) return;
stack[++top] = root;
while S is not empty while (top >= 0) {
node = POP(S) temp = stack[top--];
VISIT(node) printf("%d ", temp->data);
/* Push left first so right is processed first */
// Push left first so that right is processed first if (temp->left != NULL)
if [Link] ≠ NULL then PUSH(S, [Link]) stack[++top] = temp->left;
if [Link] ≠ NULL then PUSH(S, [Link]) if (temp->right != NULL)
end while stack[++top] = temp->right;
end procedure }
}
15
 Reverse In-Order Traversal (RNL)
Reverse Inorder (recursive) /* Recursive Traversals */
procedure REVERSE_INORDER(node) void reverseInorder(struct Node* root) {
if node == NULL then return if (root == NULL)
REVERSE_INORDER([Link]) return;
VISIT(node) reverseInorder(root->right);
REVERSE_INORDER([Link]) printf("%d ", root->data);
end procedure reverseInorder(root->left);
}
Reverse Iterative Inorder (Stack) /* Iterative Traversals using Stack */
procedure REVERSE_INORDER_ITERATIVE(root) void iterativeReverseInorder(struct Node *root) {
S = empty stack struct Node *stack[100], *curr;
current = root int top;
while current ≠ NULL or S is not empty top = -1;
// Reach the rightmost node of current subtree curr = root;
while current ≠ NULL
PUSH(S, current) while (curr != NULL || top >= 0) {
current = [Link] while (curr != NULL) {
end while stack[++top] = curr;
// Pop node from stack and visit curr = curr->right;
current = POP(S) }
VISIT(current) curr = stack[top--];
// Move to left subtree printf("%d ", curr->data);
current = [Link] curr = curr->left;
end while }
end procedure }
16
 Reverse Post-Order Traversal (RLN)
Reverse PostOrder (recursive) /* Recursive Traversals */
procedure REVERSE_POSTORDER(node) void reversePostorder(struct Node* root) {
if node == NULL then return if (root == NULL) return;
REVERSE_POSTORDER([Link]) reversePostorder(root->right);
REVERSE_POSTORDER([Link]) reversePostorder(root->left);
VISIT(node) printf("%d ", root->data);
end procedure }
/* Iterative Traversals using Stack */
Reverse Iterative PostOrder (Stack) void iterativeReversePostorder(struct Node *root) {
procedure REVERSE_POSTORDER_ITERATIVE(root) struct Node *stack[100], *lastVisited, *curr, *peekNode;
S = empty stack int top;
lastVisited = NULL top = -1;
current = root lastVisited = NULL;
while current ≠ NULL or S is not empty curr = root;
if current ≠ NULL while (curr != NULL || top >= 0) {
PUSH(S, current) if (curr != NULL) {
current = [Link] stack[++top] = curr;
else curr = curr->right;
peekNode = TOP(S) } else {
// If left child exists and not yet processed, traverse it peekNode = stack[top];
if [Link] ≠ NULL and lastVisited ≠ [Link] if (peekNode->left!=NULL && lastVisited!=peekNode->left)
current = [Link] curr = peekNode->left;
else else {
VISIT(peekNode) printf("%d ", peekNode->data);
lastVisited = POP(S) lastVisited = stack[top--];
end if }
end if }
end while }
end procedure }
17
 Level Order Traversal (BFS)
1. Level Order Traversal is the type of Breadth First Traversal where nodes are visited level by level, exploring
each level completely before moving to the next level.
a. Level Order Traversal visits all nodes present in the same level completely before visiting the next level.
b. Level order traversal utilises a queue data structure to maintain the nodes at each level, ensuring that
nodes at higher levels are visited before moving to lower levels.
2. Procedure of Level Order Traversal:
a. Visit Nodes at Each Level: Starting from the root node, visit all nodes at level 0.
b. Move to Next Level: After visiting all nodes at level 0, move to level 1 and visit all nodes at this level from
left to right.
c. Continue Level-wise: Repeat this process for subsequent levels, visiting nodes at each level from left to
right until all levels are visited.
Level Order Traversal (Breadth-First Search)
Order: Visit nodes level by level, from top to
bottom and left to right.
Data Structure Used: Queue
Use Case: Finding shortest paths, hierarchical
printing, or level-wise processing.
Algorithm Steps:
1. Enqueue the root node
2. Repeat until queue is empty:
a. Dequeue a node and visit it
b. Enqueue its left and right children if they
exist

18
Level Order Traversal (BFS)

19
 Level Order Traversal (BFS)
Level Order (Breadth-First) void levelOrder(struct Node* root) {
procedure LEVEL_ORDER(root)
struct Node* queue[100];
if root == NULL then return
Q = empty queue int front = 0, rear = 0;
ENQUEUE(Q, root) struct Node* curr;
while Q is not empty
node = DEQUEUE(Q) if (root == NULL)
VISIT(node) return;
if [Link] != NULL then ENQUEUE(Q, [Link])
if [Link] != NULL then ENQUEUE(Q, [Link]) queue[rear++] = root;
end while
while (front < rear) {
end procedure
curr = queue[front++];
printf("%d ", curr->data);
if (curr->left != NULL)
queue[rear++] = curr->left;
if (curr->right != NULL)
queue[rear++] = curr->right;
}
}

20
 Summary of Traversal Characteristics
Traversal Order Data Structure Used Primary Use Case
Preorder (NLR) Node → Left → Right Stack / Recursion Copying or
serialization
Inorder (LNR) Left → Node → Right Stack / Recursion Sorted order in
BST
Postorder (LRN) Left → Right → Node Stack / Recursion Deletion / postfix
Reverse Preorder (NRL) Node → Right → Left Stack / Recursion Mirror traversal
Reverse Inorder (RNL) Right → Node → Left Stack / Recursion Descending order
Reverse Postorder (RLN) Right → Left → Node Stack / Recursion Mirrored deletions
Level Order Level-wise Queue BFS traversal

21
 Introduction to Heap
1. A heap is a specialized binary tree–based data structure that satisfies the heap property. It is widely used in the
implementation of priority queues, efficient sorting algorithms (like Heap Sort), and several graph algorithms.
2. Basic Terminology
a. Heap Property: In a heap, for any node i, the value of the node is greater than or equal to the values of its
children (in a Max Heap) or less than or equal to the values of its children (in a Min Heap).
b. Max Heap: A heap in which each parent node’s value is greater than or equal to that of its children. Hence,
the largest element is always stored at the root.
c. Min Heap: A heap in which each parent node’s value is less than or equal to that of its children. Hence, the
smallest element is always stored at the root.

3. Types of Heaps: Different types of heaps are designed to optimize performance for specific operations:
a. Binary Heap: The most common form of heap. It is a complete binary tree where each node has at most two
children and follows either the min-heap or max-heap property. Binary heaps are usually stored in array form
for space and access efficiency.
b. Binomial Heap: A collection of binomial trees that obeys the binomial heap properties, primarily used for
implementing mergeable priority queues.
c. Fibonacci Heap: A collection of trees connected via a circular doubly linked list at their roots. Fibonacci heaps
offer better amortized performance than binary heaps for operations like decrease-key and merge, making
them highly suitable for advanced graph algorithms (e.g., Dijkstra’s and Prim’s).

22
 Introduction to Heap
4. Common Heap Operations
Operation Description
Insertion Adds a new element to the heap while maintaining the heap property.
Deletion Removes the root element (min or max) while preserving the heap property.
Peek (Find) Returns the root element (maximum or minimum) without deleting it.
Heapify Converts an arbitrary binary tree or array into a valid heap structure.
Merge Combines two heaps into a single valid heap.
Heap Sort A sorting algorithm that builds a heap and repeatedly extracts the root to obtain a sorted array.
5. Advantages of Heaps
a. Efficient implementation of priority queues.
b. Foundation for Heap Sort, a fast and in-place sorting algorithm.
c. O(1) access to the smallest/largest element.
d. Efficient merging of heaps (especially with Fibonacci or binomial heaps).
6. Disadvantages of Heaps
a. Limited in functionality compared to other data structures like balanced trees.
b. Not ideal for searching arbitrary elements or performing range queries.
c. Updating non-root elements may require additional heapify operations.
7. Applications of Heaps
a. Priority Queues: Managing tasks or processes based on priority.
b. Heap Sort: Efficient sorting of large datasets.
c. Graph Algorithms: Used in algorithms like Dijkstra’s Shortest Path and Prim’s Minimum Spanning Tree.
d. Operating Systems: Process scheduling based on priorities.
e. Network Routing: Selecting next-hop nodes based on minimum cost or highest priority.

23
 Binary Heap
1. A binary heap is a tree-based data structure that satisfies two main properties:
a. Complete Binary Tree Property: All levels of the tree are completely filled, except possibly the last
level, which is filled from left to right.
i. For a node at index i (assuming 1-based indexing), its children are at 2*i and 2*i + 1, and its
parent is at i/2 (integer division).
ii. This property ensures that a binary heap can be efficiently represented using an array.
b. Heap Property: This property defines the ordering of elements within the heap. There are two
types:
i. Min Heap: The value of each parent node is less than or equal to the values of its
children. The smallest element is always at the root.
ii. Max Heap: The value of each parent node is greater than or equal to the values of its
children. The largest element is always at the root.
2. Key Properties
a. Partial Ordering: Binary heaps are partially ordered, not fully sorted. Only the relationship
between parent and child nodes is guaranteed.
b. Completeness: All levels are completely filled except possibly the last, which is filled from left to
right. This property makes binary heaps well-suited for array representation.
c. Heap Property:
i. Min Heap: Each parent node’s value ≤ its children’s values.
ii. Max Heap: Each parent node’s value ≥ its children’s values.
d. Array Representation: For an element stored at index i in the array:
i. Left Child: at index 2i + 1
ii. Right Child: at index 2i + 2
iii. Parent: at index ⌊(i - 1) / 2⌋
24
 Core Operations on Binary Heap
1. Heapify: The process of converting an array void heapify(int arr[], int n, int i) // To heapify a subtree
or binary tree into a valid heap structure. {
// Initialize largest as root
Algorithm:
int largest = i;
HEAPIFY(array, size, i) int l = 2 * i + 1;
largest = i int r = 2 * i + 2;
left = 2 * i + 1 if (l < n && arr[l] > arr[largest]) //If left child is larger than root
largest = l;
right = 2 * i + 2 // If right child is larger than largest so far
if left < size and array[left] > array[largest] if (r < n && arr[r] > arr[largest])
largest = left largest = r;
if right < size and array[right] >
if (largest != i) { // If largest is not root
array[largest] int temp = arr[i];
largest = right arr[i] = arr[largest];
if largest != i arr[largest] = temp;
// Recursively heapify the affected sub-tree
swap(array[i], array[largest]) heapify(arr, n, largest);
HEAPIFY(array, size, largest) }
}
// Function to build a Max-Heap from the given array
To build a Max Heap:
void buildHeap(int arr[], int n) {
BUILD_MAX_HEAP(array, size) int startIdx = (n / 2) - 1; // Index of last non-leaf node
for i = (size / 2) - 1 down to 0 // Perform reverse level order traversal from last non-leaf
HEAPIFY(array, size, i) // node and heapify each node
for (int i = startIdx; i >= 0; i--)
Note: For a Min Heap, comparisons are heapify(arr, n, i);
reversed (< instead of >). }

25
Heapify Operation

26
 Core Operations on Binary Heap
2. Insertion: To insert an element into a heap: // Function to insert a new element into the heap
Algorithm (Max Heap): void insert(MaxHeap *heap, int value) {
INSERT(heap, value) if (heap->size >= MAX_HEAP_SIZE) {
if heap is full printf("Heap Overflow!\n");
report "Heap Overflow" return;
else }
insert value at end of array
size = size + 1 int i = heap->size;
i = size - 1 heap->arr[i] = value;
while i > 0 and heap[i] > heap[parent(i)] heap->size++;
swap(heap[i], heap[parent(i)])
i = parent(i) // Restore heap property by bubbling up
while (i > 0 && heap->arr[i] > heap->arr[(i - 1) / 2])
Note: For a Min Heap, use the condition {
heap[i] < heap[parent(i)]. swap(&heap->arr[i], &heap->arr[(i - 1) / 2]);
Time Complexity: O(log n) i = (i - 1) / 2;
}
}

27
 Core Operations on Binary Heap
4. Deletion (Extract Root): Removes the Binary Heap Implementation
root element (maximum in Max Heap or
#define MAX_HEAP_SIZE 100
minimum in Min Heap).
typedef struct {
Algorithm:
DELETE_ROOT(heap)
int arr[MAX_HEAP_SIZE];
if heap is empty int size;
report "Heap Underflow" } MaxHeap;
else void swap(int *a, int *b) { // Function to swap two elements
root = heap[0] int temp = *a;
heap[0] = heap[size - 1] *a = *b;
size = size - 1 *b = temp;
HEAPIFY(heap, size, 0) }
Time Complexity: O(log n) // Function to heapify a subtree rooted at node i
3. Peek (Find Max/Min): Returns the root void maxHeapify(MaxHeap *heap, int i) {
element without removing it. int largest = i;
PEEK(heap) int left = 2 * i + 1;
return heap[0] int right = 2 * i + 2;
Time Complexity: O(1)
if (left < heap->size && heap->arr[left] > heap->arr[largest])
4. Extract-Max / Extract-Min
largest = left;
a. Extract-Max: Removes and returns
the maximum element from a Max
if (right < heap->size && heap->arr[right] > heap->arr[largest])
Heap. largest = right;
b. Extract-Min: Removes and returns if (largest != i) {
the minimum element from a Min swap(&heap->arr[i], &heap->arr[largest]);
Heap. Both operations follow the maxHeapify(heap, largest);
Delete Root procedure. }
}
28
Core Operations on Binary Heap

29
Core Operations on Binary Heap

30
Core Operations on Binary Heap

31
 Binomial Heap
1. A Binomial Heap is a collection of binomial trees that together satisfy the min-heap (or max-heap)
property. Unlike a binary heap, which is a single complete binary tree, a binomial heap is a forest of smaller
trees that allows efficient merging (union) of two heaps. It combines theoretical elegance with practical
utility in applications like priority queues and graph algorithms such as Dijkstra’s and Prim’s.
2. Binomial Tree: A Binomial Tree, denoted as Bk, is the fundamental building block of a binomial heap. It is
defined recursively as follows:
1. B0 consists of a single node (Nodes = 1, Height = 0).
2. Bk is formed by linking two Bk-1 trees — making the root of one tree the leftmost child of the root of
the other.
3. Properties of a Binomial Tree
a. A binomial tree Bk contains 2k nodes.
b. The height of Bk is k.
𝑘!
c. The number of nodes at depth i is given by 𝑘𝑖 =
𝑖! 𝑘−𝑖 !
d. The root of Bk has k children, which are roots of trees ( B0, B1, …, Bk-1 ).
e. These properties ensure that binomial trees are highly structured and can be merged systematically
— a key advantage over binary heaps.
4. Definition of a Binomial Heap: A Binomial Heap is a collection (or forest) of binomial trees that follows
two essential properties:
a. Heap Property: Each binomial tree satisfies the min-heap (or max-heap) property — i.e., the key of a
parent is smaller (or larger) than its children.
b. Unique Order Property: No two binomial trees in a binomial heap have the same order. Each order
(degree) appears at most once.
c. Structural Property: The binomial heap can be viewed as a linked list of binomial trees arranged in
increasing order of degree.
32
 Binomial Heap
5. Representation: A binomial Binomial Tree B₀: A single node (Nodes = 1, Height = 0).
heap is typically represented Binomial Tree B₁: Formed by linking two B₀ trees — one becomes
as a linked list of roots, each the leftmost child of the other (Nodes = 2, Height = 1).
corresponding to one Binomial Tree B₂: Formed by linking two B₁ trees — the root of
Binomial heap, binomial tree. Each node one becomes the leftmost child of the root of the other (Nodes =
where Bk is a 4, Height = 2). Structure reflects C(2, i) = 1, 2, 1 nodes at each
stores:
binomial heap of depth.
order k. a. A key value Binomial Tree B₃: Formed by linking two B₂ trees — again, the
b. Pointers to its parent, root of one becomes the leftmost child of the other (Nodes = 8,
child, and sibling Height = 3). Each level has C(3, i) = 1, 3, 3, 1 nodes.
c. The degree (order) of
its tree
d. The root list is
maintained in Some binomial
ascending order of tree heaps
degree.
Some binomial heaps

Binomial Heap H (13 nodes): Combining B₀, B₂, and B₃ →

Binomial Heap with 13 Nodes. The binary representation of 13
If a binomial heap (H) is (1101)₂, which means the heap contains: B₃ (8 nodes) + B₂ (4
contains trees B0, B2
nodes) + B₀ (1 node) = 13 nodes total.
and B3, it contains ( 1
1. Each binomial tree corresponds to a set bit position in the
+ 4 + 8 = 13 ) nodes in
total
binary representation of the total node count.
2. Root List (linked in increasing order of degree): B0→B2→ B3
33
 Summary Binomial Heap
1. A Binomial Heap is a forest of min-heaps, where each tree corresponds to a bit position in the binary
representation of the total node count. This elegant structure allows efficient union, insertion, and extract-
min operations — making it foundational for graph algorithms like Dijkstra’s and Prim’s..
2. Interpretation
Tree Order (k) Nodes (2ᵏ) Included? Root Key
B₀ 0 1 ✅ 5
B₁ 1 2 ❌ —
B₂ 2 4 ✅ 2
B₃ 3 8 ✅ 1
Total Nodes — 13 — —
3. How It Works
a. Each root represents a binomial tree of a unique order (0, 2, and 3).
b. The root list is linked by increasing degree (0 → 2 → 3).
c. Every tree independently satisfies the Min-Heap property.
d. When merging heaps, trees of the same order are linked recursively — like adding binary numbers.
4. Conceptual Summary
Aspect Description
Structure Forest of binomial trees (each 2ᵏ nodes)
Heap Property Each tree follows min-heap order
Unique Order Property At most one tree of each order
Representation Linked list of trees by increasing degree
Binary Analogy Binary representation of heap size determines which trees exist
Example (13 = 1101₂) B₃ + B₂ + B₀ trees are present

34
 Binomial Heap
6. Applications of Binomial Heaps: Binomial heaps are especially valuable in situations requiring efficient
priority management and frequent merging of heaps.
a. Priority Queues: Enables fast insertion and extraction of highest/lowest-priority elements.
b. Graph Algorithms: Used in efficient implementations of Dijkstra’s Shortest Path and Prim’s Minimum
Spanning Tree algorithms.
c. Memory Management: Useful in garbage collection and dynamic memory allocation, where merging
operations are frequent.
d. Merging Heaps: Performs better than binary heaps when frequent heap combinations are required.
7. Advantages and Limitations
a. Advantages
i. Efficient merge and union operations compared to binary heaps.
ii. Structured and systematic representation using binomial trees.
iii. Highly suitable for algorithms involving frequent heap merging.
b. Limitations
i. More complex to implement than binary heaps.
ii. Slightly higher constant factors make it less efficient for small datasets.
iii. Not as practical as Fibonacci Heaps for highly dynamic workloads.
8. Illustrative Comparison
Feature Binomial Tree (Bₖ) Binomial Heap
Structure Recursive tree with 2k nodes Forest of binomial trees
Height K Varies per tree
Heap Property Not required Maintained (min or max)
Merge Efficiency O(1) for same-order trees O(log n) for full heaps
Use Case Theoretical concept Practical data structure for priority queues

35
 Operations on Binomial Heaps
1. Insertion: Insert a new key into the heap. Process:
a. Create a new heap containing a single node (the new key).
b. Merge this new heap with the existing one using the Union operation.
c. Adjust to maintain heap and unique-order properties.
d. Time Complexity: O(log n)
2. Union (Merge): Merge two binomial heaps into a single heap. Process:
a. Combine the root lists of both heaps in increasing order of degree.
b. Merge trees of equal order recursively — similar to binary addition, where tree orders correspond to bit
positions.
c. During merging, ensure that the heap property is preserved (the smaller key becomes the parent).
d. Time Complexity: O(log n)
3. Extract-Min: Remove and return the node with the minimum key. Steps:
a. Identify the root with the smallest key.
b. Remove that root from the heap.
c. Reverse the order of its child trees and treat them as a separate binomial heap.
d. Merge this new heap with the remaining heap using Union.
e. Time Complexity: O(log n)
4. Decrease-Key: Decrease the key value of a given node. Steps:
a. Update the node’s key with the new (smaller) value.
b. Compare it with its parent; if the heap property is violated, swap their keys.
c. Continue bubbling up until the heap property is restored.
d. Time Complexity: O(log n)
5. Delete: Delete a given node from the heap. Steps:
a. Perform Decrease-Key on the node, setting its key to ( -\infty ) (or the smallest possible value).
b. Perform Extract-Min to remove it from the heap.
c. Time Complexity: O(log n)
36
 Operations on Binomial Heaps
A Binomial Heap is a collection of binomial trees that /* 1. Create a new node with given key */
satisfy: struct Node *newNode(int key) {
a. Min-heap property (parent ≤ child)
struct Node *temp;
b. Unique degrees (no two trees of same degree)
temp = (struct Node *)malloc(sizeof(struct Node));
1. newNode(int key): Create a new isolated binomial tree
temp->data = key;
node.
temp->degree = 0;
Pseudocode:
procedure NEWNODE(key)
temp->child = temp->parent = temp->sibling = NULL;
node ← allocate Node return temp;
[Link] ← key }
[Link] ← 0
[Link] ← [Link] ← [Link] ← NULL
return node /* 2. Merge two binomial trees of same degree */
struct Node *mergeBinomialTrees(struct Node *b1,
2. mergeBinomialTrees(b1, b2): Combine two binomial struct Node *b2) {
trees of the same degree. Make the smaller key the parent. struct Node *temp;
Pseudocode: if (b1->data > b2->data) {
procedure MERGE_BINOMIAL_TREES(b1, b2) temp = b1;
if [Link] > [Link] then b1 = b2;
swap(b1, b2) b2 = temp;
[Link] ← b1 }
[Link] ← [Link] b2->parent = b1;
[Link] ← b2 b2->sibling = b1->child;
[Link] ← [Link] + 1 b1->child = b2;
return b1 b1->degree++;
return b1;
}
37
 Operations on Binomial Heaps
3. unionBinomialHeap(h1, h2): Merge two root lists /* 3. Union two heaps by merging their root lists sorted by
into one sorted by degree (like merge step of merge degree */
sort). struct Node *unionBinomialHeap(struct Node *h1, struct Node
Pseudocode: *h2) {
procedure UNION_HEAPS(h1, h2) struct Node *newHeap, **pos;
struct Node *curr1, *curr2;
if h1 = NULL return h2
if h2 = NULL return h1 if (!h1) return h2;
create newHeap as empty list if (!h2) return h1;
while h1 ≠ NULL and h2 ≠ NULL
if [Link] ≤ [Link] then newHeap = NULL;
append h1 to newHeap pos = &newHeap;
h1 ← [Link] curr1 = h1;
curr2 = h2;
else
append h2 to newHeap while (curr1 && curr2) {
h2 ← [Link] if (curr1->degree <= curr2->degree) {
append remaining nodes from (h1 or h2) *pos = curr1;
return newHeap curr1 = curr1->sibling;
} else {
*pos = curr2;
curr2 = curr2->sibling;
}
pos = &((*pos)->sibling);
}

*pos = (curr1) ? curr1 : curr2;

return newHeap;
}
38
 Operations on Binomial Heaps
4. adjustHeap(head): Ensures there are no two trees of same /*4. Adjust heap to ensure no two trees have same degree */
degree. If two trees have the same degree, they are merged. struct Node *adjustHeap(struct Node *head) {
Pseudocode: struct Node *prev, *curr, *next;
procedure ADJUST_HEAP(head) prev = NULL;
if head = NULL return NULL curr = head;
prev ← NULL if (!curr) return NULL;
curr ← head next = curr->sibling;
next ← [Link] while (next) {
while next ≠ NULL do /* Case 1: Different degree or next-next has same degree */
if [Link] ≠ [Link] if (curr->degree != next->degree ||
or ([Link] ≠ NULL and [Link] = (next->sibling && next->sibling->degree == curr->degree)) {
[Link]) prev = curr;
prev ← curr curr = next;
curr ← next } else {
else /* Case 2: Merge required */
if [Link] ≤ [Link] then if (curr->data <= next->data) {
[Link] ← [Link] curr->sibling = next->sibling;
curr ← MERGE_BINOMIAL_TREES(curr, next) curr = mergeBinomialTrees(curr, next);
else } else {
if prev = NULL then head ← next if (prev == NULL)
else [Link] ← next head = next;
else
curr ← MERGE_BINOMIAL_TREES(next, curr)
prev->sibling = next;
next ← [Link]
curr = mergeBinomialTrees(next, curr);
return head
}
}
Working:
next = curr->sibling;
a. Scans the merged heap. }
b. If two consecutive trees have the same degree → merge. return head;
c. Maintains unique-degree property. }
39
 Operations on Binomial Heaps
5. insert(heap, key): Insert a new element into the heap. /*5. Insert a new key into the heap */
Pseudocode:
struct Node *insert(struct Node *heap, int key) {
procedure INSERT(heap, key)
temp ← NEWNODE(key)
struct Node *temp, *merged;
heap ← UNION_HEAPS(heap, temp) temp = newNode(key);
heap ← ADJUST_HEAP(heap) merged = unionBinomialHeap(heap, temp);
return heap return adjustHeap(merged);
Working: }
a. Creates a single-node heap.
b. Merges it into existing heap. /*6. Get node with minimum key among roots */
c. Adjusts to maintain properties. struct Node *getMin(struct Node *heap) {
struct Node *min, *curr;
6. getMin(heap): Find and return the root node with smallest if (!heap) return NULL;
key.
Pseudocode: min = heap;
procedure GET_MIN(heap) curr = heap->sibling;
if heap = NULL return NULL
min ← heap
while (curr) {
curr ← [Link]
while curr ≠ NULL do if (curr->data < min->data)
if [Link] < [Link] then min = curr;
min ← curr curr = curr->sibling;
curr ← [Link] }
return min return min;
Working: }
a. Traverses root list.
b. Returns pointer to minimum-key node.

40
 Operations on Binomial Heaps
7. extractMin(heap): Remove and return the /*7. Extract the minimum node from heap */
minimum element from heap. struct Node *extractMin(struct Node *heap) {
struct Node *min, *prevMin, *prev, *curr;
Pseudocode: struct Node *child, *revHeap, *next, *newHeap;
procedure EXTRACT_MIN(heap) if (!heap) return NULL;
min = getMin(heap);
minNode ← GET_MIN(heap) prev = NULL;
remove minNode from root list curr = heap;
reverse [Link] list (children become /* Find min node and its previous node */
while (curr != min) {
separate roots) prev = curr;
newHeap ← UNION_HEAPS(heap, curr = curr->sibling;
}
reversedChildList) /* Remove min from root list */
return ADJUST_HEAP(newHeap) if (prev) prev->sibling = min->sibling;
else heap = min->sibling;
/* Reverse min's child list to form new heap */
child = min->child;
revHeap = NULL;
while (child) {
next = child->sibling;
child->sibling = revHeap;
child->parent = NULL;
revHeap = child;
child = next;
}
/* Union the two heaps */
newHeap = unionBinomialHeap(heap, revHeap);
newHeap = adjustHeap(newHeap);

free(min); /* Optional: free memory of removed node */

return newHeap;
}

/* Decrease the key value of a node */ 41

void decreaseKey(struct Node *heap, struct Node *node, int newKey) {
 Operations on Binomial Heaps
8. decreaseKey(heap, node, key): Decrease a node’s /*8. Decrease the key value of a node */
key and restore heap order. void decreaseKey(struct Node *heap, struct Node *node, int
newKey) {
Pseudocode:
int temp;
procedure DECREASE_KEY(heap, node, newKey) struct Node *parent;
if newKey > [Link] then return
[Link] ← newKey if (!heap || !node) return;
if (newKey > node->data) return;
while [Link] ≠ NULL and [Link] <
[Link] do node->data = newKey;
swap([Link], [Link]) parent = node->parent;
node ← [Link] /* Bubble up until heap property restored */
while (parent && node->data < parent->data) {
9. deleteKey(heap, node): Delete a given node by temp = node->data;
node->data = parent->data;
decreasing its key to -∞ and calling extractMin(). parent->data = temp;
Pseudocode: node = parent;
procedure DELETE_KEY(heap, node) parent = node->parent;
}
DECREASE_KEY(heap, node, -∞)
}
heap ← EXTRACT_MIN(heap)
/*9. Delete a given node from the heap */
void deleteKey(struct Node **heap, struct Node *node) {
if (!(*heap) || !node) return;

/* Decrease key to negative infinity and extract min */

node->data = INT_MIN;
decreaseKey(*heap, node, INT_MIN);
*heap = extractMin(*heap);
}
42
 Operations on Binomial Heaps
10. printTree() and printHeap(): Recursive display of /*10. Recursive printing of a binomial tree */
heap structure. void printTree(struct Node *h) {
Pseudocode: struct Node *curr;
procedure PRINT_TREE(node) curr = h;
while node ≠ NULL do
print([Link]) while (curr) {
PRINT_TREE([Link]) printf("%d ", curr->data);
node ← [Link] printTree(curr->child);
curr = curr->sibling;
procedure PRINT_HEAP(heap) }
print "Binomial Heap:" }
while heap ≠ NULL do
print "B", [Link], ": " /* Print the entire heap with its binomial trees */
PRINT_TREE(heap) void printHeap(struct Node *h) {
heap ← [Link] struct Node *curr;
curr = h;

printf("\nBinomial Heap:\n");
while (curr) {
printf("B%d: ", curr->degree);
printTree(curr);
printf("\n");
curr = curr->sibling;
}
}

43
 Fibonacci Heap
1. A Fibonacci Heap is an advanced heap-based data structure consisting of a collection of trees that satisfy the min-
heap or max-heap property. Unlike binary or binomial heaps, Fibonacci heaps are designed to achieve better
amortized time complexity for several key operations.
2. They are called Fibonacci heaps because the structure and number of nodes in each tree are related to the
Fibonacci sequence. Specifically, a tree of order n in a Fibonacci heap has at least Fn+2 nodes, where Fn+2 denotes
the (n + 2)th Fibonacci number.
3. Key Characteristics
a. A Fibonacci heap is a set of heap-ordered trees, where each parent node’s key is smaller (for min-heaps) or
larger (for max-heaps) than its children’s keys.
b. Min Pointer: A pointer to the minimum node (min[H]) is maintained for O(1) access to the minimum
element.
c. Marked Nodes: Nodes are marked to track whether they have lost a child, which aids in maintaining heap
properties during cascading cuts.
d. Collection of Trees: Like a binomial heap, but trees do not have fixed shapes; they can be single nodes or
complex multi-level trees. The trees in a Fibonacci heap are unordered but rooted.
e. Each tree can have any number of children, allowing for flexible structure and faster amortized operations.
4. Memory Representation
a. The roots of all trees are linked together using a circular doubly linked list, allowing fast insertion and
concatenation.
b. Each node contains pointers for:
i. Its parent
ii. One of its children
iii. Its left and right siblings (in a circular linked list)
c. Advantages of Circular Doubly Linked List
i. O(1) time for deleting a node from the root or child list.
ii. O(1) time for concatenating two lists during heap union operations.
44
 Fibonacci Heap
5. Node Structure: Each node x in a Fibonacci Heap stores the following fields:
Field Description
key[x] Key or value of the node
degree[x] Number of children of the node
p[x] Pointer to the parent node
child[x] Pointer to any one of its children
left[x], right[x] Pointers to the left and right siblings in the circular list
mark[x] Boolean flag indicating if a child was lost since last becoming a child of another node
6. Overall Heap Structure
a. Each Fibonacci Heap H consists of a root list, which is a circular doubly linked list containing the roots of
all the trees. The pointer min[H] refers to the root node containing the smallest key in the heap.
b. There are two main advantages of using a circular doubly linked list.
i. Deleting a node from the tree takes O(1) time.
ii. The concatenation of two such lists takes O(1) time.

In a fibonacci heap, a node can have more

than two children or no children at all. Also,
it has more efficient heap operations than
that supported by the binomial and binary
heaps.

45
 Operations on Fibonacci Heap
1. createNode(int key): Creates a new standalone node /*1. Create new node */
forming a circular doubly linked list (self-pointing left Node* createNode(int key) {
and right). Initially, it has no parent or child, degree = 0 Node *node;
(no children), and mark = 0 (unmarked). node = (Node*)malloc(sizeof(Node));
📘 Pseudocode: node->key = key;
procedure CREATE_NODE(key) node->degree = 0;
allocate new node
node->mark = 0;
[Link] ← key
node->parent = node->child = NULL;
[Link] ← 0
[Link] ← 0 node->left = node->right = node;
[Link] ← NULL return node;
[Link] ← NULL }
[Link] ← node
[Link] ← node /*2. Create new empty heap */
return node FibonacciHeap* createHeap() {
FibonacciHeap *heap;
2. createHeap(): Creates an empty heap with no nodes heap =
and undefined minimum pointer. (FibonacciHeap*)malloc(sizeof(FibonacciHeap));
Pseudocode: heap->min = NULL;
procedure CREATE_HEAP() heap->nodeCount = 0;
allocate heap return heap;
[Link] ← NULL }
[Link] ← 0
return heap

46
 Operations on Fibonacci Heap
3. insert(H, x): Inserts a new node into the root list of the heap
in O(1) time. If the new key is smaller than the current
minimum, the min pointer is updated.
Pseudocode:
procedure INSERT(H, x)
if [Link] == NULL:
[Link] ← x
else:
insert x into root list (next to [Link])
if [Link] < [Link]:
[Link] ← x
[Link] ← [Link] + 1
Time Complexity: O(1)
/*3. Insert node into heap */
void insert(FibonacciHeap *heap, Node *x) {
Node *temp;
if (heap->min == NULL) {
heap->min = x;
} else {
temp = heap->min->left;
heap->min->left = x;
x->right = heap->min;
x->left = temp; Steps
temp->right = x; a. Create a new node for the element.
if (x->key < heap->min->key) b. If the heap is empty, make the new node the root
heap->min = x; and mark it as min.
} c. Otherwise, insert it into the root list and update
heap->nodeCount++;
min[H] if necessary.
}
47
 Operations on Fibonacci Heap
4. unionHeap(H1, H2): Merges two Fibonacci heaps by
concatenating their circular root lists. The global minimum
pointer is updated to the smallest key. Node counts are
summed. No tree linking occurs, so this is a constant-time
union.
Pseudocode:
procedure UNION_HEAP(H1, H2)
if [Link] == NULL then
return H2
if [Link] == NULL then
return H1
// Concatenate the root lists /* Union of two heaps */
temp1 ← [Link] FibonacciHeap* unionHeap(FibonacciHeap *H1, FibonacciHeap
temp2 ← [Link] *H2) {
[Link] ← temp2 Node *temp1, *temp2;
[Link] ← temp1 if (H1->min == NULL) return H2;
[Link] ← [Link] if (H2->min == NULL) return H1;
[Link] ← [Link] temp1 = H1->min->right;
// Update minimum pointer temp2 = H2->min->left;
if [Link] < [Link] then H1->min->right->left = temp2;
[Link] ← [Link] H2->min->left->right = temp1;
// Update total node count H1->min->right = H2->min;
[Link] ← [Link] + [Link] H2->min->left = H1->min;
// Free H2 header if (H2->min->key < H1->min->key)
free(H2) H1->min = H2->min;
return H1 H1->nodeCount += H2->nodeCount;
end procedure free(H2);
Time complexity: O(1). return H1;
}
48
 Operations on Fibonacci Heap
5. linkFibNodes(H, y, x): This function links two /*5. Link two trees of same degree */
trees of the same degree — the root y with the void linkHeaps(FibonacciHeap *heap, Node *y,
larger key becomes a child of the root x (smaller Node *x) {
key), ensuring min-heap order. Used during Node *temp;
consolidation after extracting the minimum. y->left->right = y->right;
y->right->left = y->left;
Pseudocode: y->parent = x;
procedure LINK_FIB_NODES(H, y, x) if (x->child == NULL) {
remove y from root list x->child = y;
make y a child of x y->left = y->right = y;
[Link] ← [Link] + 1 } else {
[Link] ← 0 temp = x->child->right;
x->child->right = y;
y->left = x->child;
y->right = temp;
temp->left = y;
}
x->degree++;
y->mark = 0;
}

49
 Operations on Fibonacci Heap
6. consolidate(H): After removing minimum node, multiple do {
trees may have same degree. It merges trees of equal degree int d = x->degree;
iteratively (via linkFibNodes) until all trees in the root list have next = x->right;
while (A[d] != NULL) {
unique degrees. This restores the Fibonacci Heap property. y = A[d];
Pseudocode: if (x->key > y->key) {
procedure CONSOLIDATE(H) temp = x;
create array A[0...D] initialized to NULL x = y;
for each node w in root list do y = temp;
x←w }
linkHeaps(heap, y, x);
d ← [Link] A[d] = NULL;
while A[d] ≠ NULL do d++;
y ← A[d] }
if [Link] > [Link]: A[d] = x;
swap(x, y) x = next;
LINK_FIB_NODES(H, y, x) } while (x != heap->min);
heap->min = NULL;
A[d] ← NULL for (i = 0; i < D; i++) {
d←d+1 if (A[i] != NULL) {
A[d] ← x if (heap->min == NULL) {
rebuild root list from all non-null entries in A[] A[i]->left = A[i]->right = A[i];
update [Link] heap->min = A[i];
} else {
temp = heap->min->right;
/*6. Consolidate root list after extractMin */ heap->min->right = A[i];
void consolidate(FibonacciHeap *heap) { A[i]->left = heap->min;
int D, i; A[i]->right = temp;
Node *A[50], *x, *y, *temp, *next; temp->left = A[i];
D = 50; if (A[i]->key < heap->min->key)
for (i = 0; i < D; i++) A[i] = NULL; heap->min = A[i];
}
x = heap->min; }
if (x == NULL) return; }
} 50
 Operations on Fibonacci Heap
7. extractMin(H): Removes and returns the minimum /*7. Extract-Min operation */
node (z). Its children are promoted to the root list. Node* extractMin(FibonacciHeap *heap) {
Afterward, trees in the root list are consolidated to Node *z, *x, *next;
z = heap->min;
restore heap structure.
if (z != NULL) {
Pseudocode: x = z->child;
procedure EXTRACT_MIN(H) if (x != NULL) {
z ← [Link] do {
if z ≠ NULL: next = x->right;
for each child x of z: x->parent = NULL;
add x to root list of H x->left = heap->min;
x->right = heap->min->right;
[Link] ← NULL
heap->min->right->left = x;
remove z from root list heap->min->right = x;
if z == [Link]: x = next;
[Link] ← NULL } while (x != z->child);
else: }
[Link] ← [Link] z->left->right = z->right;
CONSOLIDATE(H) z->right->left = z->left;
if (z == z->right)
[Link] ← [Link] - 1
heap->min = NULL;
return z else {
Time complexity: O(log n) amortized. heap->min = z->right;
consolidate(heap);
}
heap->nodeCount--;
}
return z;
}
51
Operations on Fibonacci Heap

52
 Operations on Fibonacci Heap
8. cut(H, x, y): When a node’s key becomes smaller than /*8. Cut node x from parent y and add to root list */
its parent (heap order violation), cut() removes x from void cut(FibonacciHeap *heap, Node *x, Node *y) {
Node *temp;
y's child list and moves it to the root list. This ensures if (x->right == x) y->child = NULL;
the min-heap property is restored. else {
Pseudocode: if (y->child == x)
procedure CUT(H, x, y) y->child = x->right;
x->left->right = x->right;
remove x from y's child list x->right->left = x->left;
[Link] ← [Link] - 1 }
add x to root list of H y->degree--;
[Link] ← NULL temp = heap->min->right;
heap->min->right = x;
[Link] ← 0
x->left = heap->min;
9. cascadingCut(H, y): Ensures that trees remain x->right = temp;
balanced. If a node loses two children in succession, it temp->left = x;
is cut from its parent as well. This process cascades x->parent = NULL;
upward until either the root is reached or an unmarked x->mark = 0;
}
node is encountered. /*9. Cascading Cut */
Pseudocode: void cascadingCut(FibonacciHeap *heap, Node *y) {
procedure CASCADING_CUT(H, y) Node *z;
z ← [Link] z = y->parent;
if (z != NULL) {
if z ≠ NULL: if (y->mark == 0) y->mark = 1;
if [Link] == 0: else {
[Link] ← 1 cut(heap, y, z);
else: cascadingCut(heap, z);
}
CUT(H, y, z)
}
CASCADING_CUT(H, z) }
53
 Operations on Fibonacci Heap
10. decreaseKey(H, x, newKey): Reduces key of a given
node. If this violates heap order, node is cut and moved to
root list. If needed, cascading cuts are triggered up the tree.
Pseudocode:
procedure DECREASE_KEY(H, x, newKey)
if newKey > [Link]:
error "Invalid operation"
[Link] ← newKey
y ← [Link]
if y ≠ NULL and [Link] < [Link]:
CUT(H, x, y)
CASCADING_CUT(H, y)
if [Link] < [Link]:
[Link] ← x
Time complexity: O(1) amortized.

Decrease-Key
1. Select the node to be decreased, x, and change its
value to the new value k. Cut
2. If the parent of x, y, is not null and the key of parent is 1. Remove x from current position and add it to the root
greater than that of the k then list.
call Cut(x) and Cascading-Cut(y) subsequently. 2. If x is marked, then mark it as false.
3. If key of x is smaller than key of min, then mark x as
min. Cascading-Cut: If the parent of y is not null then follow the
following steps.
1. If y is unmarked, then mark y.
2. Else, call Cut(y) and Cascading-Cut(parent of y).
54
 Operations on Fibonacci Heap
/* 10. Decrease-Key operation */
void decreaseKey(FibonacciHeap *heap, Node *x, int
newKey) {
Node *y;
if (newKey > x->key) {
printf("New key is greater than current key!\n");
return;
}
x->key = newKey;
y = x->parent;
if (y != NULL && x->key < y->key) {
cut(heap, x, y);
cascadingCut(heap, y);
}
if (x->key < heap->min->key) heap->min = x;
}

55
 Operations on Fibonacci Heap
11. deleteNode(H, x): To delete a node, we first /*11. Delete a node */
decrease its key to −∞, making it the minimum void deleteNode(FibonacciHeap *heap, Node *x) {
element, then remove it using extractMin(). Time decreaseKey(heap, x, INT_MIN);
complexity: O(log n) amortized. extractMin(heap);
Pseudocode: }
procedure DELETE_NODE(H, x)
DECREASE_KEY(H, x, -∞) /*12. Print root list of heap */
EXTRACT_MIN(H) void printHeap(FibonacciHeap *heap) {
Node *temp;
if (heap->min == NULL) {
12. printHeap(H): Prints all keys in the root list of the
printf("Heap is empty!\n");
Fibonacci Heap (not full child hierarchy). Used mainly
for debugging and visualization.
return;
}
Pseudocode:
printf("Fibonacci Heap Root List: ");
procedure PRINT_HEAP(H) temp = heap->min;
if [Link] == NULL: do {
print "Heap is empty" printf("%d ", temp->key);
else: temp = temp->right;
for each node temp in root list do } while (temp != heap->min);
print [Link] printf("\n");
}

56
 Comparison of Heaps
Feature Binary Heap Binomial Heap Fibonacci Heap
Structure Single complete binary tree, Forest of binomial Forest of unordered, heap-
typically in an array trees, linked by roots ordered trees, linked by roots
Insert 𝑂(log𝑛) Amortized 𝑂(1), Amortized 𝑂(1)
worst-case 𝑂(log𝑛)
Extract Min 𝑂(log𝑛) 𝑂(log𝑛) Amortized 𝑂(log𝑛)
Merge Not efficient, 𝑂(𝑛) 𝑂(log𝑛) Amortized 𝑂(1)
for two heaps
Decrease Key 𝑂(log𝑛) 𝑂(log𝑛) Amortized 𝑂(1)
Practical Use Simple to implement, good Useful when Excellent theoretical
all-around performance for frequent merging of performance for specific
priority queues heaps is required algorithms like Dijkstra's, but
complex and slower in practice
due to higher constant factors
Key Takeaways
1. Binary Heap: Best for simple priority queues and in-place sorting.
2. Binomial Heap: Optimized for frequent merging and dynamic operations.
3. Fibonacci Heap: Optimized for decrease-key and union operations, ideal for theoretical
algorithmic efficiency in graph algorithms, but more complex to implement.

57
 Binary Search Tree (BST)
1. A Binary Search Tree (BST) is a specialized hierarchical data structure that facilitates efficient searching,
insertion, and deletion operations. Each node in a BST can have at most two children — a left child and a right
child — and the structure adheres to specific ordering rules that make data retrieval extremely efficient.
2. Core Properties of a BST
a. Left Subtree Property: Every node in the left subtree of a node contains a value less than that of the
node itself.
b. Right Subtree Property: Every node in the right subtree contains a value greater than or equal to that of
the node itself.
Note: This ordered structure ensures that lookup, insertion, and deletion operations can be performed in
O(log n) time on average for a balanced BST, where n is the number of nodes. However, in the worst case—
when the tree becomes skewed—the complexity can degrade to O(n).
3. Historical Background: The Binary Search Tree was independently developed by multiple researchers,
including P.F. Windley, Andrew Donald Booth, Andrew Colin, and Thomas N. Hibbard. The foundational
algorithm is attributed to Conway Berners-Lee and David Wheeler, who used it in 1960 for storing labeled
data on magnetic tapes. Among the earliest and most influential BST algorithms is Hibbard’s deletion
algorithm, which remains an important concept in computer science.

58
 Binary Search Tree (BST)
4. Key Characteristics of a Binary Search Tree
a. Hierarchical Structure: A BST consists of interconnected nodes arranged in a hierarchical fashion
with a single root node at the top and subtrees branching downward.
b. Ordering Property: The left subtree always holds smaller values, and the right subtree holds larger
values, maintaining an inherent ordering throughout the structure.
c. Efficiency: Operations like search, insert, and delete can all be achieved in O(log n) time for
balanced BSTs and O(n) in the worst case (unbalanced trees). Self-balancing trees guarantee O(log
n) even in the worst case.
d. Recursive Nature: Each subtree (left or right) of a node is itself a BST, enabling elegant and
naturally recursive algorithms.
e. Wide Applicability: BSTs are used in database indexing, symbol tables, search engines, range
queries, and as a basis for more advanced structures like AVL Trees, Red-Black Trees, and Splay
Trees.
5. Fundamental Properties
a. Duplicates are generally not allowed, as each element must be uniquely ordered.
b. Inorder traversal of a BST produces elements in sorted ascending order.
c. Average height: O(log n) for balanced trees.
d. Worst-case height: O(n), when the tree degenerates into a linear chain (skewed).
6. Applications of Binary Search Trees
a. Efficient searching and indexing (e.g., in maps and sets)
b. Dynamic sorting and range queries
c. Symbol table management in compilers and interpreters
d. Hierarchical data organization in operating systems and databases
e. Building blocks for self-balancing trees such as AVL, Red-Black, and Splay Trees
59
 Binary Search Tree (BST)
7. Advantages of BST
a. Efficient Searching: O(log n) in balanced form.
b. Ordered Data Storage: Inherent sorted arrangement enables quick access to next or previous elements.
c. Dynamic Operations: Supports insertion and deletion without full data reorganization.
d. Balanced Variants: Self-balancing BSTs maintain consistent logarithmic performance.
e. Dual Priority Support: Maximum and minimum elements can be efficiently maintained.
8. Disadvantages of BST
a. Lack of Self-Balancing (in basic BST): Can degenerate into a linear structure if input data is sorted.
b. Performance Degradation: Worst-case time complexity can reach O(n).
c. Memory Overhead: Requires pointers for left and right child nodes.
d. Scalability Issues: Inefficient for massive datasets without balancing mechanisms.
e. Functional Limitations: Designed primarily for search, insert, and delete operations.
9. Tree Traversals: BSTs can be traversed in several ways:
Traversal Type Order of Visiting Nodes Remarks
Inorder Left → Root → Right Produces sorted order of elements in a BST
Preorder Root → Left → Right Useful for copying or serializing the tree
Postorder Left → Right → Root Used for deleting the tree or evaluating expressions
Level-order Level by Level (using Queue) Traverses nodes breadth-first

10. In Essence: A Binary Search Tree forms the conceptual foundation for many advanced data structures. Its
recursive nature, inherent ordering, and ability to dynamically manage sorted data make it an indispensable
tool in computer science. Though a simple BST may suffer from imbalance in certain cases, its self-balancing
extensions (AVL, Red-Black Trees, Splay Trees) ensure consistent, high-performance operations across a broad
range of applications.

60
 Core Operations in a BST
1. Insertion: Inserts a new node while preserving BST properties.
a. Process:
i. Start at the root and compare the key with the current node.
ii. Move left if smaller, right if larger.
iii. Insert the new node at the appropriate empty spot.
b. Complexity:
i. Time: O(h), (O(log n) for balanced, O(n) for skewed trees)
ii. Space: O(h), (recursive stack)

61
 Core Operations in a BST
2. Search: Determines whether a specific key exists in the tree.
a. Process:
i. Compare the target key with the root.
ii. If equal, the key is found.
iii. If smaller, search the left subtree.
iv. If larger, search the right subtree.
v. Continue recursively or iteratively until the key is found or a null node is reached.
b. Complexity:
i. Average case: O(log n)
ii. Worst case: O(n)
iii. Auxiliary space: O(h) for recursion, where h = tree height; O(1) for iterative approach.

62
 Core Operations in a BST
3. Deletion: Removes a node from the BST while maintaining its structural integrity. The deletion logic depends
on the number of children of the node to be deleted:
a. Node with No Children (Leaf Node): Simply remove the node since it does not affect any subtree.

b. Node with One Child: Delete the node and link its parent directly to child, preserving BST property.

63
 Core Operations in a BST
3. Deletion: Removes a node from the BST while maintaining its structural integrity. The deletion logic depends on the number
of children of the node to be deleted:
c. Node with Two Children:
i. Find a replacement node—either the inorder successor (smallest node in the right subtree) or the inorder
predecessor (largest node in the left subtree).
ii. Replace the target node’s value with the replacement node’s value.
iii. Delete the replacement node (which will now fall into Case 1 or Case 2).
iv. Complexity: Time: O(h), Space: O(h)

Summary of Complexities
Operation Average Time Complexity Worst Case Space Complexity
Search O(log n) O(n) O(h)
Insertion O(log n) O(n) O(h)
Deletion O(log n) O(n) O(h)
Traversal O(n) O(n) O(h)
64
 Operations on BST
1. createNode(value): Used as a helper function whenever /*-------------------------------------------------------------
a new node is to be added in the BST. Function: createNode
Pseudo Code: Purpose : Create and return a new BST node
Procedure createNode(value) -------------------------------------------------------------*/
Create memory for new node struct node* createNode(int value) {
Set [Link] = value struct node *newNode;
Set [Link] = NULL newNode = (struct node*) malloc(sizeof(struct node));
Set [Link] = NULL newNode->key = value;
Return node newNode->left = NULL;
EndProcedure newNode->right = NULL;
Time Complexity: O(1) Space Complexity: O(1) return newNode;
2. insert(root, value) : Inserts the node such that the BST }
property is maintained (left < root < right). /*-------------------------------------------------------------
Pseudo Code: Function: insert
Procedure insert(root, value) Purpose : Insert a node into the BST
If root = NULL then -------------------------------------------------------------*/
root ← createNode(value) struct node* insert(struct node *root, int value) {
Else If value < [Link] then if (root == NULL)
[Link] ← insert([Link], value) return createNode(value);
Else If value > [Link] then
[Link] ← insert([Link], value) if (value < root->key)
EndIf root->left = insert(root->left, value);
Return root else if (value > root->key)
EndProcedure root->right = insert(root->right, value);
Time Complexity: Best / Average: O(log n) (for balanced return root;
BST), Worst: O(n) (for skewed BST) }
Space Complexity: O(h) (where h = height of BST)
65
 Operations on BST
3. search(root, key): To check if a particular value exists in /*-------------------------------------------------------------
the BST. Function: search
Pseudo Code: Purpose : Search for a key in the BST
Procedure search(root, key) -------------------------------------------------------------*/
If root = NULL or [Link] = key then struct node* search(struct node *root, int key) {
Return root if (root == NULL || root->key == key)
Else If key < [Link] then
return root;
Return search([Link], key)
if (key < root->key)
Else
Return search([Link], key) return search(root->left, key);
EndIf else
EndProcedure return search(root->right, key);
Time Complexity: Best / Average: O(log n), Worst: O(n) }
Space Complexity: O(h)
4. minValueNode(node): Commonly used during node /*-------------------------------------------------------------
deletion to find the inorder successor (smallest node in Function: minValueNode
right subtree). Purpose : Find the node with the smallest key
Pseudo Code: (leftmost)
Procedure minValueNode(node) -------------------------------------------------------------*/
Set current ← node struct node* minValueNode(struct node *node) {
While [Link] ≠ NULL do struct node *current;
current ← [Link] current = node;
EndWhile
while (current != NULL && current->left != NULL)
Return current
current = current->left;
EndProcedure
Time Complexity: O(h) return current;
Space Complexity: O(1) }
66
 Operations on BST
5. deleteNode(root, key): Handles 3 cases, when target node is /*-------------------------------------------------------------
found: Function: deleteNode
a. No child: Node is deleted directly. Purpose : Delete a node from the BST
b. One child: Node is replaced by its child. -------------------------------------------------------------*/
c. Two children: Node key is replaced with its inorder successor,
struct node* deleteNode(struct node *root, int key) {
and successor node is deleted recursively.
struct node *temp;
Procedure deleteNode(root, key)
If root = NULL then
if (root == NULL)
Return root return root;
Else If key < [Link] then if (key < root->key)
[Link] ← deleteNode([Link], key) root->left = deleteNode(root->left, key);
Else If key > [Link] then else if (key > root->key)
[Link] ← deleteNode([Link], key) root->right = deleteNode(root->right, key);
Else else {
If [Link] = NULL then if (root->left == NULL) {
temp ← [Link] temp = root->right;
Free(root) free(root);
Return temp return temp;
Else If [Link] = NULL then
}
temp ← [Link]
else if (root->right == NULL) {
Free(root)
Return temp
temp = root->left;
EndIf free(root);
temp ← minValueNode([Link]) return temp;
[Link] ← [Link] }
[Link] ← deleteNode([Link], [Link]) temp = minValueNode(root->right);
EndIf root->key = temp->key;
Return root root->right = deleteNode(root->right, temp->key);
EndProcedure }
Time Complexity: Best / Average: O(log n), Worst: O(n) return root;
Space Complexity: O(h) }
67
 Operations on BST
6. inorder(root): Performs Left → Root → Right traversal, /* Function: inorder----------------------------------*/
Procedure inorder(root) void inorder(struct node *root) {
If root ≠ NULL then
if (root != NULL) {
inorder([Link])
Print [Link]
inorder(root->left);
inorder([Link]) printf("%d ", root->key);
EndIf inorder(root->right);
EndProcedure }
Time Complexity: O(n), Space Complexity: O(h) }
/* Function: preorder ------------------------------*/
7. preorder(root): Performs Root → Left → Right traversal.
void preorder(struct node *root) {
Procedure preorder(root)
If root ≠ NULL then
if (root != NULL) {
Print [Link] printf("%d ", root->key);
preorder([Link]) preorder(root->left);
preorder([Link]) preorder(root->right);
EndIf }
EndProcedure }
Time Complexity: O(n), Space Complexity: O(h)
/* Function: postorder-------------------------------*/
8. postorder(root): Performs Left → Right → Root traversal.
void postorder(struct node *root) {
Procedure postorder(root) if (root != NULL) {
If root ≠ NULL then postorder(root->left);
postorder([Link]) postorder(root->right);
postorder([Link]) printf("%d ", root->key);
Print [Link] }
EndIf
}
EndProcedure
Time Complexity: O(n), Space Complexity: O(h)
68
 Tree Sort
1. Tree Sort is a comparison-based sorting algorithm that leverages the properties of a Binary Search Tree (BST) to
arrange elements in ascending or descending order.
a. The fundamental idea is to insert all elements of the input list or array into a BST and then perform an in-order
traversal of the tree to retrieve the elements in sorted order.
b. Since the in-order traversal of a BST naturally visits the nodes in increasing order, Tree Sort effectively converts
unsorted data into sorted data through this structured traversal.
2. Algorithm Steps
a. Input the Elements: Begin by taking the input elements and storing them in an array or list.
b. Construct the Binary Search Tree: Insert each element from the array into a Binary Search Tree following the
BST property:
a. Elements smaller than the current node go to the left subtree.
b. Elements greater than the current node go to the right subtree.
c. Perform In-order Traversal: Traverse the BST in in-order sequence (Left → Root → Right) to obtain the elements
in sorted order.
3. Complexity Analysis
a. Best Case (Balanced Tree): O(n log n)
b. Average Case: O(n log n)
c. Worst Case (Skewed Tree): O(n²)
4. Applications of Tree Sort
a. Online Sorting: Efficient when data is received incrementally; maintains a dynamically sorted dataset.
b. Adaptive Sorting (Splaysort): Using a Splay Tree instead of a normal BST makes the algorithm adaptive —
performing better on nearly sorted datasets.
c. Useful in Symbol Tables & Databases: Where continuous insertions and sorted retrievals are required.
5. Key Advantages
a. Maintains data in sorted order as elements are inserted.
b. Easy to adapt for both ascending and descending sorts.
c. Can efficiently handle dynamic data sets when combined with self-balancing trees like AVL or Splay trees.
69
 Tree Sort
9. treeSort(arr[], n): Constructs a BST by inserting /*-------------------------------------------------------------
all array elements. Then performs inorder Function: treeSort
traversal to display elements in ascending Purpose : Sort an array using Tree Sort technique
-------------------------------------------------------------*/
(sorted) order.
void treeSort(int arr[], int n) {
Pseudo Code: struct node *root;
Procedure treeSort(arr[], n) int i;
root ← NULL
For i ← 0 to n-1 do root = NULL;
root ← insert(root, arr[i])
EndFor /* Step 1: Build BST from array elements */
Print "Sorted order: " for (i = 0; i < n; i++)
root = insert(root, arr[i]);
inorder(root)
EndProcedure /* Step 2: Perform inorder traversal to display sorted
elements */
Time Complexity: printf("\nSorted order using Tree Sort: ");
a. Best / Average: O(n log n) inorder(root);
b. Worst: O(n²) (if input array is already sorted printf("\n");
and BST becomes skewed) }
Space Complexity: O(n) (for BST node storage)

70
 Threaded Binary Search Tree (TBST)
1. A Threaded Binary Search Tree (TBST) is an enhanced version
of a traditional Binary Search Tree (BST) designed to make in-
order traversal faster and more memory-efficient.
a. In a regular BST, many of the left or right pointers—
particularly in leaf nodes—are NULL, indicating the
absence of children.
b. A Threaded BST replaces these NULL pointers with
threads, which are special links pointing to a node’s in-
order predecessor or in-order successor.
2. This simple idea eliminates the need for recursion or a stack during traversal, enabling O(n) traversal time with
O(1) auxiliary space.
a. In a normal BST:
i. In-order traversal (Left → Root → Right) requires recursion or an explicit stack.
ii. Traversal can be time-efficient but consumes extra memory.
b. In a Threaded BST:
i. Each NULL pointer is replaced with a thread that connects nodes according to their in-order
sequence.
ii. Traversal can be done iteratively, without recursion or stacks, by following these threads.
3. Key Characteristics
a. Threads
i. If a node’s left child is NULL, its left pointer is replaced with a link to its in-order predecessor.
ii. If a node’s right child is NULL, its right pointer links to its in-order successor.
b. Thread Indicators (Flags) Each node contains boolean flags to distinguish between child pointers and
threads:
bool isLeftThread; // True if left pointer is a thread
bool isRightThread; // True if right pointer is a thread
71
 Threaded Binary Search Tree (TBST)
3. Key Characteristics
a. Dummy (Sentinel) Node (optional but common)
i. Simplifies traversal logic.
ii. Its left pointer points to the root, and its right pointer points to itself.
iii. The leftmost node’s left thread and rightmost node’s right thread also point to this dummy node.
b. Thread Indicators (Flags) Each node contains boolean flags to distinguish between child pointers and threads:
bool isLeftThread; // True if left pointer is a thread
bool isRightThread; // True if right pointer is a thread
4. Types of Threaded Binary Search Trees
a. Single-Threaded BST
i. Only one set of NULL pointers (usually right pointers) is replaced with threads.
ii. Right threads link nodes to their in-order successors.
iii. Enables efficient forward traversal.
b. Double-Threaded BST
i. Both left and right NULL pointers are replaced with threads.
ii. Left threads point to in-order predecessors, and right threads point to in-order successors.
iii. Enables bidirectional traversal (both forward and backward).
5. Node Structures
Single-Threaded Node: Double-Threaded Node:
struct Node { struct Node {
int data; int data;
struct Node *left; struct Node *left, *right;
struct Node *right; bool leftThread;
bool rightThread; bool rightThread;
}; };

72
 Threaded Binary Search Tree (TBST)
6. Advantages of TBST
a. Efficient Traversal: Enables in-order traversal without recursion or stack.
b. Memory Optimization: Reuses NULL pointers, minimizing wasted space.
c. Bidirectional Access: Allows both forward and reverse in-order traversal (for double-threaded trees).
d. Fast Successor/Predecessor Access: Provides direct access to neighboring nodes.
e. Parent Retrieval: Parent nodes can often be determined without explicit parent pointers.
7. Disadvantages of TBST
a. Complex Insertion/Deletion: Thread management complicates node updates.
b. Memory Overhead: Requires additional flags per node.
c. Harder Maintenance: Thread consistency must be carefully maintained.
d. Limited Flexibility: Modifying structure can break thread links.
e. Difficult Parallelization: Thread dependencies reduce concurrency potential.
8. Applications of Threaded Binary Trees
a. Expression Evaluation: Simplifies evaluation of arithmetic expressions without recursion.
b. Database Indexing: Enables fast, in-order record retrieval.
c. Symbol Table Management: Common in compilers for efficient variable lookup.
d. Disk-Based Structures: Improves data locality, reducing disk I/O.
e. Hierarchical Navigation: Used in file systems or XML document trees for linear traversal.
9. In Essence
a. A Threaded Binary Search Tree transforms unused NULL pointers in a traditional BST into valuable
connectors that preserve in-order relationships between nodes. This design allows for stack-free,
recursion-free traversal while maintaining efficient search, insert, and delete operations.
b. By efficiently linking each node with its neighbors, TBSTs offer a clean, memory-optimized, and
traversal-friendly structure — ideal for systems where memory or performance constraints make
recursion undesirable.
73
 In-Order Traversal in TBST
1. Traditional BST Traversal
a. Uses recursion or stack.
b. Traversal order: Left → Root → Right.
2. TBST Traversal
a. Follows threads directly to move to the next in-order node.
b. No recursion or stack required.
3. Algorithm for In-Order Traversal
a. Start from the leftmost node.
b. Repeat until all nodes are visited:
i. Visit (process) the current node.
ii. If the current node’s rightThread is true, move to its threaded successor.
iii. Otherwise, move to the leftmost node in its right subtree.
4. Pseudo Code:
void inorderTraversal(struct Node *root) {
struct Node *curr = leftmost(root);
while (curr != NULL) {
printf("%d ", curr->data);
if (curr->rightThread)
curr = curr->right; // Follow thread
else
curr = leftmost(curr->right); // Move to leftmost in right subtree
}
}

74
 Operations of Threaded Binary Search Tree
1. createNode(key): Creates & initializes a new TBST node. Both child //1. Function to create a new node
pointers start as threads (lthread = rthread = 1), indicating no children yet. struct Node* createNode(int key) {
Procedure createNode(key) struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
Allocate memory for new node newNode->data = key;
Set [Link] = key newNode->left = NULL;
Set [Link] = NULL newNode->right = NULL;
Set [Link] = NULL newNode->lthread = 1; // Initially threads
Set [Link] = 1 // Left pointer is a thread newNode->rthread = 1;
Set [Link] = 1 // Right pointer is a thread return newNode;
Return node }
EndProcedure //2. Inorder traversal
2. inorder(root): Performs in-order traversal without recursion or a stack void inorder(struct Node* root) {
using threads. Threads efficiently guide traversal to the next inorder node. struct Node* curr = root;
Procedure inorder(root) if (curr == NULL) {
If root is NULL then printf("Tree is empty\n");
Print "Tree is empty" return;
Return }
EndIf // Go to leftmost node
Set curr = root while (curr->lthread == 0) {
While [Link] == 0 curr = curr->left;
curr = [Link] // Move to leftmost node }
EndWhile while (curr != NULL) {
While curr != NULL printf("%d -> ", curr->data);
Print [Link] // Move to inorder successor
If [Link] == 1 then if (curr->rthread)
curr = [Link] // Move to inorder successor via thread curr = curr->right;
Else else {
curr = [Link] // Move to right child curr = curr->right;
While [Link] == 0 while (curr->lthread == 0)
curr = [Link] // Then go to leftmost node curr = curr->left;
EndWhile }
EndIf }
EndWhile }
EndProcedure
75
 Operations of Threaded Binary Search Tree
3. search(root, key): Searches for a node with given key // Search a node
using standard BST logic but follows only real child
struct Node* search(struct Node* root, int key) {
pointers (where lthread or rthread == 0).
Pseudo Code: struct Node* curr = root;
Procedure search(root, key) while (curr != NULL) {
Set curr = root if (key == curr->data)
While curr != NULL return curr;
If key == [Link] if (key < curr->data) {
Return curr if (curr->lthread == 0)
ElseIf key < [Link] curr = curr->left;
If [Link] == 0 then
else
curr = [Link]
Else break;
Break } else {
EndIf if (curr->rthread == 0)
Else curr = curr->right;
If [Link] == 0 then else
curr = [Link] break;
Else }
Break
}
EndIf
EndIf return NULL;
EndWhile }
Return NULL
EndProcedure
76
 Operations of Threaded Binary Search Tree
4. insert(root, key): Inserts a new key. Thread pointers are adjusted so that: struct Node* insert(struct Node* root, int key) {
a. The new node’s left points to its inorder predecessor. struct Node* curr = root;
b. The new node’s right points to its inorder successor. Parent threads are updated
accordingly.
struct Node* parent = NULL;
Procedure insert(root, key) while (curr != NULL) {
Set curr = root if (key == curr->data) { printf("Duplicate key! Not allowed.\n");
Set parent = NULL return root;
While curr != NULL }
If key == [Link]
Print "Duplicate key! Not allowed."
parent = curr;
Return root if (key < curr->data) {
EndIf if (curr->lthread == 0) curr = curr->left;
parent = curr else break;
If key < [Link] then } else {
If [Link] == 0 then
curr = [Link]
if (curr->rthread == 0) curr = curr->right;
Else else break;
Break }
EndIf }
Else struct Node* newNode = createNode(key);
If [Link] == 0 then
curr = [Link]
if (parent == NULL) { // Tree was empty
Else root = newNode;
Break newNode->left = NULL;
EndIf newNode->right = NULL;
EndIf } else if (key < parent->data) {
EndWhile
newNode = createNode(key)
newNode->left = parent->left;
If parent == NULL then newNode->right = parent;
root = newNode // Empty tree case parent->lthread = 0;
ElseIf key < [Link] then parent->left = newNode;
[Link] = [Link] } else {
[Link] = parent
[Link] = 0
newNode->right = parent->right;
[Link] = newNode newNode->left = parent;
Else parent->rthread = 0;
[Link] = [Link] parent->right = newNode;
[Link] = parent }
[Link] = 0
[Link] = newNode
return root;
EndIf }
Return root
EndProcedure
77
 Operations of Threaded Binary Search Tree
5. inorderSuccessor(node): Finds the next node in in-order
sequence. If rthread is 1, follow the thread; otherwise, go to the
// Helper: Find inorder successor
leftmost node of the right subtree. struct Node* inorderSuccessor(struct Node*
Pseudo Code: node) {
Procedure inorderSuccessor(node) if (node->rthread)
If [Link] == 1 then
Return [Link] // Successor is threaded return node->right;
EndIf node = node->right;
node = [Link] while (node->lthread == 0)
While [Link] == 0
node = [Link]
node = node->left;
EndWhile return node;
Return node }
EndProcedure

6. inorderPredecessor(node): Finds the previous node in in- // Helper: Find inorder predecessor
order sequence. If lthread is 1, follow the thread; otherwise, go struct Node* inorderPredecessor(struct Node*
to the rightmost node of the left subtree. node) {
Pseudo Code:
Procedure inorderPredecessor(node)
if (node->lthread)
If [Link] == 1 then return node->left;
Return [Link] // Predecessor is threaded node = node->left;
EndIf while (node->rthread == 0)
node = [Link]
While [Link] == 0 node = node->right;
node = [Link] return node;
EndWhile }
Return node
EndProcedure
78
 Operations of Threaded Binary Search Tree
7. deleteNode(root, key): Handles all three deletion cases: // Step 2: If node has two children
a. Two children: Replace node’s data with inorder successor’s and If [Link] == 0 AND [Link] == 0
delete the successor. succParent = curr
b. One child: Connect parent directly to child. succ = [Link]
c. Leaf node: Remove node and restore predecessor/successor threads. While [Link] == 0
Procedure deleteNode(root, key) succParent = succ
Set parent = NULL succ = [Link]
Set curr = root EndWhile
found = false [Link] = [Link] // Replace data
// Step 1: Search the node curr = succ
While curr != NULL parent = succParent
If key == [Link] EndIf
found = true // Step 3: Node has zero or one child
Break If [Link] == 0
EndIf child = [Link]
parent = curr ElseIf [Link] == 0
If key < [Link] then child = [Link]
If [Link] == 0 Else
curr = [Link] child = NULL
Else EndIf
Break // Step 4: Adjust parent links
EndIf If parent == NULL then
Else root = child
If [Link] == 0 ElseIf curr == [Link] then
curr = [Link] If [Link] == 1 AND [Link] == 1 then
Else [Link] = 1
Break [Link] = [Link]
EndIf Else
EndIf [Link] = child
EndWhile pred = inorderPredecessor(curr)
If found == false succ = inorderSuccessor(curr)
Print "Key not found." If [Link] == 0 then [Link] = succ
Return root If [Link] == 0 then [Link] = pred
EndIf EndIf
79
 Operations of Threaded Binary Search Tree
Else // Deletion in single-threaded TBST
If [Link] == 1 AND [Link] == 1 then struct Node* deleteNode(struct Node* root, int key) {
[Link] = 1 struct Node* parent = NULL;
[Link] = [Link] struct Node* curr = root;
Else int found = 0;
[Link] = child // Step 1: Search for the node
pred = inorderPredecessor(curr) while (curr != NULL) {
succ = inorderSuccessor(curr) if (key == curr->data) {
If [Link] == 0 then [Link] = succ found = 1;
If [Link] == 0 then [Link] = pred break;
EndIf }
EndIf parent = curr;
Free curr if (key < curr->data) {
Return root if (curr->lthread == 0) curr = curr->left;
EndProcedure else break;
} else {
if (curr->rthread == 0) curr = curr->right;
else break;
}
}
if (!found) {
printf("Key not found.\n");
return root;
}
// Case 1: Node with two children
if (curr->lthread == 0 && curr->rthread == 0) {
struct Node* succParent = curr;
struct Node* succ = curr->right;
while (succ->lthread == 0) {
succParent = succ;
succ = succ->left;
}
curr->data = succ->data; // Copy successor value

80
 Operations of Threaded Binary Search Tree
// Now delete successor parent->right = child;
curr = succ; // Update inorder predecessor/successor
parent = succParent; struct Node* pred = inorderPredecessor(curr);
} struct Node* succ = inorderSuccessor(curr);
// Case 2: Node with zero or one child if (curr->lthread == 0) pred->right = succ;
struct Node* child; if (curr->rthread == 0) succ->left = pred;
if (curr->lthread == 0) child = curr->left; }
else if (curr->rthread == 0) child = curr->right; }
else child = NULL; free(curr);
if (parent == NULL) { return root;
// Deleting root node }
root = child; Summary:
} else if (curr == parent->left) {
Function Purpose
if (curr->lthread == 1 && curr->rthread == 1) {
createNode() Allocates and initializes a threaded node
parent->lthread = 1;
parent->left = curr->left; inorder() Traverses tree without recursion using
} else { threads
parent->left = child; search() Searches node by key
// Update inorder predecessor/successor insert() Inserts new node maintaining thread
struct Node* pred = inorderPredecessor(curr); links
struct Node* succ = inorderSuccessor(curr); inorderSuccessor() Finds next inorder node
if (curr->lthread == 0) pred->right = succ; inorderPredecessor() Finds previous inorder node
if (curr->rthread == 0) succ->left = pred; deleteNode() Deletes node and restores threading
Time and Space Complexity
}
} else { Operation Time Complexity Auxiliary Space
if (curr->lthread == 1 && curr->rthread == 1) { Insertion O(log n) O(1)
parent->rthread = 1; Deletion O(log n) O(1)
parent->right = curr->right; Searching O(log n) O(1)
} else { Traversal O(n) O(1)
81
 Disjoint-Set Data Structure (Union–Find)
1. Concept Overview: Two sets are said to be disjoint if they share no elements in common. The Disjoint-Set
structure helps manage such sets dynamically, efficiently answering questions like:
a. Are two elements in the same group?
b. How can we merge two groups?
c. Who represents (or leads) a given group?
2. Example Scenario – Friendship Network:
a. Imagine 10 people: a, b, c, d, e, f, g, h, i, j.
b. The following friendships are formed: a ↔ b, b ↔ d, c ↔ f, c ↔ i, j ↔ e, g ↔ j.
c. From these relations, we can identify the following friend groups: Each group represents a disjoint set. Two
individuals are considered friends (directly or indirectly) if they share the same representative.
Group Members Find(a) = Find(d)→Same Key Idea: This approach avoids repetitive searching and provides
G1 {a, b, d} representative→Friends almost constant-time queries.
G2 {c, f, i} Find(c) ≠ Find(g)→Different a. Initially: Every element is its own parent (a singleton set).
G3 {e, g, j} representatives→Not friends b. After relations: Union operations merge sets as friendships form.
G4 {h} c. Find operation: Helps identify if two members belong to same set.

3. The Disjoint-Set Data Structure — also known as Union–Find or Merge–Find Set — is one of the most elegant and
efficient data structures in computer science. It maintains a collection of disjoint (non-overlapping) sets and
supports three key operations:
a. MakeSet(x): Create a new set containing element x.
b. Find(x): Identify the representative (or root) of the set containing x.
c. Union(x, y): Merge the sets containing x and y into a single set.
4. This structure is essential for efficiently solving problems involving grouping, connectivity, and partitioning—such
as network connection analysis, clustering, and Kruskal’s Minimum Spanning Tree (MST) algorithm.
5. With optimizations like Union by Rank and Path Compression, these operations run in near constant time, making
Union–Find one of the most efficient tools in algorithm design.
82
 Evolution & History of Disjoint-Set Forests
1. The Disjoint-Set Forest has evolved through decades of theoretical refinement and innovation. Below is a timeline of its
most significant milestones:
Year Researchers Contribution / Breakthrough
1964 Galler & Fischer Introduced the disjoint-set forest to efficiently manage dynamic sets using parent pointers.
1973 Hopcroft & First established the time complexity bound of O(log* n) — where log* is the extremely slow-growing
Ullman iterated logarithm.
1975 Robert Tarjan Major breakthrough: proved that Union–Find with union by rank and path compression runs in
O(mα(n)) time, where α(n) is the inverse Ackermann function — practically constant for all realistic n.
1979 Robert Tarjan Proved O(mα(n)) bound is both an upper &d lower bound for pointer-based algorithms.
1989 Fredman & Saks Proved that any Union–Find must take at least Ω(α(n)) time per operation — cementing Tarjan’s result
as optimal.
1991 Galil & Italiano Published a comprehensive survey summarizing developments in disjoint-set algorithms and
applications.
1994 Anderson & Proposed a parallel, non-blocking Union–Find, enabling efficient concurrent operations in
Woll multiprocessor systems.
2007 Conchon & Introduced a semi-persistent and formally verified version using the Coq proof assistant — ensuring
Filliâtre both correctness and efficiency.
— Gabow & Tarjan If union operations follow a known tree structure, performance can reach linear time (O(n)).

2. In summary: From its 1964 foundation to Tarjan’s theoretical breakthroughs and beyond, the disjoint-set structure has
become a cornerstone of modern algorithm design — combining simplicity, elegance, and near-optimal efficiency.
3. Why It Matters: The Disjoint Set structure is extremely efficient — with optimizations like path compression and union by
rank/size, operations can be performed in near constant time. It is an essential tool for solving problems that involve:
a. Grouping or clustering
b. Dynamic connectivity (e.g., networks, social relations)
c. Detecting cycles in graphs
d. Minimum Spanning Trees (Kruskal’s Algorithm)
83
 Disjoint Set Representation & Operations
1. Representation: The Disjoint-Set Data Structure (also known as Union–Find) is most commonly
implemented as a forest of trees, where each node maintains a pointer to its parent. This
representation is often called the Galler–Fischer tree structure.
a. Each node stores:
i. A parent pointer (showing which node it belongs to),
ii. An auxiliary value — either rank or size (but not both).
b. In this structure:
i. Root nodes represent the set identifiers.
ii. A root node can be recognized because its parent pointer either points to itself or
holds a special sentinel value.
iii. Each tree in the forest corresponds to one set; all members of that set are connected
under the same root.
iv. Two nodes belong to the same set if and only if their roots are identical.
c. Storage: Nodes can be stored conveniently in an array, where each index represents an
element, and its value represents the parent’s index. This storage requires Θ(n log n) bits,
though practically it’s linear in n for fixed-size elements.
2. Core Operations: Disjoint-set structures support three key operations:
a. MakeSet(x) → Create a new set containing element x.
b. Find(x) → Determine which set (tree) element x belongs to.
c. Union(x, y) → Merge the sets containing elements x and y.

84
 Disjoint Set Representation & Operations
1. createUnionFind(n): Initializes the Union-Find // 1. Create and initialize Union-Find structure
structure for n elements. UnionFind* createUnionFind(int n) {
Pseudo Code: int i;
function createUnionFind(n) UnionFind *uf;
for i ← 0 to n-1 do uf = (UnionFind *)malloc(sizeof(UnionFind));
parent[i] ← i // each node is its own parent uf->n = n;
rank[i] ← 0 // rank = 0 for all uf->parent = (int *)malloc(n * sizeof(int));
size[i] ← 1 // each set has size 1 uf->rank = (int *)malloc(n * sizeof(int));
end for uf->size = (int *)malloc(n * sizeof(int));
end function for (i = 0; i < n; i++) {
Working: Creates three arrays — parent, rank, and size. uf->parent[i] = i;
Each element starts as a separate set where parent[i]=i. uf->rank[i] = 0;
Used once at program start. uf->size[i] = 1;
}
2. makeSet(x): Creates an independent singleton set for return uf;
element x. }
Pseudo Code:
function makeSet(x) //2. MakeSet(x): Create a new singleton set
parent[x] ← x void makeSet(UnionFind *uf, int x) {
rank[x] ← 0 if (x >= 0 && x < uf->n) {
size[x] ← 1 uf->parent[x] = x;
end function uf->rank[x] = 0;
Working: Used when initializing or resetting a particular uf->size[x] = 1;
element. Essentially ensures x is its own parent (new }
independent set). }
85
 Disjoint Set Representation & Operations
2. Find Operation: This operation locates root (representative)
Example:
of set containing x by following parent pointers.
Suppose we have a set a. Find(c) is called.
 Without optimization, repeated Find operations may
represented as a tree: b. Without path compression: c →
require traversing a long chain of parent pointers, which
can be slow if the trees are deep. a b→a
 Path Compression is an optimization that flattens tree / c. With path compression:
during a Find operation. Flattening the tree reduces the b [Link] and [Link] are
height, improving performance while maintaining correct / updated to a
set representatives. c
a. When Find(x) is called:
a. Traverse from x up to the root of the tree.
Key Points:
b. Make the root the direct parent of x and all a. Path compression only occurs during Find.
intermediate nodes along the path. b. It reduces the amortized time complexity of
c. This ensures that future Find operations for any operations to near-constant time.
node along this path reach root in constant time. c. Combined with Union by Rank/Size, it ensures
b. How Path Compression Works: optimal performance for a sequence of MakeSet,
i. Traverse to Root: Start at node x and follow parent
Find, and Union operations.
pointers until reaching the root of the tree.
ii. Update Parent Pointers: Once the root is found,
update the parent pointer of every node along the
path from x to the root so that they point directly to
the root.
c. Result:
a. The tree becomes flatter.
b. Subsequent Find operations on any node along the
path reach the root in constant time.
c. Path compression does not change representative of
the set — it only optimizes the structure for faster
access.
86
Disjoint Set Representation & Operations
3. find(x): Finds and returns the representative (root) of the set containing x.
function find(x)
root ← x
while parent[root] ≠ root do
root ← parent[root]
end while
while parent[x] ≠ root do
temp ← parent[x]
parent[x] ← root
x ← temp
end while
return root
end function
Working:
a. Follows parent pointers until the root is found.
b. Then flattens tree (path compression) so all nodes directly point to the root.
c. This drastically reduces future lookup times.

// Find(x): Representative with Path Compression

int find(UnionFind *uf, int x) {
int root=x, temp;
while (uf->parent[root] != root) root = uf->parent[root];
while (uf->parent[x] != root) {
temp = uf->parent[x];
uf->parent[x] = root;
x = temp;
}
return root;
}
87
 Disjoint Set Representation & Operations
4. Union Operation (Merging Disjoint Sets): The Union(x, y) operation is
used to merge two distinct disjoint sets into a single set. Steps for Union:
a. Find the root (representative) of both x and y using the Find()
operation.
b. If both elements already share the same root, they are in the same set,
so no action is needed.
c. Otherwise, attach one root under the other to merge the sets.
Caution: Repeated unions without any optimization can create tall trees,
which increases the time required for Find() operations. To prevent this,
Union by Rank or Union by Size is used to maintain balanced trees.

4(a) Union by Rank (Minimizing Tree Height): Rank of a node approximates

the height of the tree representing a set. We maintain an additional array,
rank[], parallel to the parent array.
a. If i is the representative of a set, then rank[i] is its rank.
b. Without path compression, rank equals the tree height; with path
compression, rank may exceed the actual height.
c. Goal: When uniting two sets (trees), minimize the height of the resulting
tree to keep Find() operations efficient.
Rules for Union by Rank:
a. Let left and right be the roots of the two trees.
b. If rank[left] < rank[right], attach left under right (the rank of right does
not change).
c. If rank[right] < rank[left], attach right under left.
d. If rank[left] == rank[right], attach either one under the other, and
increment the rank of the new root by 1.
88
 Disjoint Set Representation & Operations
4(a) unionByRank(x, y): Merges the two sets containing x // Union by Rank
and y using rank heuristic (to keep tree shallow). void unionByRank(UnionFind *uf, int x, int y) {
Pseudo Code: int xRoot, yRoot;
function unionByRank(x, y)
xRoot ← find(x) xRoot = find(uf, x);
yRoot ← find(y) yRoot = find(uf, y);
if xRoot = yRoot then return
if rank[xRoot] < rank[yRoot] then if (xRoot == yRoot)
parent[xRoot] ← yRoot return;
else if rank[yRoot] < rank[xRoot] then
parent[yRoot] ← xRoot if (uf->rank[xRoot] < uf->rank[yRoot]) {
else uf->parent[xRoot] = yRoot;
parent[yRoot] ← xRoot } else if (uf->rank[yRoot] < uf->rank[xRoot]) {
rank[xRoot] ← rank[xRoot] + 1 uf->parent[yRoot] = xRoot;
end function } else {
uf->parent[yRoot] = xRoot;
Working: uf->rank[xRoot]++;
a. Always attaches smaller-rank tree under larger-rank }
tree. }
b. If both have same rank, one becomes root and its
rank increases by 1.
c. Prevents unnecessary depth growth.

89
 Disjoint Set Representation & Operations
4(b) Union by Size (Attaching Smaller Trees): Instead of Pseudo Code (Union by Size):
height, we can use the size of a tree (number of nodes) to function unionBySize(x, y)
decide which tree becomes the child. An additional array, xRoot ← find(x)
size[], is maintained: yRoot ← find(y)
a. If i is the representative of a set, size[i] is the number if xRoot = yRoot then return
of elements in the set. if size[xRoot] < size[yRoot] then
b. Goal: Always attach the smaller tree under the larger parent[xRoot] ← yRoot
tree to keep trees balanced and shallow. size[yRoot] ← size[yRoot] + size[xRoot]
else
Rules for Union by Size: parent[yRoot] ← xRoot
a. Let left and right be the roots of the two trees. size[xRoot] ← size[xRoot] + size[yRoot]
b. If size[left] < size[right], attach left under right and end function
update size[right] += size[left]. // Function: Union by Size
c. If size[right] < size[left], attach right under left and void unionBySize(UnionFind *uf, int x, int y) {
update size[left] += size[right]. int xRoot, yRoot, xSize, ySize;
d. If sizes are equal, either tree can become the child; xRoot = find(uf, x);
update the size accordingly. yRoot = find(uf, y);
if (xRoot == yRoot) return;
Key Notes: xSize = uf->size[xRoot];
Strategy Decision How to Merge Extra Info ySize = uf->size[yRoot];
Factor if (xSize < ySize) {
Union by Height Attach smaller- Increment rank if uf->parent[xRoot] = yRoot;
uf->size[yRoot] += xSize;
Rank (rank) rank tree under equal
} else {
larger-rank tree
uf->parent[yRoot] = xRoot;
Union by Number of Attach smaller- Update size after
uf->size[xRoot] += ySize;
Size nodes size tree under merge
}
larger-size tree
}
90
 Disjoint Set Representation & Operations
5. displaySets(): Displays the representative (root) of // Display all sets
each element in the disjoint set system. void displaySets(UnionFind *uf) {
Pseudo Code: int i;
function displaySets() printf("\nCurrent Set Representatives:\n");
for i ← 0 to n-1 do for (i = 0; i < uf->n; i++) {
print "Element", i, "→ Root", find(i) printf("Element %d ? Root %d\n", i, find(uf, i));
end for }
end function }
Working: // Free allocated memory
a. For each element, it prints the representative found void freeUnionFind(UnionFind *uf) {
by find(i). free(uf->parent);
free(uf->rank);
b. Useful for visualizing how elements get grouped after
free(uf->size);
multiple union operations.
free(uf);
}
6. freeUnionFind(): Deallocates all dynamically allocated Summary Table
memory. Function Main Task Optimization
Pseudo Code: createUnionFind Initialize parent, rank, size —
function freeUnionFind() arrays
free(parent) makeSet Create a singleton set —
free(rank) find Locate representative of Path
free(size) set Compression
end function unionByRank Merge two sets by rank Union by Rank
Working: Ensures that memory used by arrays is released unionBySize Merge two sets by size Union by Size
before program termination. displaySets Print representative of Uses find()
each element
freeUnionFind Free memory —
91
 PROCESS MAKE-IN-INDIA
RE-ENGINEERING

CAPACITY BUILDING
DIGITAL LOCKER

Knowledge gives discipline, from discipline

comes worthiness, from worthiness one gets
wealth, from wealth (one does) good deeds,
from that (comes) joy.

e-LEARNING SKILL INDIA

AURANGABAD