Chapter 1

Tree

➔ Introduction

● A tree data structure is defined as a collection of objects or entities known as

nodes that are linked together to represent or simulate hierarchy.

● A tree data structure is a non-linear data structure because it does not store in a
sequential manner. It is a hierarchical structure as elements in a Tree are
arranged in multiple levels.

● In the Tree data structure, the topmost node is known as a root node. Each node
contains some data, and data can be of any type. In the above tree structure, the
node contains the name of the employee, so the type of data would be a string.

● Each node contains some data and the link or reference of other nodes that can be
called children.

➔Basic Concepts and Terminology

● Node: In a tree, every individual element is called a node. It stores actual data of that
particular element and links to the next element in the hierarchical structure.
● Root: The root node is the topmost node in the tree hierarchy. In other words, the root
node is the one that doesn't have any parent. In the above structure, node A is the root
 node of the tree. If a node is directly linked to some other node, it would be called a
parent-child relationship.

● Child node: If the node is a descendant of any node, then the node is known as a child
node.

● Parent: If the node contains any sub-node, then that node is said to be the parent of
that sub-node.

● Sibling: The nodes that have the same parent are known as siblings.

● Leaf Node: The node of the tree, which doesn't have any child node, is called a leaf
node. A leaf node is the bottom-most node of the tree. There can be any number of leaf
nodes present in a general tree. Leaf nodes can also be called external nodes.

● Internal nodes: A node which has at least one child node known as an internal node

● Ancestor node: An ancestor of a node is any predecessor node on a path from the root
to that node. The root node doesn't have any ancestors. In the tree shown in the above
image, nodes A, B, D and H are the ancestors of node L.

● Descendant: The immediate successor of the given node is known as a descendant of

a node. In the above figure, L is the descendant of node H.

● Edge: In tree data structure, the connecting link between any two nodes is called edge.
In a tree with ‘n’ number of nodes there will be a maximum of ‘n-1’ number of edges.

● Path: The sequence of nodes and edges from one node to another node is called a
path between those two nodes. Length of a path is the total number of nodes in that
path.

● Null Tree: A tree with no nodes is called a null tree.

● Degree of a Tree: Degree of a node is the total number of children of that node. The
degree of node A is 2, degree of node F is 1 and degree of P id 0.

● Degree of a Tree: The highest degree of a node among all the nodes in a tree is called
the degree of tree. In the above figure the degree of the tree is 2.

● Depth or Level of a Node: In tree data structure, the root node is said to be at Level 1
and children of the root node are at Level 1 and the children of the nodes which are at
Level 1 will be at Level 2 and so on.. In other words, in a tree each step from top to
bottom is called a Level and the Level Count starts with ‘1’’ and is incremented by One
(1) at each Level(step).
● In-degree: The in-degree of a node is the total number of edges coming to that node.

● Out-degree: The out-degree of a node is the toil number of edges going outside from
 the node.

● Sub Tree: In tree data structure, each child from a node forms a subtree recursively.
Every child node will form a sub tree on its parent node.

● Height: In tree data structure, the total number of edges from leaf node to a particular
node in the longest path is called the height of that node. In a tree, the height of the root
node is said to be the height of the tree. In a tree, the height of all leaf nodes is ‘0’.

● Depth: Total number of edges from root node to a particular node is called as depth of
that node. In a tree, the depth of the root node is ‘0’. The tree in the above figure has
depth 4.

➔Binary Tree and Types of Binary Tree

● General tree: The general tree is one of the types of tree data structure. In the
general tree, a node can have either 0 or maximum n number of nodes. There is
no restriction imposed on the degree of the node (the number of nodes that a
node can contain). The topmost node in a general tree is known as a root node.
The children of the parent node are known as subtrees.

There can be n number of subtrees in a general tree. In the general tree, the
subtrees are unordered as the nodes in the subtree cannot be ordered. Every
non-empty tree has a downward edge, and these edges are connected to the
nodes known as child nodes. The root node is labeled with level 0. The nodes
that have the same parent are known as siblings.
● Binary tree: Here, the binary name itself suggests two numbers, i.e., 0 and 1. In a
binary tree, each node in a tree can have utmost two child nodes. Here, utmost
means whether the node has 0 nodes, 1 node or 2 nodes.
 ● Binary Search tree: Binary search tree is a non-linear data structure in which one
