1.

Write short notes on:-

i. Binomial heaps
A Binomial Heap is a set of Binomial Trees where each Binomial
Tree follows the Min Heap property. And there can be at most
one Binomial Tree of any degree.
Examples Binomial Heap:

A Binomial Heap with 12 nodes. It is a collection of 2

Binomial Trees of orders 2 and 3 from left to right.
ii. Fibonacci heaps
Fibonacci Heap is a collection of trees with min-heap or max-
heap property. In Fibonacci Heap, trees can have any shape
even all trees can be single nodes (This is unlike Binomial Heap
where every tree has to be Binomial Tree).
 2. Explain the tree traversal techniques with an example.

3 .Construct an expression tree for the expression (a+b*c) +

((d*e+f)*g). Give the outputs when you apply inorder,
preorder and postorder traversals.
 4. How to insert and delete an element into a binary
search tree and write down the code for the insertion
routine with an example.
 Allocate the memory for tree.
 Set the data part to the value and set the left and right pointer
of tree, point to NULL.
 If the item to be inserted, will be the first element of the tree,
then the left and right of this node will point to NULL.
 Else, check if the item is less than the root element of the
tree, if this is true, then recursively perform this operation
with the left of the root.
 If this is false, then perform this operation recursively with the
right sub-tree of the root.

Insert (TREE, ITEM)

o Step 2: END
C Function
1. #include<stdio.h>
2. #include<stdlib.h>
3. void insert(int);
4. struct node
5. {
6. int data;
7. struct node *left;
8. struct node *right;
9. };
10. struct node *root;
11. void main ()
12. {
13. int choice,item;
14. do
15. {
16. printf("\nEnter the item which you want to insert?\n");
17. scanf("%d",&item);
18. insert(item);
19. printf("\nPress 0 to insert more ?\n");
20. scanf("%d",&choice);
21. }while(choice == 0);
22. }
23. void insert(int item)
24. {
25. struct node *ptr, *parentptr , *nodeptr;
26. ptr = (struct node *) malloc(sizeof (struct node));
27. if(ptr == NULL)
28. {
29. printf("can't insert");
30. }
31. else
32. {
33. ptr -> data = item;
34. ptr -> left = NULL;
35. ptr -> right = NULL;
36. if(root == NULL)
37. {
38. root = ptr;
39. root -> left = NULL;
40. root -> right = NULL;
41. }
42. else
43. {
44. parentptr = NULL;
45. nodeptr = root;
46. while(nodeptr != NULL)
47. {
48. parentptr = nodeptr;
49. if(item < nodeptr->data)
50. {
51. nodeptr = nodeptr -> left;
52. }
53. else
54. {
55. nodeptr = nodeptr -> right;
56. }
57. }
58. if(item < parentptr -> data)
59. {
60. parentptr -> left = ptr;
 61. }
62. else
63. {
64. parentptr -> right = ptr;
65. }
66. }
67. printf("Node Inserted");
68. }
69. }

Output

Enter the item which you want to insert?

12
Node Inserted
Press 0 to insert more ?
0

Enter the item which you want to insert?

23
Node Inserted
Press 0 to insert more ?
1
 5. What are threaded binary tree? Write an algorithm for
inserting a node in a threaded binary tree.
The idea of threaded binary trees is to make inorder traversal faster
and do it without stack and without recursion. A binary tree is made
threaded by making all right child pointers that would normally be
NULL point to the inorder successor of the node (if it exists).
tmp -> left = par;
tmp -> right = par -> right;
Before insertion, the right pointer of parent was a thread, but after insertion it
will be a link pointing to the new node.
par -> rthread = false;
par -> right = tmp;
Following example shows a node being inserted as right child of its parent.

(GRAPHS )
 1. Explain Shortest Path algorithm: Dijikstra Algorithm.
an algorithm that is used for finding the shortest
distance, or path, from starting node to target node
in a weighted graph is known as Dijkstra’s Algorithm.
This algorithm makes a tree of the shortest path from the
starting node, the source, to all other nodes (points) in the
graph.
Dijkstra's algorithm makes use of weights of the edges for
finding the path that minimizes the total distance (weight)
among the source node and all other nodes. This algorithm
is also known as the single-source shortest path algorithm.
2. a) Explain prims algorithm along with its implementation
Prim's Algorithm is a greedy algorithm that is used to find the
minimum spanning tree from a graph. Prim's algorithm finds the
subset of edges that includes every vertex of the graph such that
the sum of the weights of the edges can be minimized.

Prim's algorithm starts with the single node and explores all the
adjacent nodes with all the connecting edges at every step. The
edges with the minimal weights causing no cycles in the graph got
selected.

Prim's algorithm is a greedy algorithm that starts from one vertex and
continue to add the edges with the smallest weight until the goal is
reached. The steps to implement the prim's algorithm are given as follows
-

o First, we have to initialize an MST with the randomly chosen vertex.

o Now, we have to find all the edges that connect the tree in the
above step with the new vertices. From the edges found, select the
minimum edge and add it to the tree.
o Repeat step 2 until the minimum spanning tree is formed.

b) Construct the minimum spanning tree (MST) for the

given graph using prims algorithm
Since all the vertices have been included in the MST, so we stop.

Now, Cost of Minimum Spanning Tree

