Module III: TREES: (10 Hours)

Trees – definition, terminology, Binary trees-definition, Properties of BinaryTrees, Binary Tree ADT,
representation of Binary Trees-array and linked

representations, Binary Tree traversals, Threaded binary trees.

Priority Queues–Definition and applications, Max Priority Queue ADT- implementation-Max Heap-
Definition, Insertion into a Max Heap, Deletion from a Max Heap.

Minimum Spanning Tree: Prim’s and Kruskal’s Algorithm, Shortest Path

Algorithms.
Definition:

A tree is a non-linear data structure that represents a hierarchical relationship among elements
(called nodes).
It consists of nodes connected by edges.

 The topmost node is called the root.

 Each node may have zero or more child nodes.

 Nodes having the same parent are called siblings.

 Nodes with no children are called leaf nodes or terminal nodes.

 Nodes having at least one child are called internal nodes.

Example:

 Root: A
 Children of A: B, C
 Siblings: B and C, D and E
 Leaf Nodes: D, E, F
 Internal Nodes: A, B, C
 Tree - Terminology
 In linear data structure data is organized in sequential order and in
non-linear data structure data is organized in random order. Tree is
a very popular non-linear data structure used in wide range of
applications. A tree data structure can be defined as follows...

 DEF:Tree is a non linear data structure which organizes the data in a

hierarchical manner.

 Key properties of Tree:

 A tree T is represented by nodes and edges, which includes:

1. T is empty (called null or empty tree).

2. T has a left subtree and right subtree.
Terminology:

 Root:-In a tree data structure, the first node is called as Root

Node. Every tree must have root node. We can say that root node is
the origin of tree data structure. In any tree, there must be only one
root node. We never have multiple root nodes in a tree.
Example:

Edge :- Connecting link between any two nodes is called as EDGE. In a tree with ‘N’ number
of nodes there will be a maximum of ‘N-1’ number of edges.

Parent :- Node which is predecessor of any node is called as PARENT NODE i.e. node which
has branch from it to any other node is called as parent node. In the above figure node B is the
parent node of E, F, and G node and E, F, and G are called children of B.

Child :- Node which is descendant of any node is called as CHILD Node. In simple words, the
node which has a link from its parent node is called as child node.

Siblings :- Nodes which belong to same Parent are called as SIBLINGS. In simple words, the
nodes with same parent are called as Sibling nodes. Children of same parent are called Sibling.

Leaf :- Node which does not have a child is called as LEAF Node. In simple words, a leaf is a
node with no child. In the figure E,F,C,G,C,H are the leaf nodes
Level :- Root node is said to be at Level 0 and the children of 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 the above figure,
the node A is at level 0, the node B, C, Dare at level 1, the nodes E, F, G, H are at level 2.

Tree Height :- Number of edges in the longest path from the root to the leaf node.
the height of the tree is 3

Predecessor:-While displaying the tree, if some particular nodes previous to some other nodes
than that node is called the predecessor of the other node. In our example, the node E is
predecessor of node B.

Successor:-The node which occurs next to some other node is called successor of that node. In
our example, B is successor of F and G.

Internal Nodes:-The nodes in the tree which are other than leaf nodes and the root node are
called as internal nodes. These nodes are present in between root node and leaf nodes in the tree
that’s why these nodes are called as internal node. Here, B and D are internal nodes.

Degree of tree :-The maximum degree of the node in the tree is called the degree of the tree.
Here, the degree of tree is 3.

Binary tree
A binary tree is a finite set of nodes that is either empty or consist a root node and two disjoint
binary trees called the left subtree and the right subtree.
In other words, a binary tree is a non-linear data structure in which each node has maximum of
two child nodes. The tree connections can be called as branches
A binary tree is a special case of an ordered tree, where k is 2.
Example:

1) Complete Binary Tree

A binary tree T is said to be complete binary tree if -
1. All its levels, except possibly except possibly the last, have the maximum number of nodes and
2. All the nodes at the last level appears as far left as possible.

2) Strictly Binary Tree

When every non leaf node in a binary tree is filled with left and right subtrees, the tree is called
a strictly binary tree.
3) Extended Binary Tree