node is connected to n number of nodes. It is a node-based data structure. A
node can be represented in a binary search tree with three fields, i.e., data part,
left-child, and right-child. A node can be connected to the utmost two child nodes
in a binary search tree, so the node contains two pointers (left child and right child
pointer).
Every node in the left subtree must contain a value less than the value of the root
node, and the value of each node in the right subtree must be bigger than the
value of the root node.

In the above figure, we can observe that the root node is 40, and all the nodes of
the left subtree are smaller than the root node, and all the nodes of the right subtree are
greater than the root node.
Similarly, we can see the left child of the root node is greater than its left child and
smaller than its right child. So, it also satisfies the property of binary search tree.
Therefore, we can say that the tree in the above image is a binary search tree.
● Skewed Binary Tree: A tree in which every node has either only the left subtree
or right subtree is called a skewed binary tree. There are two types of skewed
binary trees:
○ Left Skewed Binary Tree: A binary tree is said to be left skewed if all the
nodes of the tree contain either left child only or no child at all. One can
also say it is a left-side-dominated tree.

○ Right Skewed Binary Tree: A binary tree is said to be right-skewed if all

the nodes of the tree contain either the right child only or no child at all.
One can also say it is a right-side-dominated tree.

● Strictly Binary Tree: A strictly binary tree is a binary tree where all non-leaf nodes
have two branches. When every non-leaf node in a binary tree is filled with left
and right subtrees, the tree is called a strictly binary tree.
 ● Full Binary Tree: If each node of a
binary tree has either two children or no
child at all, it is said to be a full binary
tree. A full binary tree is defined as a
binary tree in which all nodes have
either zero or two child nodes. A full binary tree is a binary tree in which all the
leaves are on the same level and every non-leaf node has two children.

● Complete Binary Tree: A complete binary tree is a binary tree in which all the
levels are completely filled except possibly the last one, which is filled from the
left.

● Expression Tree: The expression tree is a binary tree in which each internal
node corresponds to the operator and each leaf node corresponds to the
operand.
● Heap: A heap is a special tree-based data structure in which the tree is a
complete binary tree. There are two types of heaps:-
○ Max-Heap: In a max-heap the key present at the root node must be
greatest among the keys present at all of its children. The same property
must be recursively true for all sub-trees in that binary tree.

○ Min-Heap:
In a min-heap
the key
present at the
root node must be minimum among the keys present at all of its children.
The same property must be recursively true for all sub-trees in that binary
tree.
➔ Representation of Tree (Static and Dynamic):-
● Static Representation of Tree: In static representation, a tree is represented
sequentially in the memory by using a single one-dimensional array. Here, a
block of memory for an array is to be allocated before going to store the actual
tree in it. Hence, nodes of the tree are stored level by level, starting from the zero
level where the root is present.
A complete binary tree of height h has (2h+1- 1) nodes in it. The nodes can
be stored in a one-dimensional array. An array of size (2h+1- 1) or (2d- 1) (where d
= no. of levels) is required.
Following rules can be used to decide the location of any ith node of a
tree. For any node with index i, where i, 1 ≤ i ≤ n
i) Parent (i) = [i/2] if i ≠ 1
If i = 1 then it is root which has no parent
ii) Lchild (i) = 2 * i, if 2i ≤ n
If 2i > n, then i has no left child
iii) Rchild (i) = (2 * i) + 1, if 2i+1 ≤ n
If (2i + 1) > n, then i has no right child

● Example:- For the array representation of binary tree, we will form an array of size
2*n+1 size where n is the number of nodes in the binary tree. Now we will move
step by step for the array representation of the binary tree.
1. First, suppose we have a binary tree with seven nodes
2. Now, for the array representation of a binary tree, we have to give
numbering to the corresponding nodes. The standard form of numbering
the nodes is to start from the root node and move from left to right at every
level. After numbering the tree and nodes will look like this:

3. Now as we have
numbered from zero you can simply place the corresponding number in
the matching index of an array then the array will look like this:

4. That is
the array representation of a binary tree but this is the easy case as every
node has two children so what about other cases? We will discuss other
cases below.
5. In these cases, we will discuss the scenarios for the array representation of
binary trees where the lead node is not always on the last level.

6. So consider the binary tree given below:

 7. While giving a number you are stuck with the cases where you encounter a
leaf node so just make the child node of the leaf nodes as NULL then the
tree will look like this:

8. Now just
number the nodes as done above for the array representation of binary tree after that
the tree will look like this:
 9. Now we have the number on each node we can easily use the tree for
array representation of binary tree and the array will look like this:

● Dynamic Representation of Tree (USing Linked List) :- For the linked list
representation, we will use the doubly linked list, which has two pointers so that
we can point to the left and right children of a binary tree node. NULL is given to
the pointer as
the address
when no child
is connected.

● The Linked list

representation of the above binary tree is :
➔ Binary Search Tree (BST) Implementation and Operations A binary
search tree follows some order to arrange the elements. In a Binary search tree, the value
of the left node must be smaller than the parent node, and the value of the right node must
be greater than the parent node. This rule is applied recursively to the left and right
subtrees of the root.

Let's understand the concept of Binary search tree with an example.

In the above figure, we can observe that the root node is 40, and all the nodes of the left
 subtree are smaller than the root node, and all the nodes of the right subtree are greater
than the root node.

Similarly, we can see the left child of the root node is greater than its left child and
smaller than its right child. So, it also satisfies the property of binary search trees.
Therefore, we can say that the tree in the above image is a binary search tree.

➔ Creating Binary Search Tree

● The function create() creates an empty binary search tree. This initializes th root
pointer to NULL.
Struct tree *root = NULL;
● Algorithm:-
○ Step 1:- root = NULL
○ Step 2:- read key and create a new node to store key value
○ Step 3:- if root is null then new node is root
○ Step 4:- t=root, flag=false
○ Step 5:- while (t ≠ null) and (flag = false) do
case 1: if key < t -> data
Attach new node to t -> left
case 2: if key > t -> data
Attach new node to t -> right
case 3: if t -> day = key
then print “key already exists”
○ Step 6:- Stop
● C Function for Creating BST
struct node *create(struct node *root,int value)
{
if(root==NULL)
{
root=(struct node *)malloc (sizeof(struct node));
root->lchild=root->rchild=NULL;
root->data=value;
return root;
}
else
{
if(value<root->data)
{
printf("%d inserted left child of %d\n",value,root->data);
root->lchild=create(root->lchild,value);
}
 else if(value>root->data)
{
printf("%d inserted right child of %d\n",value,root->data);
root->rchild=create(root->rchild,value);
}
else
printf("Duplicate");
return root;
}
}

● Example:-
Let's see the creation of binary search tree using an example.

Suppose the data elements are - 45, 15, 79, 90, 10, 55, 12, 20, 50

○ First, we have to insert 45 into the tree as the root of the tree. ○ Then, read
the next element; if it is smaller than the root node, insert it as the root of the
left subtree, and move to the next element.
○ Otherwise, if the element is larger than the root node, then insert it as the
root of the right subtree.

Now, let's see the process of creating the Binary search tree using the given data
element. The process of creating the BST is shown below -
Step 1: Insert 45.

Step 2 : Insert 15.

As 15 is smaller than 45, so insert it as the root node of the left subtree.
Step 3 : Insert 79.

As 79 is greater than 45, so insert it as the root node of the right

subtree.

Step 4 : Insert 90.

90 is greater than 45 and 79, so it will be inserted as the right subtree of 79.
Step 5 : Insert 10.

10 is smaller than 45 and 15, so it will be inserted as a left subtree of

15.

Step 6 : Insert 55.

55 is larger than 45 and smaller than 79, so it will be inserted as the left subtree
of 79.
Step 7 : Insert 12.