= Sum of all edge weights
= 10 + 25 + 22 + 12 + 16 + 14
= 99 units

3. a) Explain Prims Algorithm along with its implementation.

Same as 2[a]
b) Using Prim’s Algorithm, find the cost of minimum
spanning tree (MST) of the given graph

4. a)Explain Kruskal algorithm along with its implementation.

Kruskal's Algorithm is used to find the minimum spanning tree for a
connected weighted graph. The main target of the algorithm is to find the
subset of edges by using which we can traverse every vertex of the graph.
It follows the greedy approach that finds an optimum solution at every
stage instead of focusing on a global optimum.
In Kruskal's algorithm, we start from edges with the lowest weight and
keep adding the edges until the goal is reached. The steps to implement
Kruskal's algorithm are listed as follows -

o First, sort all the edges from low weight to high.

o Now, take the edge with the lowest weight and add it to the
spanning tree. If the edge to be added creates a cycle, then reject
the edge.
o Continue to add the edges until we reach all vertices, and a
minimum spanning tree is created.

b)Construct the minimum spanning tree (MST) for the given graph using Kruskal’s Algorithm.
 5 MARKS QUESTIONS

1. Explain the logic behind using “Threaded binary tree” in Data Structures. Draw a labelled
diagram to show working of threaded binary tree.

In the linked representation of binary trees, more than one half of the
link fields contain NULL values which results in wastage of storage
space. If a binary tree consists of n nodes then n+1 link fields contain
NULL values. So in order to effectively manage the space, a method
was devised by Perlis and Thornton in which the NULL links are
replaced with special links known as threads. Such binary trees with
threads are known as threaded binary trees. Each node in a
threaded binary tree either contains a link to its child node or thread to
other nodes in the tree.
2. Describe Binary Tree along with its representation. How will you search an element in
Binary Tree. Explain.

A binary tree is a non-linear data structure of the tree type that has a
maximum of two children for every parent node. The node at the top
of the entire binary tree is called the root node. In any binary tree,
every node has a left reference, right reference, and data element.

searching for some specific node in binary search tree is pretty easy
due to the fact that, element in BST are stored in a particular order.

3. The Inorder and Preorder Traversal of a Tree are given below:-

INORDER: DBMINEAFCJGK

PREORDER: ABDEIMNCGJK

i) Construct the corresponding Binary Tree.

ii) Determine Post order Traversal of the Tree drawn.

4. Explain the following:-

 i) Binary Tree & Binary Search Tree

ii) Complete Binary Tree

A complete binary tree is a binary tree in which all the levels are completely
filled except possibly the lowest one, which is filled from the left.

A complete binary tree is just like a full binary tree, but with two major
differences

1. All the leaf elements must lean towards the left.

2. The last leaf element might not have a right sibling i.e. a complete
binary tree doesn't have to be a full binary tree.
 UNIT-4
1. Write Kruskal’s Algorithm for finding Minimum
Spanning Tree.

2. Outline the distinguishing features of Depth First

Search (DFS) and Breadth First Search (BFS) in context
of graphs.
3. Explain Adjacency Matrix with the help of suitable
diagram.

4. How will you detect a cycle in a Directed as well as

Undirected graph. Explain with help of an example.
2 MARKS QUESTIONS
 UNIT 3
1. What are various representation of Binary Tree.

2. Write Advantages of Threaded Binary Tree.

In threaded binary tree, linear and fast traversal of nodes in the tree so
there is no requirement of stack. ...
It is more general as one can efficiently determine the successor and
predecessor of any node by simply following the thread and links.

3. Define Leaf.

4. What is Ordered Tree.

An ordered tree is an oriented tree in which the children of a

node are somehow ordered. It is a rooted tree in which an
ordering is specified for the children of each vertex. This is
called a “plane tree” because the ordering of the children is
equivalent to an embedding of the tree in the plane, with the root
at the top and the children of each vertex lower than that vertex.
 The ordered trees can be further specified as labelled ordered
trees and unlabelled ordered trees.
2 MARKS QUESTIONS
UNIT-4
1. Define Graph. List Any 3 application area of Graph

1. Computer Science
o Graphs are used to define the flow of computation.
o Graphs are used to represent networks of communication.
o Graphs are used to represent data organization.
o Graph transformation systems work on rule-based in-memory
manipulation of graphs.

2. Electrical Engineering
In Electrical Engineering, graph theory is used in designing of
circuit connections. These circuit connections are named as
topologies. Some topologies are series, bridge, star and parallel
topologies.

3. Linguistics
o In linguistics, graphs are mostly used for parsing of a language
tree and grammar of a language tree.
o Semantics networks are used within lexical semantics, especially
as applied to computers, modeling word meaning is easier when a
given word is understood in terms of related words.
o Methods in phonology (e.g. theory of optimality, which uses lattice
graphs) and morphology (e.g. morphology of finite - state, using
finite-state transducers) are common in the analysis of language as
a graph.

2. Define OutDegree of Graph

The number of edges going out of a vertex in a directed graph.

3. Define Undirected Graph

4. Define Adjacent Nodes

Adjacency − Two node or vertices are adjacent if they are
connected to each other through an edge. In the following example,
B is adjacent to A, C is adjacent to B, and so on.