The binary tree that is extended with zero (no nodes) or left or right node or both the nodes is
called an extended binary tree or a 2- tree.
The extended binary tree is shown in figure above. The extended nodes are indicated by square
box. Maximum nodes in the binary tree have one child (nodes) shown at either left or right by
adding one or more children, the tree can be extended. The extended binary tree is very useful
for representation of algebraic expressions. The left and right child nodes denote operands and
parent node indicates operator.

4) Full Binary Tree

A Binary Tree is full binary tree if and only if -
1. Each non- leaf node has exactly two child nodes.
2. All leaf nodes are at the same level.

Properties of Binary trees

1) The maximum number of nodes at level ‘l’ of a binary tree is 2l-1.
2) Maximum number of nodes in a binary tree of height ‘h’ is 2h – 1.
3) In a Binary Tree with N nodes, minimum possible height or minimum number of levels is ⌈
Log2(N+1) ⌉
4) A Binary Tree with L leaves has at least ⌈ Log2L ⌉ + 1 levels
5) In Binary tree where every node has 0 or 2 children, number of leaf nodes is always one more
than nodes with two children.
Representation of Binary Trees
Let T be a Binary Tree. There are two ways of representing T in the memory as follow:
1. Sequential Representation of Binary Tree.

2. Link Representation of Binary Tree.

1) Linked Representation of Binary Tree
Consider a Binary Tree T. T will be maintained in memory by means of a linked list
representation which uses three parallel arrays; INFO, LEFT, and RIGHT pointer
variable ROOT as follows. In Binary Tree each node N of Twill correspond to a location k such
that
• LEFT [k] contains the location of the left child of node N.
• INFO [k] contains the data at the node N.
• RIGHT [k] contains the location of right child of node N.
Representation of a node:

In this representation of binary tree root will contain the location of the root R of T. If any one
of the subtree is empty, then the corresponding pointer will contain the null value if the
tree T itself is empty, the ROOT will contain the null value.
Example:
Consider the binary tree T in the figure. A schematic diagram of the linked list representation
of T appears in the following figure. Observe that each node is pictured with its three fields, and
that the empty subtree is pictured by using x for null entries.
Binary Tree
Linked Representation of the Binary Tree

2) Sequential representation of Binary Tree

Let us consider that we have a tree T. let our tree T is a binary tree that us complete binary tree.
Then there is an efficient way of representing T in the memory called the sequential
representation or array representation of T. This representation uses only a linear array TREE as
follows:
• The root N of T is stored in TREE [1].
• If a node occupies TREE [k] then its left child is stored in TREE [2 * k] and its right
child is stored into TREE [2 * k + 1].
For Example:
Consider the following Tree:
Its sequential representation is as follows

Binary Tree traversals

Tree traversal is the process of visiting each node in the tree exactly once. Visiting each node
in a graph should be done in a systematic manner. If search result in a visit to all the vertices, it
is called a traversal. There are basically three traversal techniques for a binary tree that are,
• Preorder traversal
• Inorder traversal
• Postorder traversal
1) Preorder traversal
To traverse a binary tree in preorder, following operations are carried out:
1. Visit the root.
2. Traverse the left sub tree of root.
3. Traverse the right sub tree of root.
Note: Preorder traversal is also known as NLR traversal.
Algorithm:
Algorithm preorder(t)
/*t is a binary tree. Each node of t has three fields:
lchild, data, and rchild.*/
{
If t! =0 then
{
Visit(t);
Preorder(t->lchild);
Preorder(t->rchild);
}
}
Example: Let us consider the given binary tree,

Therefore, the preorder traversal of the above tree will be: 7,1,0,3,2,5,4,6,9,8,10
2) Inorder traversal
To traverse a binary tree in inorder traversal, following operations are carried out:
1. Traverse the left most sub tree.
2. Visit the root.
3. Traverse the right most sub tree.
Note: Inorder traversal is also known as LNR traversal.
Algorithm:
Algorithm inorder(t)
/*t is a binary tree. Each node of t has three fields:
lchild, data, and rchild.*/
{
If t! =0 then
{
Inorder(t->lchild);
Visit(t);
Inorder(t->rchild);
}
}
Example: Let us consider a given binary tree.