12 is smaller than 45 and 15 but greater than 10, so it will be inserted as the right
subtree of 10.

Step 8 : Insert 20.

20 is smaller than 45 but greater than 15, so it will be inserted as the right
subtree of 15.
 Step 9 : Insert 50.

50 is greater than 45 but smaller than 79 and 55. So, it will be inserted as a left
subtree of 55.

Now, the creation of a binary search tree is completed.

➔ Searching in a BST
● Searching means to find or locate a specific element or node in a data structure. In
Binary search tree, searching a node is easy because elements in BST are
stored in a specific order. The steps of searching a node in Binary Search tree
are listed as follows -
 1. First, compare the element to be searched with the root element of the
tree.
2. If the root is matched with the target element, then return the node's
location.
3. If it is not matched, then check whether the item is less than the root
element, if it is smaller than the root element, then move to the left
subtree.
4. If it is larger than the root element, then move to the right subtree.
5. Repeat the above procedure recursively until the match is found.
6. If the element is not found or not present in the tree, then return NULL.

● Algorithm:- Search - BST (Key)

○ Step 1 : Initialize t = root, flag = false

○ Step 2 : while (t ≠ null) and (flag = false) do
case 1: t -> data = key
flag = true
case 2: key < t -> data
t = t -> left
case 3: key > t -> data
t = t -> right
end case
end while
○ Step 3 : if (flag = true) then
display “Key is found at node”,t
else
display “Key does not exist.”
○ Step 4 : Stop

● Non Recursive C Function for search key:

BSTNODE *search(BSTNODE *root, int key)

{
BSTNODE *temp=root;
if(temp == NULL) || (temp -> data == key)
return temp;
else
{
while(temp != NULL) && (temp -> data != NULL)
{
if(key < temp -> data)
temp = temp -> left;
else
temp = temp -> right
 }
return(temp);
}
}

● Recursive C Function for search key:

BSTNODE *search(BSTNODE *root, int key)

{
BSTNODE *temp=root;
if(temp == NULL) || (temp -> data == key)
return temp;
else
{
if(key < temp -> data)
search(temp -> left, key);
else
search(temp -> right, key);
}
}

● Example:
Let's understand the searching in binary trees using an example. We are taking
the binary search tree formed above. Suppose we have to find node 20 from the
below tree.

Step 1:

Step 2:
 Step 3:

➔ Inserting a Node into BST

● A new key in BST is always inserted at the leaf. To insert an element in BST,
we have to start searching from the root node; if the node to be inserted is
less than the root node, then search for an empty location in the left subtree.
Else, search for the empty location in the right subtree and insert the data.
Inserting in BST is similar to searching, as we always have to maintain the
rule that the left subtree is smaller than the root, and the right subtree is larger
than the root.

● Algorithm:- Insert_BST(Key)

○ Step 1: t = root, flag = false

○ Step 2: while (t ≠ null) and (flag = false) do
case 1: key < t -> data
t1 = t;
t = t -> left
case 2: key > t -> data
t1 = t;
t = t -> right
 case 3: t -> data = key
flag = true
display “item already exist”
break
end case
end while
○ Step 3: if (t =null) then
new = getNode(node)
new -> data = key
new -> left = null
new -> right = null
if(t1 -> data < key) then
t1 -> right = new
else
t1 -> left = new
endif
○ Step 4: Stop

● Recursive C function for inserting node into BST:

BST *Insert_BST(BSTNODE *root, int n)
{
if(root == NULL)
{
root = (BSTNODE *)malloc(sizeof(BSTNODE));
root -> data = n;
root -> left = root -> right = NULL;
}
else
if(n < root -> data)
root -> left = Insert_BST(root -> left, n);
else
root -> right = Insert_BST(root -> right, n);
return(root);
}

● Non - Recursive C function for inserting node into BST:

BST *Insert_BST(BSTNODE *root, int n)
{
BSTNODE *temp, *newnode;
newnode = (BSTNODE*) malloc
(sizeof(BSTNODE)); newnode -> data = n;
newnode -> left = newnode -> right = NULL;
if(root == NULL)
root = newnode;
else
{
 temp = root;
while(temp)
{
if (n < temp -> data)
{
if(temp -> left == NULL)
{
temp -> left = newnode;
break;
}
else
temp -> temp -> left;
else if(n > temp -> data)
{
if(temp -> right == NULL)
{
temp -> right = newnode;
break;
}
else
temp = temp -> right;
}
}
return root;
}
}
}

● Example:
Let's see the process of inserting a node into BST using an example.
➔ Deleting Node from BST
● In a binary search tree, we must delete a node from the tree by keeping in mind
that the property of BST is not violated. To delete a node from BST, there are
three possible situations occur -
○ The node to be deleted is the leaf node, or,
○ The node to be deleted has only one child, and,
○ The node to be deleted has two children

● When the node to be deleted is the leaf node

It is the simplest case to delete a node in BST. Here, we have to replace the leaf
node with NULL and simply free the allocated space.

We can see the process to delete a leaf node from BST in the below image. In
the image below, suppose we have to delete node 90, as the node to be deleted
is a leaf node, so it will be replaced with NULL, and the allocated space will be
free.

● When the node to be deleted has only one child

In this case, we have to replace the target node with its child, and then delete the
child node. It means that after replacing the target node with its child node, the
child node will now contain the value to be deleted. So, we simply have to replace
the child node with NULL and free up the allocated space.

We can see the process of deleting a node with one child from BST in the below
image. In the below image, suppose we have to delete the node 79, as the node
to be deleted has only one child, so it will be replaced with its child 55.

So, the replaced node 79 will now be a leaf node that can be easily deleted.

● When the node to be deleted has two children

This case of deleting a node in BST is a bit complex among other two cases. In
such a case, the steps to be followed are listed as follows -

○ First, find the inorder successor of the node to be deleted.

○ After that, replace that node with the inorder successor until the target
node is placed at the leaf of tree.
○ And at last, replace the node with NULL and free up the allocated space.

The inorder successor is required when the right child of the node is not empty.
We can obtain the inorder successor by finding the minimum element in the right
child of the node.

We can see the process of deleting a node with two children from BST in the
below image. In the below image, suppose we have to delete node 45 that is the
root node, as the node to be deleted has two children, so it will be replaced with
its inorder successor. Now, node 45 will be at the leaf of the tree so that it can be
deleted easily.
➔ Compute the Height of a Binary Tree
● Recursive function which returns the height of linked binary tree:
int tree_height(struct node *root)
{
if (root == NULL)
return 0;
else
return (1 + max(tree_height(root -> left), tree_height(root ->
right)));
}

● Function max()

int max(int x, int y)

{
if(x > y)
return x;
else
return y;
}

➔ Tree Traversals (Preorder, Inorder and Postorder)

● The term 'tree traversal' means traversing or visiting each node of a tree. There is
a single way to traverse the linear data structure such as linked list, queue, and
stack. Whereas, there are multiple ways to traverse a tree that are listed as
follows -
○ Preorder traversal
○ Inorder traversal
○ Postorder traversal
● Preorder Traversal (DLR)
This technique follows the 'root - left - right' policy. It means that, first root node is
visited after that the left subtree is traversed recursively, and finally, the right
subtree is recursively traversed. As the root node is traversed before (or pre) the
left and right subtree, it is called preorder traversal.

So, in a preorder traversal, each node is visited before both of its subtrees.

The applications of preorder traversal include -

○ It is used to create a copy of the tree.
○ It can also be used to get the prefix expression of an expression tree.

Algorithm

Until all nodes of the tree are not visited

Step 1 - Visit the root node

Step 2 - Traverse the left subtree recursively.
Step 3 - Traverse the right subtree recursively.

Example

Let's see an example of the preorder traversal technique.

Now, start applying the preorder traversal on the above tree. First, we traverse
the root node A; after that, move to its left subtree B, which will also be traversed
in preorder.
So, for left subtree B, first, the root node B is traversed itself; after that, its left
subtree D is traversed. Since node D does not have any children, move to right
subtree E. As node E also does not have any children, the traversal of the left
subtree of root node A is completed.
 Now, move towards the right subtree of root node A that is C. So, for right
