SVKMs NMIMS

Mukesh Patel School of Technology Management and Engineering, Shirpur

Course: Data Structures and Algorithms
--------------------------------------------------------------------------------------------------------
Unit – IV
Linear Data Structure II

4.1. Introduction to Non Linear Data Structures

This section covers nonlinear data structures. While linear data structures like arrays and
queues arrange elements in a sequential order, nonlinear data structures allow for more
complex relationships among data elements. These structures do not follow a straight line;
instead, they enable hierarchical or interconnected arrangements, making them ideal for
modelling real-world systems where elements are related in multiple ways. Nonlinear data
structures are foundational in areas that require flexible data organization, such as artificial
intelligence, databases, and network design.

Two of the most prominent examples of nonlinear data structures are trees and graphs. A
tree is a hierarchical structure consisting of nodes connected by edges, starting from a root
node and branching into child nodes. Common types include binary trees, binary search trees
(BSTs), AVL trees, and B-trees. Each serves specific purposes, such as efficient searching or
balanced data storage. On the other hand, a graph is a collection of vertices (nodes)
connected by edges, which can be directed or undirected, weighted or unweighted. Graphs
are more general than trees and can represent complex relationships, including cycles and
multiple connections between nodes.

These nonlinear structures have wide-ranging applications in computer science. Trees are
used in file systems, database indexing, compiler design, and decision-making algorithms.
Graphs are essential in modelling computer networks, social media connections,
transportation systems, and search engine algorithms. Their ability to represent complex
relationships and support efficient traversal and search operations makes them indispensable
tools in modern computing.

4.2. Binary Tree: Introduction

A binary tree is a fundamental data structure in computer science, widely used in various
applications such as searching, sorting, expression parsing, and hierarchical data
representation. It is a type of tree data structure where each node has at most two children,
commonly referred to as the left child and the right child.

Why Binary Trees?

Binary trees offer a structured way to store data that allows efficient insertion, deletion, and
traversal operations. They are particularly useful in scenarios where hierarchical relationships
exist, such as:

Unit-III : Linear Data Structures-II (Linked List) Page 1 of 34

 SVKMs NMIMS
Mukesh Patel School of Technology Management and Engineering, Shirpur
Course: Data Structures and Algorithms
--------------------------------------------------------------------------------------------------------
 Representing arithmetic expressions
 Organizing data for quick search (e.g., Binary Search Trees)
 Implementing priority queues (e.g., Heaps)
 Facilitating efficient sorting algorithms (e.g., Tree Sort)

4.2.1. Binary Tree Terminologies

Understanding binary trees requires familiarity with several key terms. Below is a detailed
explanation of each:

1. Node
A node is the basic unit of a binary
tree. Each node contains:
 Data (or value)
 A pointer/reference to the left
child
 A pointer/reference to the
right child
2. Root
The root is the topmost node of a
binary tree. It is the starting point
for any traversal or operation. A
tree can have only one root.
3. Child
A child is a node that descends from
another node. In binary trees, each
node can have:
 Left child
 Right child
4. Parent
A parent is a node that has one or more children. If node A points to node B, then A is
the parent of B.
5. Leaf Node
A leaf node is a node that does not have any children. These are the terminal nodes of
a binary tree.
6. Subtree
A subtree is a portion of a tree that forms a tree itself. Every node in a binary tree can
be considered the root of its own subtree.
7. Degree
The degree of a node is the number of children it has. In a binary tree, the degree can
be 0, 1, or 2.

Unit-III : Linear Data Structures-II (Linked List) Page 2 of 34

 SVKMs NMIMS
Mukesh Patel School of Technology Management and Engineering, Shirpur
Course: Data Structures and Algorithms
--------------------------------------------------------------------------------------------------------
8. Level
The level of a node refers to its
depth in the tree, starting from the
root at level 0. Each subsequent
child level increases by 1.
9. Height
The height of a binary tree is the
length of the longest path from the
root to a leaf. It is a measure of the
tree’s depth. A binary tree of height
h can have at most 2h+1 -1.
10. Depth
The depth of a node is the number
of edges from the root to that node.
It is similar to level but used in
different contexts.
11. Balanced Tree
A balanced binary tree is one
in which the height
difference between the left
and right subtrees of any
node is at most one.
Balanced trees ensure
optimal performance for
operations like search and
insertion.
12. Full Binary Tree
A full binary tree is a tree in
which every node has either
0 or 2 children. No node has
only one child.
13. Perfect Binary Tree
A perfect binary tree is a tree
in which all internal nodes
have two children and all leaf
nodes are at the same level.
14. Complete Binary Tree
A complete binary tree is a
tree in which all levels are
completely filled except
possibly the last, which is
filled from left to right.

Unit-III : Linear Data Structures-II (Linked List) Page 3 of 34

 SVKMs NMIMS
Mukesh Patel School of Technology Management and Engineering, Shirpur
Course: Data Structures and Algorithms
--------------------------------------------------------------------------------------------------------
The diagram shown for the Complete Binary Tree can also serve as an example of a Full
Binary Tree, which is not a Perfect Binary Tree.

15. Binary Search Tree (BST)

A BST is a special type of binary tree where:

 The left subtree of a node contains only nodes with values less than the node’s
value.
 The right subtree contains only nodes with values greater than the node’s value.

BSTs allow efficient searching, insertion, and deletion operations.

16. Binary Heap

A binary heap is a complete binary tree used to implement priority queues. It can be:

 Min-Heap: Parent node is smaller than its children.

 Max-Heap: Parent node is larger than its children.

17. Threaded Binary Tree

A threaded binary tree is a variation where null pointers are replaced with pointers to the
inorder predecessor or successor, improving traversal efficiency.

18. Degenerate (or Pathological) Tree

A degenerate tree is a tree where each parent node has only one child. It behaves like a linked
list and is inefficient for operations.

19. Mirror Tree

Given a binary tree, a mirror tree is a binary tree where the left and right children of all nodes
of the original binary tree are swapped. It is the mirror image of the original tree.

4.2.2. Memory Representation of Binary Tree

The memory representation of binary trees plays a critical role in determining the efficiency
of storage, traversal, and manipulation operations. This section focuses exclusively on the two
primary methods used to represent binary trees in memory: linked representation and array
representation. Each method offers distinct structural characteristics and is suited to specific
types of binary trees and computational requirements.

Unit-III : Linear Data Structures-II (Linked List) Page 4 of 34

 SVKMs NMIMS
Mukesh Patel School of Technology Management and Engineering, Shirpur
Course: Data Structures and Algorithms
--------------------------------------------------------------------------------------------------------
The linked representation approach enables dynamic memory allocation and is particularly
effective for trees with irregular or sparse structures. In contrast, the array representation
stores tree elements in contiguous memory locations, using index-based formulas to establish
parent-child relationships. This method is most efficient when the binary tree is complete or
nearly complete. This section presents a comparative analysis of both representations,
highlighting their memory layouts, indexing logic, and suitability for various tree
configurations. By understanding these memory models, one can make informed decisions
about which representation to adopt based on the nature of the binary tree and the
operations to be performed.

4.2.2.1. Array Based Representation of Binary Tree

In array-based memory representation, a binary tree is stored in a sequential array using

level-order traversal (also known as breadth-first traversal). This method is especially efficient
for complete or nearly complete binary trees. In this representation, a binary tree is stored in
a one-dimensional array where each node's position in the tree corresponds to a specific
index in the array. The indexing rule is commonly used in the array representation of binary
trees, especially binary heaps. This method allows a binary tree to be stored efficiently in a
linear data structure like an array, without using pointers or references for child and parent
nodes.