Therefore the inorder traversal of above tree will be: 0,1,2,3,4,5,6,7,8,9,10

3) Postorder traversal
To traverse a binary tree in postorder traversal, following operations are carried out:
1. Traverse the left sub tree of root.
2. Traverse the right sub tree of root.
3. Visit the root.
Note: Postorder traversal is also known as LRN traversal.
Algorithm:
Algorithm postorder(t)
/*t is a binary tree .Each node of t has three fields:
lchild, data, and rchild.*/
{
If t! =0 then
{
Postorder(t->lchild);
Postorder(t->rchild);
Visit(t);
}
}
Example: Let us consider a given binary tree.

Therefore the postorder traversal of the above tree will be: 0,2,4,6,5,3,1,8,10,9,7

Threaded Binary Tree

A binary tree can be represented by using array representation or linked list representation.
When a binary tree is represented using linked list representation. If any node is not having a
child we use a NULL pointer. These special pointers are threaded and the binary tree having
such pointers is called a threaded binary tree. Thread in a binary tree is represented by a dotted
line. In linked list representation of a binary tree, they are a number of a NULL pointer than
actual pointers. This NULL pointer does not play any role except indicating there is no child.
The threaded binary tree is proposed by A.J Perlis and C Thornton. There are three ways to
thread a binary tree.

1. In the in order traversal When The right NULL pointer of each leaf node can be replaced by a
thread to the successor of that node then it is called a right thread, and the resultant tree called a
right threaded tree or right threaded binary tree.

2. When The left NULL pointer of each node can be replaced by a thread to the predecessor of that
node under in order traversal it is called left thread and the resultant tree will call a left threaded
tree.
3. In the in order traversal, the left and the right NULL pointer can be used to point to predecessor
and successor of that node respectively. then the resultant tree is called a fully threaded tree.
In the threaded binary tree when there is only one thread is used then it is called as one way
threaded tree and when both the threads are used then it is called the two way threaded tree. The
pointer point to the root node when If there is no in-order predecessor or in-order successor.
Consider the following binary tree:

The in-order traversal of a given tree is

given tree is shown below:
Advantages of Thread Binary Tree
Non-recursive pre-order, in-order and post
Disadvantages of Thread Binary Tree
1. Insertion and deletion operation becomes more difficult.
2. Tree traversal algorithm becomes difficult.
3. Memory required to store a node increases. Each node has to store the information whether the
links is normal links or threaded links.
Types of Threaded of Binary Tree
There are three types of Threaded Binary Tree,
1) Right Threaded Binary Tree
Right threaded binary tree for a given tree is shown:
2) Left Threaded Binary Tree
Left threaded binary tree for a given tree is shown:

3) Fully Threaded Binary Tree

Fully threaded binary tree for a given tree is shown
PRIORITY QUEUE
Def: Priority queue is a variant of queue data structure in which insertion is performed in the
order of arrival and deletion is performed based on the priority.
In priority queue every element is associated with some priority. Normally the
priorities are specified using numerical values. In some cases lower values indicate high priority
and in some cases higher values indicate high priority. In priority queues elements are processed
according to their priority but not according to the order they are entered into the queue.

Ex: let P be a priority queue with three elements a, b, c whose priority factors are 2,1,1
respectively. Here, larger the number, higher is the priority accorded to that element. When a
new element d with higher priority 4 is inserted, d joins at the head of the queue
superseding the remaining elements. When elements in the queue have the same priority,
then the priority queue behaves as an ordinary queue following the principle of FIFO amongst
shown:
: [Link] priority queues elements are processed
order they are entered into the queue.
is inserted, d joins at the head of the queue
hey 2,1,1
s
such elements.

