1. Define Queue data structure.
Write an Algorithm for a queue to perform the following task based on the
given figure.
Definition:
A Queue is a linear data structure that follows the FIFO (First In First Out) principle. The element inserted first
is removed first. Common operations include enqueue (insert) and dequeue (remove).
Basic Queue Operations Algorithm (for array implementation):
Initialize: front = -1, rear = -1, size = N, queue = []
Enqueue(Q, item):
if rear == size - 1:
print "Queue Overflow"
else:
if front == -1:
front = 0
rear = rear + 1
Q[rear] = item
Dequeue(Q):
if front == -1 or front > rear:
print "Queue Underflow"
else:
item = Q[front]
front = front + 1
return item
2. Define Binary Tree. What is the difference between a full binary tree and a complete binary tree? Explain
pre-order tree traversal with an example.
Definition:
A Binary Tree is a hierarchical structure in which each node has at most two children: left and right.
Differences:
Full Binary Tree: Each node has 0 or 2 children.
Complete Binary Tree: All levels are filled except possibly the last. Nodes in the last level are filled left to
right.
Pre-order Traversal (Root-Left-Right):
Example Tree:
/\
B C
/\
D E
Pre-order traversal: A, B, D, E, C
3. What do you mean by tree traversal? Perform in-order, pre-order, and post-order traversals from the given
Binary Tree.
Definition:
Tree Traversal refers to the process of visiting each node in a tree exactly once in a specific order.
Types of Traversals:
- In-order (Left, Root, Right)
- Pre-order (Root, Left, Right)
- Post-order (Left, Right, Root)
4. Construct a Binary Tree from Pre-order and In-order Tree Traversals.
Given:
Pre-order: 1,2,4,8,9,10,11,5,3,6,7
In-order: 8,4,10,9,11,2,5,1,6,3,7
Algorithm:
1. Take the first element from pre-order (1) as root.
2. Locate it in in-order array; left part is left subtree, right part is right subtree.
3. Recursively build left and right subtrees.
5. Write a recursive algorithm for pre-order binary tree traversal.
def preorder(node):
if node is not None:
print(node.data) # Visit root
preorder(node.left) # Traverse left
preorder(node.right) # Traverse right
6. Write an algorithm to insert a node in the Binary Tree based on the given diagram.
def insert(root, key):
if root is None:
return Node(key)
queue = []
queue.append(root)
while queue:
temp = queue.pop(0)
if not temp.left:
temp.left = Node(key)
break
else:
queue.append(temp.left)
if not temp.right:
temp.right = Node(key)
break
else:
queue.append(temp.right)
7. Why do we need AVL tree? Explain the conditions for an AVL tree. How is a tree converted into AVL?
Explain any one method with an example.
Need for AVL Tree:
To maintain balance in a binary search tree. Unbalanced trees lead to O(n) time complexity.
Conditions:
An AVL tree is a self-balancing BST where the balance factor (height of left subtree - right subtree) is
between -1 and 1 for every node.
Conversion / Rotation Example:
Right Rotation (LL Rotation):
Unbalanced at left-left case:
Right rotate at C:
/\
A C
8. What is Graph in data structure? Write an algorithm to construct a given graph using adjacency matrix.
Definition:
A Graph is a collection of nodes (vertices) connected by edges. It can be directed or undirected, weighted or
unweighted.
Adjacency Matrix Algorithm:
def create_adj_matrix(vertices, edges):
matrix = [[0]*vertices for _ in range(vertices)]
for (u, v) in edges:
matrix[u][v] = 1
matrix[v][u] = 1 # if undirected
return matrix
9. Explain the DFS algorithm based on the following undirected graph.
DFS (Depth First Search):
A graph traversal technique that explores as far as possible along each branch before backtracking.
Algorithm:
def DFS(graph, start, visited=None):
if visited is None:
visited = set()
visited.add(start)
print(start)
for neighbor in graph[start]:
if neighbor not in visited:
DFS(graph, neighbor, visited)