In this method, the root node is always stored at index 0 of the array. For any node located at
index i, its left child is placed at index 2i + 1, and its right child is placed at index 2i + 2.
Conversely, the parent of any node at index i (except the root) can be found at index
floor((i - 1) / 2). This mathematical relationship allows for efficient navigation between parent
and child nodes using simple arithmetic, making
it ideal for algorithms that require frequent
access and updates, such as heap operations.

The Tree and its equivalent array representation

is given here:

Index 0 1 2 3 4 5 6
Value A B C D E - G

This representation is memory-efficient for

complete binary trees because it avoids the overhead of storing pointers or references, and
it allows constant-time access to parent or child nodes. However, it becomes inefficient for
sparse or unbalanced trees, as it may lead to unused array spaces and wasted memory, similar
to the index 5. The children of the node B (available at index 1) are available at the index
3(2*1+1) & 4 (2*1+2), whereas the parent of G (available at index 6) is 2(= floor((6-1)/2)).
Despite this limitation, the array-based indexing rule remains a fundamental concept in data
structures due to its simplicity and performance benefits in specific scenarios.

Unit-III : Linear Data Structures-II (Linked List) Page 5 of 34

 SVKMs NMIMS
Mukesh Patel School of Technology Management and Engineering, Shirpur
Course: Data Structures and Algorithms
--------------------------------------------------------------------------------------------------------
4.2.2.2. Linked Based Representation of Binary Tree

The linked-based memory representation of a binary tree is a dynamic and flexible method of
storing tree data structures in computer memory. In this approach, each node of the binary
tree is represented as a separate object or structure that contains three fields: one for storing
the data (or key) and two pointers or references, one pointing to the left child and the other
to the right child.
Left Child Pointer Data Right Child Pointer

The root node serve as the entry point to the tree, and all other nodes are connected through
these left and right pointers, forming a hierarchical structure. The Linked list representation
equivalent to the tree diagram from 4.2.2.1 is shown here.

This representation is particularly advantageous when the binary tree is sparse or when the
number of nodes is not known in advance, as it allows for efficient memory usage and
dynamic allocation. Unlike array-based representations, which may waste memory due to
unused indices in incomplete trees, the linked representation only allocates memory for
nodes that actually exist. This makes it ideal for applications such as expression trees, decision
trees, and binary search trees, where the structure of the tree can vary significantly.

Traversal operations such as inorder, preorder, and postorder are naturally implemented
using recursion or stacks, leveraging the pointer-based connectivity of the nodes. Insertion
and deletion operations are also more straightforward in this model, as they involve simply
adjusting the pointers without the need to shift elements, as would be required in an array.
Moreover, the linked representation supports trees of arbitrary size and shape, making it
highly adaptable to various computational problems. However, it does come with some
overhead, as each node requires additional memory for storing pointers, and accessing a
specific node may require traversal from the root, unlike the direct indexing possible in arrays.
Despite this, the benefits of flexibility, dynamic memory management, and ease of structural

Unit-III : Linear Data Structures-II (Linked List) Page 6 of 34

 SVKMs NMIMS
Mukesh Patel School of Technology Management and Engineering, Shirpur
Course: Data Structures and Algorithms
--------------------------------------------------------------------------------------------------------
modifications make the linked-based representation a preferred choice in many real-world
applications involving hierarchical data.

4.2.1. Construction of Binary Tree

Constructing a binary tree from given data involves arranging elements such that each node
has at most two children: a left and a right child. The construction method depends on the
format and interpretation of the input, whether it's a list of values, a level-order traversal, or
a set of parent-child relationships.

In a typical level-order construction, elements are inserted sequentially from the input,
starting with the root. Each node is created and its left and right children are assigned based
on the next available values. This method ensures a complete binary tree structure when all
positions are filled.

If the input includes null markers (e.g., NULL or -1) to indicate missing children, the
construction must account for these gaps, resulting in an incomplete binary tree. The process
can be implemented using a queue to keep track of nodes whose children are yet to be
assigned.

The construction can be done using:

 Linked representation, where each node is dynamically created with pointers to its
children.
 Array representation, where nodes are placed at specific indices based on their
position in the tree.

The choice of construction logic depends on the intended structure and traversal behavior.
Once constructed, the binary tree can be used for various operations such as traversal, height
calculation, and structural analysis.

Consider the data : 12,23,16,47,39,33,55. The binary tree representation for the data is given
below:

Unit-III : Linear Data Structures-II (Linked List) Page 7 of 34

 SVKMs NMIMS
Mukesh Patel School of Technology Management and Engineering, Shirpur
Course: Data Structures and Algorithms
--------------------------------------------------------------------------------------------------------
To insert the numbers 12, 23, 16, 47, 39, 33, and 55 into a complete binary tree, we follow a
level-order insertion approach, ensuring that all levels are filled from left to right before
moving to the next level.

We begin by inserting 12 as the root. Next, 23 becomes the left child of 12, and 16 becomes
the right child. Moving to the next level, 47 is inserted as the left child of 23, followed by 39
as its right child. Then, 33 is placed as the left child of 16, and finally, 55 is inserted as the right
child of 16. This results in a complete binary tree where all levels are fully filled, and the nodes
are added from left to right, maintaining the completeness property.

Algorithm for insertion in to a binary tree is given below :

Algorithm InsertCompleteBinaryTree(ROOT, value)

STEP 1. If ROOT is NULL:
a. Create a newNode with value
b. Set ROOT = newNnode
c. Return root

STEP 2. Initialize an empty queue Q

STEP 3. Enqueue ROOT into Q
STEP 4. While Q is not empty:
a. current = Q.front()
b. If current.LEFT is NULL:
i. Create a newNode with value
ii. Set current.LEFT = newNode
iii. Return ROOT
Else:
iv. Enqueue current.LEFT into Q

c. If current.right is NULL:
i. Create a new node with value
ii. Set current.RIGHT = newNode
iii. Return ROOT
Else:
iv. Enqueue current.RIGHT into Q

d. Dequeue current from Q

The algorithm for inserting elements into a complete binary tree using a queue data structure
is designed to maintain the structural integrity of the tree, ensuring that all levels are filled
from left to right before moving to the next level. This approach is particularly useful when
building a tree dynamically, as it guarantees that the resulting tree remains complete at every
stage of insertion.

Unit-III : Linear Data Structures-II (Linked List) Page 8 of 34

 SVKMs NMIMS
Mukesh Patel School of Technology Management and Engineering, Shirpur
Course: Data Structures and Algorithms
--------------------------------------------------------------------------------------------------------
The process begins by checking if the root node is null; if it is, the first value is inserted as the
root. For subsequent insertions, a queue is used to perform a level-order traversal of the tree.
This means nodes are visited level by level, from left to right, using the queue to keep track
of nodes whose children are yet to be filled.

Each time a new value is to be inserted, the algorithm dequeues a node from the front of the
queue and checks whether its left child is null. If it is, the new node is inserted as the left child,
and the process ends for that value. If the left child exists, it is enqueued for future processing.
The algorithm then checks the right child of the current node. If it is null, the new node is
inserted as the right child. If not, the right child is also enqueued. This process continues until
a suitable position is found for the new node, ensuring that the tree remains complete. The
use of a queue is crucial because it allows the algorithm to maintain the correct order of node
processing, ensuring that nodes are filled from top to bottom and left to right.

This method is efficient and straightforward, making it ideal for applications where a
complete binary tree structure is required, such as in heap implementations or certain types
of scheduling algorithms.