The working of a priority queue may be likened to a situation when a file of patients
waits for their turn in a queue to have an appointment with a doctor.
equal priority and follow an FCFS scheme by appointments. Howeve
bleeding injuries is brought in, he/she is accorded higher priority and i
the head of the queue for immediate attention by the doctor. This is priority queue at work.
There are two types of priority queues they are as follows...
1. Max Priority Queue
2. Min Priority Queue
Max Heap Data structure
Heap data structure is a specialized binary tree based data structure. Heap is a binary tree with
special characteristics. In a heap data structure, nodes are arranged based on thier values. A
heap data structure some times also called as Binary Heap.
There are two types of heap data structures and they are as follows...
1. Max Heap
2. Min Heap
Every heap data structure has the following properties...
Property #1 (Ordering): Nodes must be arranged in an order according to their values based
on Max heap or Min heap.
Property #2 (Structural): All levels in a heap must be full except the last level and all nodes
must be filled from left to right strictly.
Max Heap
Max heap data structure is a specialized full binary tree data structure. In a max heap nodes are
arranged based on node value.
Example:
Above tree is satisfying both Ordering property and Structural property according to the Max
Heap data structure.
Operations on Max Heap
The following operations are performed on a Max heap data structure...
1. Finding Maximum
2. Insertion
3. Deletion

Finding Maximum Value Operation in Max Heap

Finding the node which has maximum value in a max heap is very simple. In max heap, the root
node has the maximum value than all other nodes. So, directly we can display root node value
as maximum value in max heap.
Insertion Operation in Max Heap
Insertion Operation in max heap is performed as follows...
• Step 1 - Insert the newNode as last leaf from left to right.
• Step 2 - Compare newNode value with its Parent node.
• Step 3 - If newNode value is greater than its parent, then swap both of them.
• Step 4 - Repeat step 2 and step 3 until newNode value is less than its parent node (or) newNode
reaches to root.
Example
Consider the above max heap. Insert a new node with value 85.
• Step 1 - Insert the newNode with value 85 as last leaf from left to right. That means newNode
is added as a right child of node with value 75. After adding max heap is as follows...

• Step 2 - Compare newNode value (85) with its Parent node value (75). That means 85 > 75.

 Step 3 - Here newNode value (85) is greater than its parent value (75), then swap both of
them. After swapping, max heap is as follows...
Step 4 - Now, again compare newNode value (85) with its parent node value (89).

Here, newNode value (85) is smaller than its parent node value (89). So, we stop insertion
process. Finally, max heap after insertion of a new node with value 85 is as follows...
Deletion Operation in Max Heap
In a max heap, deleting last node is very simple as it does not disturb max heap properties.
Deleting root node from a max heap is little difficult as it disturbs the max heap properties. We
use the following steps to delete root node from a max heap...
• Step 1 - Swap the root node with last node in max heap.
• Step 2 - Delete last node.
• Step 3 - Now, compare root value with its left child value.
• Step 4 - If root value is smaller than its left child, then compare left child with its right sibling. Else
goto Step 6
• Step 5 - If left child value is larger than its right sibling, then swap root with left child otherwise
swap root with its right child.
• Step 6 - If root value is larger than its left child, then compare root value with its right child value.
• Step 7 - If root value is smaller than its right child, then swap root with right child otherwise stop
the process
• Step 8 - Repeat the same until root node fixes at its exact position.
Example
Consider the above max heap. Delete root node (90) from the max heap.
• Step 1 - Swap the root node (90) with last node 75 in max heap. After swapping max heap is
as follows...
 Step 2 - Delete last node. Here the last node is 90. After deleting node with value 90 from
heap, max heap is as follows...

• Step 3 - Compare root node (75) with its left child (89).
Here, root value (75) is smaller than its left child value (89). So, compare left child (89)
with its right sibling (70).

• Step 4 - Here, left child value (89) is larger than its right sibling (70), so swap root with its
left child (89).
Step 5 - Now, again compare 75 with its left child (36).

Here, node with value 75 is larger than its left child. So, we compare node 75 with its right
child 85.
Step 6 - Here, node with value 75 is smaller than its right child (85). So, we swap both of
them.
After swapping max heap is as follows...

• Step 7 - Now, compare node with value 75 with the left child (15).
 Here, node with value 75 is larger than its left child (15) and it does not have right child. So
we stop the process. Finally, max heap after deleting root node (90) is as follows...

Minimum Spanning Tree:

Definition

A spanning tree of a connected, undirected, weighted graph is a subgraph that:

 Includes all vertices of the original graph.

 Is connected (there’s a path between every pair of vertices).

 Has no cycles.

If there are weights (costs) on the edges, then among all possible spanning trees,
the one with the minimum total weight is called the Minimum Spanning Tree (MST).