subtree C, first the root node C has traversed itself; after that, its left subtree F is
traversed. Since node F does not have any children, move to the right subtree G.
As node G also does not have any children, traversal of the right subtree of root
node A is completed.

Therefore, all the nodes of the tree are traversed. So, the output of the preorder
traversal of the above tree is -

A→B→D→E→C→F→G

● Postorder Traversal (LRD):

This technique follows the 'left - right - root' policy. It means that the first left
subtree of the root node is traversed, after that recursively traverses the right
subtree, and finally, the root node is traversed. As the root node is traversed after
(or post) the left and right subtree, it is called postorder traversal.

So, in a postorder traversal, each node is visited after both of its subtrees.

The applications of postorder traversal include -

○ It is used to delete the tree.

○ It can also be used to get the postfix expression of an expression tree.

Algorithm
Until all nodes of the tree are not visited

Step 1 - Traverse the left subtree recursively.

Step 2 - Traverse the right subtree recursively.
Step 3 - Visit the root node.

Example

Let's see an example of the postorder traversal technique.

 Now, start applying the postorder traversal on the above tree. First, we traverse
the left subtree B that will be traversed in postorder. After that, we will traverse
the right subtree C in postorder. And finally, the root node of the above tree, i.e.,
A, is traversed.

So, for left subtree B, first, its left subtree D is traversed. Since node D does not
have any children, traverse the right subtree E. As node E also does not have
any children, move to the root node B. After traversing node B, the traversal of
the left subtree of root node A is completed.

Now, move towards the right subtree of root node A that is C. So, for right subtree
C, first its left subtree F is traversed. Since node F does not have any children,
traverse the right subtree G. As node G also does not have any children,
therefore, finally, the root node of the right subtree, i.e., C, is traversed. The
traversal of the right subtree of root node A is completed.

At last, traverse the root node of a given tree, i.e., A. After traversing the root
node, the postorder traversal of the given tree is completed.

Therefore, all the nodes of the tree are traversed. So, the output of the postorder
traversal of the above tree is -

D→E→B→F→G→C→A

● Inorder Traversal (LDR):

This technique follows the 'left root right' policy. It means that the first left subtree
is visited after that root node is traversed, and finally, the right subtree is
traversed. As the root node is traversed between the left and right subtree, it is
named inorder traversal.
So, in the inorder traversal, each node is visited in between its subtrees.

The applications of Inorder traversal includes -

○ It is used to get the BST nodes in increasing order.

○ It can also be used to get the prefix expression of an expression tree.

Algorithm:-
Until all nodes of the tree are not visited

Step 1 - Traverse the left subtree recursively.

Step 2 - Visit the root node.
Step 3 - Traverse the right subtree recursively.

Example:-

Let's see an example of the Inorder traversal technique.

Now, start applying the inorder traversal on the above tree. First, we traverse the
left subtree B that will be traversed in inorder. After that, we will traverse the root
node A. And finally, the right subtree C is traversed in inorder.
So, for left subtree B, first, its left subtree D is traversed. Since node D does not
have any children, so after traversing it, node B will be traversed, and at last, the
right subtree of node B, that is E, is traversed. Node E also does not have any
children; therefore, the traversal of the left subtree of root node A is completed.

After that, traverse the root node of a given tree, i.e., A.

 At last, move towards the right subtree of root node A that is C. So, for right
subtree C; first, its left subtree F is traversed. Since node F does not have any
children, node C will be traversed, and at last, a right subtree of node C, that is,
G, is traversed. Node G also does not have any children; therefore, the traversal
of the right subtree of root node A is completed.

As all the nodes of the tree are traversed, the inorder traversal of the given tree is
completed. The output of the inorder traversal of the above tree is -

D→B→E→A→F→C→G

➔ Count Total Nodes of a Binary Tree:-

int count(struct node *temp)
{
if(temp!=NULL)
{
cnt++;
count(temp->lchild);
count(temp->rchild);
}
return cnt;
}