By repeatedly applying this algorithm for each value in the input list, a complete binary tree
is constructed incrementally. For example, inserting the values 12, 23, 16, 47, 39, 33, and 55
would result in a tree where 12 is the root, 23 and 16 are its children, 47 and 39 are the
children of 23, and 33 and 55 are the children of 16. This structure satisfies the definition of
a complete binary tree, with all levels fully filled and nodes added from left to right. The
algorithm’s simplicity and effectiveness make it a fundamental technique in tree-based data
structures, and its reliance on the queue data structure highlights the importance of level-
order traversal in maintaining tree completeness.

4.2.2. Binary Tree Traversal

Traversal refers to visiting all nodes of a binary tree in a specific order. Common traversal
methods include:

 Inorder Traversal (LEFT, ROOT, RIGHT)

Inorder traversal is one of the fundamental traversal techniques used in binary trees. In this
method, the nodes are visited in the following order: left subtree → ROOT → right subtree.
This means that for any given node, the algorithm first recursively visits all nodes in its left
subtree, then processes the current node, and finally recursively visits all nodes in its right
subtree. In the case of a binary search tree (BST), inorder traversal yields the nodes in sorted
(ascending) order, making it particularly useful for retrieving data in a structured format. The
traversal can be implemented using either recursion or an explicit stack for iterative
processing.

Unit-III : Linear Data Structures-II (Linked List) Page 9 of 34

 SVKMs NMIMS
Mukesh Patel School of Technology Management and Engineering, Shirpur
Course: Data Structures and Algorithms
--------------------------------------------------------------------------------------------------------
For example, given a BST with nodes arranged as 12 (ROOT), 8 (LEFT), and 16 (RIGHT), the
inorder traversal would visit 8 → 12 → 16. This traversal is widely used in applications such as
expression tree evaluation, syntax tree parsing, and data serialization.

The algorithm for the Inorder traversal is given below :

Inorder(ROOT) Algorithm

STEP 1. If ROOT is NULL, Then Return

STEP 2. InorderTraversal(ROOT.LEFT) // Traverse left subtree
STEP 3. Visit(ROOT) // Process Root node (e.g., print or store value)
STEP 4. InorderTraversal(ROOT.RIGHT) // Traverse right subtre

 Preorder Traversal (Root, Left, Right)

Preorder traversal is a fundamental depth-first traversal technique used in binary trees,

where nodes are visited in the order: ROOT → left subtree → right subtree. This means that
for any given node, the algorithm first processes the current node, then recursively visits all
nodes in its left subtree, followed by those in its right subtree. Preorder traversal is
particularly useful in applications where the root node must be handled before its children,
such as in tree copying, prefix expression evaluation, and hierarchical data representation.
Unlike inorder traversal, which yields sorted data in a binary search tree, preorder traversal
focuses on accessing the root before exploring its descendants. It can be implemented using
recursion or an explicit stack for iterative processing.

For example, given a binary tree with nodes arranged as 12 (ROOT), 8 (LEFT), and 16 (RIGHT),
the preorder traversal would visit 12 → 8 → 16. This traversal is ideal for scenarios where the
structure of the tree needs to be preserved or reconstructed, as it captures the root-first
hierarchy of the tree. The Final Preorder for the given example is : 12 → 8 → 16

The algorithm for the Preorder traversal is given below :

Preorder(ROOT) Algorithm

STEP 1. If node is NULL, Then Return

STEP 2. Visit(ROOT) // Process Root node (e.g., print or store value)
STEP 3. PreorderTraversal(ROOT.LEFT) // Traverse left subtree
STEP 4. PreorderTraversal(ROOT.RIGHT)// Traverse right subtree

 Postorder Traversal (Left, Right, Root)

Postorder traversal is a fundamental depth-first traversal technique used in binary trees,

where nodes are visited in the order: left subtree → right subtree → root. This means that
for any given node, the algorithm first recursively explores all nodes in its left subtree, then

Unit-III : Linear Data Structures-II (Linked List) Page 10 of 34

 SVKMs NMIMS
Mukesh Patel School of Technology Management and Engineering, Shirpur
Course: Data Structures and Algorithms
--------------------------------------------------------------------------------------------------------
proceeds to the right subtree, and finally processes the current node itself. This traversal is
particularly useful in scenarios where hierarchical dependencies must be resolved from the
bottom up, such as in deleting a tree, evaluating postfix expressions, or freeing memory in
tree structures. Unlike inorder traversal, which yields sorted data in a binary search tree,
postorder traversal focuses on completing all child node operations before handling the
parent node. It can be implemented using recursion or an explicit stack for iterative
processing.

For example, given a binary tree with nodes arranged as 12 (root), 8 (left), and 16 (right), the
postorder traversal would visit 8 → 16 → 12. This traversal ensures that all subtrees are fully
processed before the root, making it ideal for tasks that require post-processing of child
elements.

The algorithm for the Postorder traversal is given below :

Postorder(ROOT) Algorithm

STEP 1. If node is NULL, Then Return

STEP 2. PostorderTraversal(Root.left) // Traverse left subtree
STEP 3. PostorderTraversal(Root.right) // Traverse right subtree
STEP 4. Visit(Root) // Process Root node (e.g., print or store value)

Consider the application of the Inorder, preorder and postorder traversal algorithm for the
following binary tree.

The Inorder traversal can be given as : 47→23→39→12→33→16→55.

The Preorder traversal can be given as : 12→23→47→39→16→33→55.
The Postorder traversal can be given as : 47→39→23→33→55→16→12.

4.2.3. Binary Tree Construction from the given traversal

Inorder, preorder, and postorder are linear representations that encode the structure of the
tree in a compact form. These sequences are often stored or transmitted instead of the full

Unit-III : Linear Data Structures-II (Linked List) Page 11 of 34

 SVKMs NMIMS
Mukesh Patel School of Technology Management and Engineering, Shirpur
Course: Data Structures and Algorithms
--------------------------------------------------------------------------------------------------------
tree to save space and simplify data handling. Constructing a binary tree from given traversals
is crucial because traversals to perform meaningful operations such as searching, inserting,
deleting, or applying algorithms like expression evaluation or Huffman coding, the actual
hierarchical structure of the tree must be reconstructed. Traversals alone do not reveal
parent-child relationships or the shape of the tree, which are essential for understanding and
manipulating the data effectively. By reconstructing the tree from traversals, we can uniquely
identify and restore the original tree, enabling visualization, debugging, and further
algorithmic processing. Binary trees can be constructed from traversal sequences alone using
specific combinations that uniquely determine the tree structure.

The most reliable methods include using inorder with preorder or inorder with postorder
traversals, as these combinations allow us to identify the root node and divide the tree into
left and right subtrees, enabling accurate reconstruction. While preorder and postorder
together do not always yield a unique tree, they can still be used to construct a possible tree,
especially if the tree is known to be full.

Another valid approach is using level order with inorder, which, although more complex, can
also uniquely reconstruct the tree. In cases where only a single traversal is available,
reconstruction is possible if additional information like null markers or tree type constraints
(e.g., full binary tree, BST) is provided.

These methods are essential because traversal sequences are compact representations of
tree structures, often used for storage, transmission, or serialization, and reconstructing the
tree from them is necessary to perform meaningful operations like searching, evaluating
expressions, or applying tree-based algorithms.

4.2.3.1. Construction of Binary Tree from given In-order and Pre-order

Traversals

Steps to Construct Binary Tree from In-order and Pre-order Traversals