Properties of MST

1. MST of a graph with V vertices has exactly (V – 1) edges.

2. The MST is unique if all edge weights are distinct.

3. Removing any edge from MST makes it disconnected.

4. Adding any edge to MST creates a cycle.

5. MST is not unique if multiple edges have the same weight.

Applications of MST

 Designing communication networks (telephone, computer, electrical).

 Used in approximation algorithms for NP-hard problems.

 Clustering in machine learning.

  Road/pipe network optimization.

🔹 Example Graph

Possible MST (using Prim or Kruskal):

Edges: A–B(1), B–D(2), A–C(3)
Total Cost = 6

. Kruskal’s Algorithm

Definition

Kruskal’s Algorithm is a greedy algorithm that builds the MST by

selecting edges in increasing order of weight, ensuring that no cycles are formed.

Algorithm Steps

1. Sort all edges in non-decreasing order of their weights.

2. Initialize the MST as empty.

3. For each edge (u, v) in sorted order:

o If adding (u, v) does not form a cycle, include it in MST.

o Otherwise, skip it.

4. Repeat until MST has (V – 1) edges.

Example

Graph edges:
 Edge Weight

A–B 1

B–C 2

C–D 3

A–C 4

B–D 5

Steps:

 Pick A–B → add

 Pick B–C → add

 Pick C–D → add

(MST complete → 3 edges for 4 vertices)

MST Edges: A–B, B–C, C–D

Total Weight = 6

Pseudo Code:

Prim’s Algorithm

Definition

Prim’s Algorithm is also a greedy algorithm for finding an MST.

It starts from any vertex and grows the MST by adding the smallest edge
that connects a vertex inside the MST to a vertex outside the MST.

Algorithm Steps

1. Start with any vertex (say A).

2. Choose the minimum weight edge from A connecting to any other vertex.
3. Add that vertex to the tree.

4. From all edges connecting MST to new vertices, pick the smallest edge.

5. Repeat until all vertices are included.

Example

Graph:

Edge Weight

A–B 1

B–C 2

C–D 3

A–C 4

Steps:

 Start from A.

 Pick A–B (1).

 Pick B–C (2).

 Pick C–D (3).

MST Edges: A–B, B–C, C–D

Total Weight = 6

Pseudo Code:

Difference between Prim’s and Kruskal’s Algorithms

 Feature Prim’s Kruskal’s

Approach Grows tree from a starting Adds edges in sorted

vertex order

Basis Vertex-based Edge-based

Graph Type Dense graphs Sparse graphs

Cycle Not needed Required (Union-Find)

Detection

Complexity O(E log V) O(E log V)

Shortest Path Algorithms

(A) Dijkstra’s Algorithm

Definition:

Dijkstra’s Algorithm is used to find the shortest path from a single source vertex to all other vertices
in a weighted graph with non-negative edge weights.

Steps

1. Set the distance of the source vertex = 0, and all others = ∞.

2. Mark all vertices unvisited.

3. Select the unvisited vertex with the smallest distance (initially source).

4. For each of its neighbors, update the distance if a shorter path is found.

5. Mark the vertex as visited.

6. Repeat until all vertices are visited.

Example

Graph:
Source = A

Vertex Shortest Distance Path

A 0 A

B 2 A–B

C 3 A–B–C

D 6 A–B–C–D

Result: Shortest paths from A to all vertices found.

Pseudo Code:

(B) Bellman–Ford Algorithm

Definition

Bellman–Ford Algorithm also finds the shortest path from a single source to all other vertices,
and can handle negative edge weights (unlike Dijkstra).

Steps

1. Initialize distances: dist[source] = 0, others = ∞.

2. Repeat (V – 1) times:
For every edge (u, v) with weight w,
If dist[v] > dist[u] + w, update dist[v] = dist[u] + w.

3. Check for negative weight cycle:

If any edge still gives a smaller distance, then a negative cycle exists.
 4. Comparison of Dijkstra and Bellman–Ford

Feature Dijkstra Bellman–Ford

Edge Weights Only non-negative Can be negative

Approach Greedy Dynamic Programming

Detect Negative Cycles No Yes

Complexity O(E log V) O(VE)