➔ Count Leaf Nodes of Binary Tree:-

int countleaf(struct node *temp)
{
if(temp!=NULL)
{
if(temp->lchild==NULL && temp->rchild==NULL)
leafcnt++;
countleaf(temp->lchild);
countleaf(temp->rchild);
}
return leafcnt;
}

➔ Count Non-Leaf Nodes of a Binary Tree:-

int countnleaf(struct node *temp)
 {
if(temp!=NULL)
{
if(temp->lchild!=NULL || temp->rchild!=NULL)
nleafcnt++;
countnleaf(temp->lchild);
countnleaf(temp->rchild);
}
return nleafcnt;
}

➔ Heap Sort with its Implementation

● A heap is a complete binary tree, and the binary tree is a tree in which the node
can have the utmost two children. A complete binary tree is a binary tree in which
all the levels except the last level, i.e., leaf node, should be completely filled, and
all the nodes should be left-justified. There are two types of heap:-

○ Max Heap: In this type of heap, the value of parent node will always be
greater than or equal to the value of child node across the tree and the
node with highest value will be the root node of the tree.

○ Min Heap: In this type of heap, the value of parent node will always be less
than or equal to the value of child node across the tree and the node with
lowest value will be the root node of the tree.
● Heapsort is a popular and efficient sorting algorithm. The concept of heap sort is to
eliminate the elements one by one from the heap part of the list, and then insert
them into the sorted part of the list. Heapsort is the in-place sorting algorithm.

● Working of Heap Sort Algorithm:

In heap sort, basically, there are two phases involved in the sorting of elements.
By using the heap sort algorithm, they are as follows -

○ The first step includes the creation of a heap by adjusting the elements of
the array.
○ After the creation of the heap, now remove the root element of the heap
repeatedly by shifting it to the end of the array, and then store the heap
structure with the remaining elements.

Now let's see the working of heap sort in detail by using an example. To
understand it more clearly, let's take an unsorted array and try to sort it using
heap sort. It will make the explanation clearer and easier.

First, we have to construct a heap from the given array and convert it into max
heap.
After converting the given heap into max heap, the array elements are -

Next, we have to delete the root element (89) from the max heap. To delete this
node, we have to swap it with the last node, i.e. (11). After deleting the root
element, we again have to heapify it to convert it into max heap.

After swapping the array element 89 with 11, and converting the heap into
max-heap, the elements of array are -

In the next step, again, we have to delete the root element (81) from the max
heap. To delete this node, we have to swap it with the last node, i.e. (54). After
deleting the root element, we again have to heapify it to convert it into max heap.
After swapping the array element 81 with 54 and converting the heap into
max-heap, the elements of array are -

In the next step, we have to delete the root element (76) from the max heap
again. To delete this node, we have to swap it with the last node, i.e. (9). After
deleting the root element, we again have to heapify it to convert it into max heap.

After swapping the array element 76 with 9 and converting the heap into
max-heap, the elements of array are -

In the next step, again we have to delete the root element (54) from the max
heap. To delete this node, we have to swap it with the last node, i.e. (14). After
deleting the root element, we again have to heapify it to convert it into max heap.

After swapping the array element 54 with 14 and converting the heap into
max-heap, the elements of array are -

In the next step, again we have to delete the root element (22) from the max
heap. To delete this node, we have to swap it with the last node, i.e. (11). After
deleting the root element, we again have to heapify it to convert it into max heap.

After swapping the array element 22 with 11 and converting the heap into
max-heap, the elements of array are -

In the next step, again we have to delete the root element (14) from the max
heap. To delete this node, we have to swap it with the last node, i.e. (9). After
deleting the root element, we again have to heapify it to convert it into max heap.
After swapping the array element 14 with 9 and converting the heap into
max-heap, the elements of array are -

In the next step, again we have to delete the root element (11) from the max
heap. To delete this node, we have to swap it with the last node, i.e. (9). After
deleting the root element, we again have to heapify it to convert it into max heap.

After swapping the array element 11 with 9, the elements of array are -

Now, heap has only one element left. After deleting it, heap will be empty.