i. Start with the first node in Pre-order, this is the Root of the tree.
ii. Find the identified Root in the inorder traversal, this divides the inorder list into left
and right subtrees.
iii. Filter the In-order list to include only nodes that appear in the left and right parts of
the In-order list.
iv. Recursively repeat the process for left and right subtrees using the filtered Post-order
and corresponding In-order segments.

Example : Consider the following Inorder and level order :

In-Order: 25 50 75 100 125 150 175
Pre-Order: 100 50 25 75 150 125 175

1. Root is 100 (first in Pre-order)

Unit-III : Linear Data Structures-II (Linked List) Page 12 of 34

 SVKMs NMIMS
Mukesh Patel School of Technology Management and Engineering, Shirpur
Course: Data Structures and Algorithms
--------------------------------------------------------------------------------------------------------
In In-order, 100 splits the list into:
a. Left subtree: 25 50 75
b. Right subtree: 125 150 175
2. Filter Pre-order:
a. Left subtree Pre-order: 50 25 75
b. Right subtree Pre order: 150 125 175
3. Recursively consider each subtree from level order for finding Root of the subtree and
use In-order Traversal to identify Left and Subtree for the selected Root.

The Resultant Binary Tree is given below:

4.2.3.2. Construction of Binary Tree from given In-order and Post-order

Traversals

Steps to Construct Binary Tree from In-order and Post-order Traversals

i. Start with the Last node in Post-order, this is the Root of the tree.
ii. Find the identified root in the In-order traversal, this divides the In-order list into left
and right subtrees.
iii. Filter the In-order list to include only nodes that appear in the left and right parts of
the In-order list.
iv. Recursively repeat the process for left and right subtrees using the filtered Post-order
and corresponding In-order segments.

Example : Consider the following In-order and Post-order :

In-Order: 25 50 75 100 125 150 175
Pre-Order: 25 75 50 125 175 150 100

1. Root is 100 (first in Pre-order)

In In-order, 100 splits the list into:
a. Left subtree: 25 50 75
b. Right subtree: 125 150 175
2. Filter Post-order:
a. Left subtree Post-order: 25 75 50
b. Right subtree Post order: 125 175 150

Unit-III : Linear Data Structures-II (Linked List) Page 13 of 34

 SVKMs NMIMS
Mukesh Patel School of Technology Management and Engineering, Shirpur
Course: Data Structures and Algorithms
--------------------------------------------------------------------------------------------------------
3. Recursively consider each subtree from level order for finding Root of the subtree and
use In-order Traversal to identify Left and Subtree for the selected Root.

The Resultant Binary Tree is given below:

4.2.3.3. Construction of Binary Tree from given Post-order and Pre-order

Traversals

4.2.3.4. Construction of Binary Tree from given Level-order and In-order

Traversals
Level Order Traversal is a method of traversing a binary tree where nodes are visited level by
level from top to bottom and left to right within each level. It starts at the Root node, then
visits all nodes at depth 1 (children of the Root), followed by all nodes at depth 2, and so on.

Consider the following binary tree.

The Level-order traversal can be given as: 12→23→16→47→39→33→55.

This traversal is typically implemented using a queue data structure, which helps maintain the
order of nodes to be visited next, where we enqueue the Root, then its children, and continue
processing nodes in the order they were added. Level order traversal is especially useful for
visualizing the structure of the tree, performing breadth-first searches, and solving problems
where hierarchical relationships matter, such as finding the shortest path or printing the tree
in a human-readable format.

Unit-III : Linear Data Structures-II (Linked List) Page 14 of 34

 SVKMs NMIMS
Mukesh Patel School of Technology Management and Engineering, Shirpur
Course: Data Structures and Algorithms
--------------------------------------------------------------------------------------------------------
Steps to Construct Binary Tree from Level Order and Inorder Traversals

i. Start with the first node in Level order, this is the Root of the tree.
ii. Find the Root in the In-order traversal, this divides the In-order list into left and right
subtrees.
iii. Filter the Level order list to include only nodes that appear in the left and right parts of
the In-order list.
iv. Recursively repeat the process for left and right subtrees using the filtered Level order
and corresponding In-order segments.

Example : Consider the following In-order and Level-order :

Inorder: 25 50 75 100 125 150 175
Level Order: 100 50 150 25 75 125 175

1. Root is 100 (first in Level-order)

In In-order, 100 splits the list into:
a. Left subtree: 25 50 75
b. Right subtree: 125 150 175
2. Filter Level-order:
a. Left subtree Level-order: 50 25 75
b. Right subtree Level-order: 150 125 175
3. Recursively consider each subtree from Level-order for finding Root of the subtree and
use In-order Traversal to identify Left and Subtree for the selected Root.
The Resultant Binary Tree is given below:

4.3. Binary Search Tree (BST)

A Binary Search Tree (BST) is a specialized form of a binary tree where each node contains a
value such that all values in its left subtree are less than the node’s value, and all values in its
right subtree are greater. This structure allows for efficient data operations and offers several
key benefits. One of the primary advantages is fast searching, as BSTs enable lookup
operations in logarithmic time complexity (O(log n)) in the best and average cases, especially
when the tree is balanced. This makes them significantly more efficient than linear data
structures like arrays or linked lists for large datasets.

Unit-III : Linear Data Structures-II (Linked List) Page 15 of 34

 SVKMs NMIMS
Mukesh Patel School of Technology Management and Engineering, Shirpur
Course: Data Structures and Algorithms
--------------------------------------------------------------------------------------------------------
This structure allows efficient searching, insertion, and deletion operations, typically with an
average time complexity of O(log n), although in the worst case (e.g., a skewed tree), it can
degrade to O(n). BSTs usually do not allow duplicate values, and if they do, duplicates are
handled in a specific manner. Such that the duplicates are inserted in the right subtree in the
form of an in-order successor to the node. The tree is inherently recursive, as each subtree is
itself a BST. Traversal methods include in-order, pre-order, post-order, and level order, with
inorder traversal yielding values in sorted order. This benefit of sorted data retrieval of an
inorder traversal of a BST is useful for tasks like reporting, exporting, or displaying data in a
structured format. Moreover, BSTs support finding the inorder successor (next higher value)
and inorder predecessor (next lower value), are useful in various algorithms and applications.

The height of a BST significantly affects its performance, and balanced BSTs like AVL or Red-
Black Trees maintain optimal height close to log(n). The minimum value in a BST is found by
traversing the leftmost path, while the maximum value is found by traversing the rightmost
path. BSTs also support dynamic data management, allowing insertion and deletion of
elements without the need for resizing or shifting, unlike arrays. Their flexible structure makes
them adaptable into more advanced balanced trees such as AVL trees or Red-Black trees,
which maintain optimal performance even in worst-case scenarios. Additionally, BSTs are
widely used in various applications including databases, file systems, compilers, and memory
management systems, where quick access to sorted or hierarchical data is essential. Overall,
the binary search tree is a powerful and versatile data structure that combines efficiency with
simplicity, making it a cornerstone in computer science and software development.

4.4.1. Insertion in to a BSTree

Inserting a node into a Binary Search Tree (BST) involves placing the new value in its correct
position so that the BST properties are maintained. The process begins by comparing the
value to be inserted with the root node. If the value is less than the root, we move to the left
subtree; if it is greater, we move to the right subtree. This comparison continues recursively
(or iteratively) until we find a position where the left or right child is NULL, indicating that the
new node can be inserted there. For
example, if we want to insert the value 25
into a BST with root 30, we compare 25
with 30 and move left. If the left child is 20,
we compare 25 with 20 and move right. If
the right child of 20 is NULL, we insert 25
there. This method ensures that the tree
remains a valid BST, where all left
descendants are smaller and all right
descendants are larger than their parent
nodes. The insertion operation has a time
complexity of O(log n) in a balanced BST,
making it efficient for dynamic data
storage and retrieval.

Unit-III : Linear Data Structures-II (Linked List) Page 16 of 34

 SVKMs NMIMS
Mukesh Patel School of Technology Management and Engineering, Shirpur
Course: Data Structures and Algorithms
--------------------------------------------------------------------------------------------------------
The Algorithm for insertions of a value in a binary search tree is given below :

Algorithm: Initialize Binary Search Tree

STEP 1.Define a structure called Node with three fields:

a. INFO – to store the value of the node
b. LEFT – to store the reference to the Left Child node
c. RIGHT – to store the reference to the Right Child node

STEP 2. Declare a pointer variable ROOT to represent the starting point of the Tree list.
STEP 3. Set ROOT = NULL to indicate that the list is initially empty.

This algorithm sets up the basic structure of a Binary Search Tree (BST). First, we define a
structure called a Node, which has three parts: INFO to store the actual data, LEFT to point to
the left child, and RIGHT to point to the right child. Then, we declare a pointer called ROOT,
which will act as the starting point of our tree. Initially, we set ROOT = NULL, meaning the tree
is empty and ready to have nodes inserted. This setup is essential before performing any
operations like insertion or searching in the tree.

Algorithm createNewNode(Data)

STEP 1. BEGIN
STEP 2. If AVAIL = NULL, Then, Write “OVEERFLOW” & Go to STEP 8.
STEP 3. Set NewNode = AVAIL
STEP 4. Set AVAIL = AVAIL -> NEXT
STEP 5. Set NewNode-> INFO = Data
STEP 6. Set NewNode - > LEFT = NULL
STEP 7. Set NewNode - > RIGHt = NULL
STEP 8. RETURN NewNode

This algorithm is used to create a new node that can be inserted into the BST. It starts by
checking if there is available memory (represented by AVAIL). If AVAIL is NULL, it means
there’s no space to create a new node, and we display an "OVERFLOW" message. Otherwise,
we take a node from AVAIL, assign it to NewNode, and update AVAIL to point to the next
available node. Then, we store the given Data in NewNode.INFO, and set both LEFT and RIGHT
pointers of the new node to NULL, indicating that it has no children yet. Finally, we return this
newly created node so it can be inserted into the tree

Algorithm insertNode(ROOT, key)

STEP 1. BEGIN
STEP 2. if ROOT is NULL:
STEP 3. return createNewNode(key)
STEP 4. Set CURRENT = ROOT
STEP 5. Set PARENT = NULL

Unit-III : Linear Data Structures-II (Linked List) Page 17 of 34

 SVKMs NMIMS
Mukesh Patel School of Technology Management and Engineering, Shirpur
Course: Data Structures and Algorithms
--------------------------------------------------------------------------------------------------------
STEP 6. REPEAT STEPS 7, & 8 while CURRENT≠ NULL
STEP 7. Set PARENT = CURRENT
STEP 8. if key < CURRENT.INFO, then
i. CURRENT = CURRENT.LEFT
else
ii. CURRENT = CURRENT.RIGHT
STEP 9. if key < PARENT.INFO, then
i. PARENT.LEFT = createNewNode(key)
else:
ii. PARENT.RIGHT = createNewNode(key)
STEP 10. return ROOT

This algorithm inserts a new value (called key) into the BST. If the tree is empty (ROOT = NULL),
we simply create a new node and make it the root. If the tree already has nodes, we start
from the root and use two pointers: CURRENT to traverse the tree and PARENT to keep track
of the previous node. We move left or right depending on whether the key is less than or
greater than the current node’s value. Once we find the correct position (where CURRENT
becomes NULL), we attach the new node as either the left or right child of PARENT, based on
the comparison. This ensures that the BST property is maintained, where left children are
smaller and right children are larger than their parent.

Suppose we want to insert the following values into the BST:

50, 30, 70, 20, 40, 60, 80.

For each value, we use the createNewNode(Data) algorithm. This checks if memory is
available (represented by AVAIL). If available, it creates a new node with the given value, sets
its left and right pointers to NULL, and returns the node.

To begin with, we will use the insertNode(ROOT, key) algorithm to insert each value into the
tree:

1. Insert 50
Since ROOT is NULL, we create a new node with value 50 and set it as the root.
2. Insert 30
30 < 50 → move to the left of 50
Left child is NULL → insert 30 as the left child of 50
3. Insert 70
70 > 50 → move to the right of 50
Right child is NULL → insert 70 as the right child of 50
4. Insert 20
20 < 50 → move left to 30
20 < 30 → move left of 30
Left child is NULL → insert 20 as left child of 30

Unit-III : Linear Data Structures-II (Linked List) Page 18 of 34

 SVKMs NMIMS
Mukesh Patel School of Technology Management and Engineering, Shirpur
Course: Data Structures and Algorithms
--------------------------------------------------------------------------------------------------------
5. Insert 40
40 < 50 → move left to 30
40 > 30 → move right of 30
Right child is NULL → insert 40 as right child of 30
6. Insert 60
60 > 50 → move right to 70
60 < 70 → move left of 70
Left child is NULL → insert 60 as left child of 70
7. Insert 80
80 > 50 → move right to 70
80 > 70 → move right of 70
Right child is NULL → insert 80 as right child of 70.

The resultant Binary Search Tree is shown in the figure.

4.4.2. Searching a value in BST

Searching a node in a Binary Search Tree (BST) involves starting from the root and comparing
the target key with the current node’s value. If the key matches, the node is found; if the key
is smaller, the search continues in the left subtree; if larger, it proceeds to the right subtree.
This process repeats until the key is found or a NULL pointer is reached, indicating the key is
not present. Due to the BST’s ordered structure, this search is efficient, typically requiring
time proportional to the height of the tree, i.e., O(log n) in a balanced BST.

Algorithm SearchBSTree(ROOT, KEY)

STEP 1. BEGIN
STEP 2. Set CURRENT = ROOT
STEP 3. Repeat Steps 4 while CURRENT ≠ NULL
STEP 4. If KEY = CURRENT → VALUE, then
a. Write “NODE FOUND”.
b. RETURN CURRENT & Go to STEP 7
Else If KEY < CURRENT → VALUE, then
c. Set CURRENT = CURRENT → LEFT
Else
d. Set CURRENT = CURRENT → RIGHT
STEP 5. Write “NODE NOT FOUND”
STEP 6. RETURN NULL
STEP 7. END

This algorithm describes way to search for a specific value in a Binary Search Tree (BST). It
begins at the root of the tree and keeps checking whether the current node contains the
desired value. If it does, the search is successful. If not, it decides whether to move left or
right in the tree based on whether the key is smaller or larger than the current node’s value.
This process continues until the value is found or the search reaches the end of a branch,

Unit-III : Linear Data Structures-II (Linked List) Page 19 of 34

 SVKMs NMIMS
Mukesh Patel School of Technology Management and Engineering, Shirpur
Course: Data Structures and Algorithms
--------------------------------------------------------------------------------------------------------
meaning the value is not present in the tree. The algorithm then ends by returning either the
found node or indicating that the node was not found.

Consider the following Binary Search Tree:

Example: Search for Node with Value 60

1. Start at the root node (50).