After completion of sorting, the array elements are -

Now, the array is completely sorted.

➔ Huffman Encoding (Implementation using Priority Queue)
● Huffman code is a data compression algorithm which uses the greedy technique
for its implementation. The algorithm is based on the frequency of the characters
appearing in a file.
● Greedy Algorithm for Constructing a Huffman Code:

○ Huffman invented a greedy algorithm that creates an optimal prefix code

called Huffman code
○ The Huffman Code is obtained for each distinct character in primarily two
steps:
Step 1: Create a Huffman Tree first using only the unique
characters in the data stream provided.
Step 2: Second, we must proceed through the constructed Huffman
Tree, assign codes to the characters, and then use those codes to decode
the provided text.

● How Can a Huffman Tree Be Constructed from Input Characters? Step 1: Sort
the characters by frequency, ascending. These are kept in a Q/min-heap priority
queue.
Step 2: For each distinct character and its frequency in the data stream,
create a leaf node.
Step 3: Remove the two nodes with the two lowest frequencies from the
nodes, and the new root of the tree is created using the sum of these
frequencies.
○ Make the first extracted node its left child and the second extracted node its
right child while extracting the nodes with the lowest frequency from the
min-heap.
○ To the min-heap, add this node.
○ Since the left side of the root should always contain the minimum frequency.

Step 4: Repeat steps 3 and 4 until there is only one node left on the heap,
or all characters are represented by nodes in the tree. The tree is finished when
just the root node remains.

● Example:-
Character Frequency

a 4
 b 7

c 3

d 2

e 4

Step 1: Build a min-heap in which each node represents the root of a tree with a
single node and holds 5 (the number of unique characters from the provided
stream of data).

Step 2: Obtain two minimum frequency nodes from the min heap in step two. Add
a third internal node, frequency 2 + 3 = 5, which is created by joining the two
extracted nodes.

○ Now, there are 4 nodes in the min-heap, 3 of which are the roots of trees
with a single element each, and 1 of which is the root of a tree with two
elements.

Step 3: Get the two minimum frequency nodes from the heap in a similar manner
in step three. Additionally, add a new internal node formed by joining the two
extracted nodes; its frequency in the tree should be 4 + 4 = 8.
 ○ Now that the minimum heap has three nodes, one node serves as the root
of trees with a single element and two heap nodes serve as the root of
trees with multiple nodes.

Step 4: Get the two minimum frequency nodes in step four. Additionally, add a
new internal node formed by joining the two extracted nodes; its frequency in the
tree should be 5 + 7 = 12.
○ When creating a Huffman tree, we must ensure that the minimum value is
always on the left side and that the second value is always on the right
side. Currently, the image below shows the tree that has formed:

Step 5: Get the following two minimum frequency nodes in step 5. Additionally,
add a new internal node formed by joining the two extracted nodes; its frequency
in the tree should be 12 + 8 = 20.

Continue until all of the distinct characters have been added to the tree. The
Huffman tree created for the specified cast of characters is shown in the above
image.
Now, for each non-leaf node, assign 0 to the left edge and 1 to the right edge to
create the code for each letter.

Rules to follow for determining edge weights:

○ We should give the right edges weight 1 if you give the left edges weight 0.
○ If the left edges are given weight 1, the right edges must be given weight 0.
○ Any of the two aforementioned conventions may be used.
○ However, follow the same protocol when decoding the tree as well.

Following the weighting, the modified tree is displayed as follows:

● Understanding the Code
○ We must go through the Huffman tree until we reach the leaf node, where
the element is present, in order to decode the Huffman code for each
character from the resulting Huffman tree.
○ The weights across the nodes must be recorded during traversal and
allocated to the items located at the specific leaf node.
○ The following example will help to further illustrate what we mean: ○ To
obtain the code for each character in the picture above, we must walk the
entire tree (until all leaf nodes are covered).
○ As a result, the tree that has been created is used to decode the codes for
each node. Below is a list of the codes for each character:
Character Frequency/count Code

a 4 01

b 7 11

c 3 101
d 2 100

e 4 00