Since 60 > 50, move to the right child.
2. Now at node 70.
Since 60 < 70, move to the left child.
3. Now at node 60.
The value matches the key we are searching for.
4. ✅ Node Found!

Example: Search for Node with Value 25

1. Start at the root node (50).

Since 25 < 50, move to the left child.

2. Now at node 30.
Since 25 < 30, move to the left child.
3. Now at node 20.
Since 25 > 20, move to the right child, but it's NULL.
4. ❌ Node Not Found!

This example shows how the BST structure helps in quickly narrowing down the search path
based on comparisons, making it efficient

4.4.3. Deleting a value from the given BST

Deleting a node from a Binary Search Tree (BST) is a structured process that depends on the
node's presence and its children. If the node value is not found, the search concludes without
any change to the tree. If the node is a leaf, meaning it has no children, it is removed by simply
disconnecting it from its parent. If the node has only one child, it is replaced by its child,
ensuring the BST properties remain intact. The most complex case is when the node has two
children; in this situation, the node’s value is replaced with either its in-order successor (the
smallest value in the right subtree) or in-order predecessor (the largest value in the left
subtree), and then the successor or predecessor node is deleted using one of the simpler
cases. This approach maintains the BST’s structure and ordering rules throughout the deletion
process.

Unit-III : Linear Data Structures-II (Linked List) Page 20 of 34

 SVKMs NMIMS
Mukesh Patel School of Technology Management and Engineering, Shirpur
Course: Data Structures and Algorithms
--------------------------------------------------------------------------------------------------------
Algorithm deleteNode(ROOT, key)

STEP 1. BEGIN
STEP 2. If ROOT = NULL, then Return NULL.
STEP 3. if KEY < ROOT → VALUE, then
i. ROOT→LEFT = deleteNode(ROOT→LEFT, key)
ii. Return ROOT
else if KEY > ROOT → VALUE, then
i. ROOT→RIGHT = deleteNode(ROOT→RIGHT, key)
ii. Return ROOT
else if KEY == ROOT → VALUE, then
I. if ROOT→LEFT =NULL and ROOT→RIGHT =NULL, then Return NULL
II. if ROOT→LEFT =NULL, then Return ROOT→RIGHT.
III. if ROOT→RIGHT =NULL, then Return ROOT→LEFT.
IV. Set SUCCESSOR = ROOT→RIGHT
V. Repeat Step 4.f , while SUCCESSOR →LEFT ≠ NULL
VI. Set SUCCESSOR = SUCCESSOR →LEFT
VII. ROOT →VALUE = SUCCESSOR →VALUE
VIII. ROOT→RIGHT = deleteNode(ROOT →RIGHT,SUCCESSOR →VALUE)
STEP 4. Return ROOT.
STEP 5. END.

This algorithm for deleting a node from a Binary Search Tree (BST) is serves as a precise and
structured guide for handling all possible cases during the deletion process. The algorithm
begins with a base condition that checks whether the root of the tree is null, which would
indicate either an empty tree or that the recursive search has reached a point where the key
is not present. In such a case, the function returns null, effectively terminating that branch of
recursion without making any changes to the tree. This is to handle the case of a node not
found. If the root is not null, the algorithm compares the key to be deleted with the value of
the current node. If the key is less than the root’s value, the algorithm recursively calls itself
on the left subtree and updates the left child of the root with the result of the deletion.
Similarly, if the key is greater than the root’s value, it proceeds to the right subtree and
updates the right child accordingly. These recursive calls continue until the node containing
the key is found. Once the node is located, the algorithm evaluates its structure to determine
the appropriate deletion strategy. If the node is a leaf (i.e., it has no children), it is removed
by returning null, which disconnects it from its parent. If the node has only one child, either
left or right, the algorithm returns that child, effectively bypassing the node and linking its
parent directly to its child. This ensures that the BST property is maintained while removing
the node.

The most complex case arises when the node has two children. In this scenario, the algorithm
finds the node’s in-order successor, which is the smallest node in its right subtree. To locate
the successor, it initializes a pointer to the right child and iteratively traverses the left children
until it reaches the leftmost node. Once the successor is found, its value is copied into the
node to be deleted, effectively replacing it. However, the successor still exists in the tree and

Unit-III : Linear Data Structures-II (Linked List) Page 21 of 34

 SVKMs NMIMS
Mukesh Patel School of Technology Management and Engineering, Shirpur
Course: Data Structures and Algorithms
--------------------------------------------------------------------------------------------------------
must be removed to avoid duplication. Since the successor is guaranteed to have at most one
child, the algorithm recursively calls itself to delete the successor from the right subtree. This
recursive deletion ensures that the successor is properly removed and that the tree remains
correctly structured. After handling all possible cases, whether the node is not found, is a leaf,
has one child, or has two children, the algorithm returns the updated root node, which
reflects the changes made during the deletion process. This return value propagates back up
through the recursive calls, ensuring that all parent nodes correctly update their child
pointers. The final return of the root node completes the deletion operation.

This recursive approach ensures that the BST remains valid after the deletion, preserving the
essential property that for any node, all values in its left subtree are less than its own value,
and all values in its right subtree are
greater.

Consider the Binary Search Tree, for the

understanding the deletion process. The
examples of all four deletion cases as per
the algorithm discussed earlier.

The first case, where the node to be

deleted is not found, can be demonstrated
by attempting to delete node ‘0090’, which
does not exist in the tree. The algorithm will
recursively search through the tree and
eventually reach a null pointer, returning
‘NULL’ and leaving the tree unchanged.

The second case involves deleting a leaf

node, which is a node with no children. Node
‘0038’ is a perfect example of this, as it has
no left or right child. When the algorithm
finds this node, it will return null, effectively
removing it from its parent node ‘0035’.

 The third case is the deletion of a node with

only one child. Node ‘0045’ fits this scenario,
as it has only one right child, ‘0042’. The
algorithm will replace 45 with its child ‘0042’,
maintaining the BST structure and ensuring
that the parent node ‘0040’ now points

Unit-III : Linear Data Structures-II (Linked List) Page 22 of 34

 SVKMs NMIMS
Mukesh Patel School of Technology Management and Engineering, Shirpur
Course: Data Structures and Algorithms
--------------------------------------------------------------------------------------------------------
directly to ‘0042’. Please note the original Binary Search Tree is considered for the
purpose of illustration.
 The fourth and most complex
case is the deletion of a node with two
children, which is best illustrated by
deleting node ‘0030’. This node has both
a left child ‘0020’ and a right child ‘0040’.
According to the algorithm, the in-order
successor must be found, which the
smallest node is in the right subtree, in
this case, node ‘0035’. The value of
‘0035’ is copied into node ‘0030’, and
then the algorithm recursively deletes
node ‘0035’, which is a simpler case
since ‘0035’ has only one child ‘0038’.
This process ensures that the BST
remains valid and properly ordered after
the deletion.

Each of these examples demonstrates how the algorithm handles different structural
scenarios in a BST, ensuring that the tree remains correctly linked and ordered after each
deletion operation.

4.4. Application of Binary Trees

A binary tree has a wide range of applications across computer science and real-world
systems due to its simple yet powerful hierarchical structure. One of its most common uses
is in expression parsing, where expression trees help evaluate mathematical formulas and
expressions. Binary trees are also fundamental in searching and sorting algorithms, especially
in the form of binary search trees (BSTs), which allow efficient data retrieval, insertion, and
deletion. They are used in hierarchical data representation, such as file systems,
organizational charts, and decision-making processes. In network routing algorithms, binary
trees help manage paths and connections efficiently. Additionally, they play a key role in data
compression techniques like Huffman coding, where binary trees are used to generate
optimal prefix codes. Despite their advantages, binary trees can become inefficient if not
balanced properly, leading to degraded performance in operations. However, when
implemented thoughtfully, they offer a clean and efficient way to manage structured data.

4.4.1. Construction of Expression Tree

An expression tree is a specialized binary tree used to represent and evaluate arithmetic
expressions in a structured and hierarchical manner. In this tree, leaf nodes represent
operands such as constants or variables, while internal nodes represent operators like

Unit-III : Linear Data Structures-II (Linked List) Page 23 of 34

 SVKMs NMIMS
Mukesh Patel School of Technology Management and Engineering, Shirpur
Course: Data Structures and Algorithms
--------------------------------------------------------------------------------------------------------
addition, subtraction, multiplication, or division. Expression trees are particularly useful
because they clearly capture the precedence and associativity of operations, making them
ideal for parsing and evaluating complex expressions in compilers and interpreters. They
allow easy conversion between different notations, infix, prefix, and postfix, and support
recursive evaluation, simplification, and optimization of expressions. However, despite these
advantages, expression trees can be memory-intensive and complex to construct, especially
from infix expressions that require parsing. For simple arithmetic operations, they may be less
efficient compared to linear representations like postfix notation. Nonetheless, their ability
to model expressions accurately and flexibly makes them a powerful tool in programming
language design and symbolic computation.

Steps to Construct an Expression Tree from a Postfix Expression

Input: A valid infix expression

Output: Root node of the corresponding expression tree
STEP 1. BEGIN
STEP 2. Initialize:
a. An empty stack for operators.
b. An empty list for output (postfix expression).
STEP 3. Scan the infix expression token by token:
a. If token is operand, Then Append to output.
b. If token is ‘(’, Then Push to stack.
c. If token is ‘)’ Then Pop from stack to output until ‘(’ is found. Discard ‘(’.
d. If token is operator, Then
i. WHILE stack is not empty and top of stack has higher or equal
precedence,
I. pop to output.
ii. Push current operator to stack.
STEP 4. After scanning all tokens, pop remaining operators from stack to output.
STEP 5. Initialize an empty stack for tree nodes.
STEP 6. Scan the postfix expression token by token:
STEP 7. If token is operand:
a. Create a new tree node.
b. Push to stack.
STEP 8. If token is operator:
STEP 9. Pop two nodes from stack.
a. Create a new node with the operator.
b. Set the first popped node as right child, second as left child.
c. Push the new node to stack.
STEP 10. After scanning the complete expression, the stack contains the root of the
expression tree.
STEP 11. END

The first step involves transforming the infix expression, which is naturally readable but
ambiguous due to operator precedence and parentheses, into a postfix expression that is

Unit-III : Linear Data Structures-II (Linked List) Page 24 of 34

 SVKMs NMIMS
Mukesh Patel School of Technology Management and Engineering, Shirpur
Course: Data Structures and Algorithms
--------------------------------------------------------------------------------------------------------
unambiguous and easier to process. This is done using an algorithm, which is also referred as
Shunting Yard Algorithm, which uses a stack to temporarily hold operators and a list to build
the output. As the expression is scanned from left to right, operands are directly added to the
output, while operators are pushed onto the stack based on their precedence and
associativity. Parentheses are used to control grouping: a left parenthesis is pushed onto the
stack, and when a right parenthesis is encountered, operators are popped from the stack to
the output until the matching left parenthesis is found. After the entire expression is scanned,
any remaining operators on the stack are popped to the output. The result is a postfix
expression that preserves the correct order of operations without requiring parentheses.

Once the postfix expression is obtained, the second step is to construct the expression tree
using a stack-based approach. The postfix expression is scanned token by token. For each
operand, a new tree node is created and pushed onto the stack. When an operator is
encountered, the top two nodes are popped from the stack, these represent the operator’s
operands. A new node is created with the operator as its value, and the two popped nodes
are assigned as its left and right children (the first popped node becomes the right child, and
the second becomes the left). This new subtree is then pushed back onto the stack. After the
entire postfix expression is processed, the stack contains a single node, which is the root of
the complete expression tree. This tree accurately represents the original infix expression,
capturing both the structure and precedence of operations.

Consider the Problem Statement: Given the infix arithmetic expression: “A + B / C - D * E –

F”, perform the following tasks:
1. Convert the infix expression into its equivalent postfix expression, ensuring correct
operator precedence and associativity.
2. Construct the corresponding expression tree based on the postfix expression, where
each internal node represents an operator and each leaf node represents an
operand.
Given: Infix Expression : A + B/C- D*E – F)
Symbol Stack Postfix Remarks
Scanned Expression
A ( A Put in to Expression
+ (+ A ‘+’ PUSH in to STACK
B (+ AB Put in to Expression
/ (+/ AB ‘/’ PUSH in to STACK
C (+/ ABC Put in to Expression
- (- ABC/+ Operator Precedence Resolved
D (- ABC/+D Put in to Expression
* (-* ABC/+D ‘*’ PUSH in to STACK
E (-* ABC/+DE Put in to Expression
- (- ABC/+DE*- Operator Precedence Resolved
F (- ABC/+DE*-F Put in to Expression
) EMPTY ABC/+DE*-F- POP all remaining operators from STACK
Equivalent Postfix Expression: ABC/+DE*-F-

Unit-III : Linear Data Structures-II (Linked List) Page 25 of 34

 SVKMs NMIMS
Mukesh Patel School of Technology Management and Engineering, Shirpur
Course: Data Structures and Algorithms
--------------------------------------------------------------------------------------------------------
Now, using the postfix expression obtained, we proceed to construct its corresponding
expression tree.

Symbol Stack Expression Tree Remarks

Scanned
initially EMPTY NULL --
A A NULL Create
node ‘A’&
PUSH in
Stack
B AB NULL Create
node ‘B’ &
PUSH in
Stack
C ABC Create
node ‘C’&
PUSH in
Stack
/ A/ POP last
two
Nodes,
form a
Tree and
Push Root
in STACK
+ + POP last
two
Nodes,
form a
Tree and
Push Root
in STACK
D +D Create
node ‘D’&
PUSH in
Stack

Unit-III : Linear Data Structures-II (Linked List) Page 26 of 34

 SVKMs NMIMS
Mukesh Patel School of Technology Management and Engineering, Shirpur
Course: Data Structures and Algorithms
--------------------------------------------------------------------------------------------------------
E +DE Create
node ‘E’&
PUSH in
Stack

* +* POP last
two
Nodes,
form a
Tree and
Push Root
in STACK
- - POP last
two
Nodes,
form a
Tree and
Push Root
in STACK

F -F

Unit-III : Linear Data Structures-II (Linked List) Page 27 of 34

 SVKMs NMIMS
Mukesh Patel School of Technology Management and Engineering, Shirpur
Course: Data Structures and Algorithms
--------------------------------------------------------------------------------------------------------
- - POP last
two
Nodes,
form a
Tree and
Push Root
in STACK

EMPTY POP Root

of the
Final
Expression
Tree

4.4.2. Construction of Huffman Tree

Huffman coding is a lossless data compression algorithm that constructs a specialized binary
tree known as a Huffman tree to represent variable-length prefix codes for characters based
on their frequencies. In this tree, leaf nodes represent individual characters or symbols, while
internal nodes represent combined frequencies of their child nodes. The Huffman tree is built
using a greedy approach, where the two least frequent nodes are repeatedly merged to form
a new node until a single tree remains. This hierarchical structure ensures that more frequent
characters receive shorter codes, optimizing the overall compression. Huffman coding is
widely used in file compression formats like ZIP and multimedia standards such as JPEG and
MP3 due to its efficiency and simplicity. However, constructing the Huffman tree requires
prior knowledge of symbol frequencies and can be computationally intensive for large
datasets. Additionally, the need to store the tree or codebook alongside compressed data can
introduce overhead. Despite these limitations, Huffman coding remains a foundational
technique in data compression, offering a clear and structured method for minimizing storage
and transmission costs.

Assume that the following text is required to be send over a stream

“KAAARARA AABRAA DAABRAA”

Each character to be sent requires eight bit of space (One Byte), So the total amount of data
transmitted would be 184 (23 bytes).

Unit-III : Linear Data Structures-II (Linked List) Page 28 of 34

 SVKMs NMIMS
Mukesh Patel School of Technology Management and Engineering, Shirpur
Course: Data Structures and Algorithms
--------------------------------------------------------------------------------------------------------
Character A B R K D Space Total
Length
Frequency 13 2 4 1 1 2 23
Probability 0.56 0.08 0.17 0.04 0.04 0.08 1

Steps for Huffman Tree Construction

STEP 1. Input the Frequencies: Start with a list of characters and their corresponding
frequencies, as shown above.
STEP 2. Create Leaf Nodes: Create a leaf node for each character and insert all nodes into
a priority queue (min-heap) based on frequency. The deletion in (min-heap) returns the
node with lowest value, irrespective of the order of insertions of the elements in the
Heap.

Initial Priority Queue:

D K B Space R A

Each individual node is initially created as a leaf node and inserted into a priority queue
implemented as a Min-Heap. Within this queue, nodes are organized in ascending order
based on their frequency. In cases where multiple nodes share the same frequency, they are
further ordered by the ascending sequence of their labels

STEP 3. Build the Tree :

a. Repeat the following steps until there is only one node left in the priority queue:
i. Extract the two nodes with the lowest frequencies.
ii. Create a new internal node with these two nodes as children.
iii. The frequency of the new node is the sum of the two child nodes.
b. Insert the new node back into the priority queue.

After First Iteration:

Priority Queue:

Unit-III : Linear Data Structures-II (Linked List) Page 29 of 34

 SVKMs NMIMS
Mukesh Patel School of Technology Management and Engineering, Shirpur
Course: Data Structures and Algorithms
--------------------------------------------------------------------------------------------------------

B Space D-K R A

If a newly inserted node, serving as the root of a newly formed subtree—has a frequency
equal to that of existing nodes in the tree, it is placed after all other nodes with the same
frequency, maintaining their original order.

This process of constructing new trees or subtrees is repeated iteratively until only a single
node remains in the priority queue.

After Second Iteration:

Priority Queue:

D-K R B-Space A

After Third Iteration:

Priority Queue:

D-K R B-Space A

After Fourth Iteration:

Unit-III : Linear Data Structures-II (Linked List) Page 30 of 34

 SVKMs NMIMS
Mukesh Patel School of Technology Management and Engineering, Shirpur
Course: Data Structures and Algorithms
--------------------------------------------------------------------------------------------------------

Priority Queue:

B-Space D-K-R A

After Fifth Iteration:

Priority Queue:

B-Space-D- A
K-R

After Fifth Iteration:

Unit-III : Linear Data Structures-II (Linked List) Page 31 of 34

 SVKMs NMIMS
Mukesh Patel School of Technology Management and Engineering, Shirpur
Course: Data Structures and Algorithms
--------------------------------------------------------------------------------------------------------

Priority Queue:

B-Space-D-K-R-A
STEP 4. Final Node is the Root: When only one node remains in the queue, it becomes
the root of the Huffman Tree.
STEP 5.Assign Codes (Optional): Traverse the tree from the root and assign '0' for left
branches and '1' for right branches.

STEP 6.The code for each character is the path from the root to its leaf.

Character Frequency Huffman Code

A 13 1
B 2 000

Unit-III : Linear Data Structures-II (Linked List) Page 32 of 34

 SVKMs NMIMS
Mukesh Patel School of Technology Management and Engineering, Shirpur
Course: Data Structures and Algorithms
--------------------------------------------------------------------------------------------------------
R 4 011
K 1 0101
D 1 0100
Space 2 001

The number of bits required to store this message is calculated as given below:

The total length of the Huffman-coded message "KAAARARA AABRAA DAABRAA", based
on the provided character frequencies and Huffman code is 45 bit, as calculated below.

Character Frequency Huffman Code Bits Used

A 13 1 13*1 = 13
B 2 000 2*3 = 6
R 4 011 4*3 = 12
K 1 0101 1*4 = 4
D 1 0100 1*4 = 4
Space 2 001 2*3 = 6
Total Bits used 45

This demonstrates a significant reduction from the 184 bits required in fixed-length ASCII
encoding.

When encoding the same string using a height-balanced binary tree, each unique character
is assigned a fixed-length binary code based on the total number of distinct characters, as
shown below.

In this case, there are six unique

characters: A, R, space, B, D, and K, to
represent each character uniquely in a
balanced binary tree, we require a code
length of 3 bits, since

⌈log2 (6)⌉=3.

Multiplying the frequency of each

character by this fixed code length, the
total number of bits required to transmit
the entire message becomes 69 bits. This approach ensures uniform code lengths and
simplifies decoding, though it may not be as space-efficient as traditional Huffman coding,
which assigns shorter codes to more frequent characters.

Unit-III : Linear Data Structures-II (Linked List) Page 33 of 34

 SVKMs NMIMS
Mukesh Patel School of Technology Management and Engineering, Shirpur
Course: Data Structures and Algorithms
--------------------------------------------------------------------------------------------------------
Using ASCII encoding, each of the 23 characters (including spaces) is represented using 8 bits,
resulting in a total of 184 bits. In contrast, a height-balanced binary tree encoding assigns a
fixed-length code of 3 bits to each character, based on the 6 unique characters in the message,
reducing the total to 69 bits. It proves that the most efficient method is Huffman encoding,
which assigns variable-length codes based on character frequency. With frequent characters
like 'A' receiving shorter codes and less frequent ones like 'K' and 'D' receiving longer ones,
the total message length is minimized to just 45 bits. This comparison highlights how Huffman
coding significantly optimizes data transmission by leveraging character frequency.

The compression ratios comparing the three encoding methods for the message "KAAARARA
AABRAA DAABRAA":

Huffman coding compresses the same message into just 45 bits.

Comparison of Huffman Coding vs ASCII

ASCII encoding uses 184 bits to represent the message.

 Compression Ratio (How much size is reduced):

Huffman coding reduces the size by 75.54% compared to ASCII.
(Calculated as: (1 - 45 / 184) × 100)
 Compressed Size as a Percentage of Original:
Huffman coding uses only 24.46% of the original size.
(Calculated as: (45 / 184) × 100)

Comparison of Huffman Coding vs Height-Balanced Tree Coding

Height-Balanced Tree coding uses 69 bits to represent the message.

 Compression Ratio (How much size is reduced):

Huffman coding reduces the size by 34.78% compared to Height-Balanced Tree
coding.
(Calculated as: (1 - 45 / 69) × 100)
 Compressed Size as a Percentage of Height-Balanced Tree Size:
Huffman coding uses 65.22% of the size used by Height-Balanced Tree coding.
(Calculated as: (45 / 69) × 100).

Unit-III : Linear Data Structures-II (Linked List) Page 34 of 34