Assignment # 3

Submitted by:

Name Registration No.

Eman Fatima SP24-BAI-015

Submitted to: Sir Atique Ahmad Zafar

Subject: Data Structures

Dated: May 26,2025

 Topic: Tree and Graph
Question 1:
Algorithm:
Insertion:
1. Define node Structure.
2. Create a new node with given id and name. Set left and right child to NULL.
3. If the root is NULL, make the new node the root.
4. Else, start from the root and search for the correct position:
• Traverse left if id < current node’s ID
• Traverse right if id > current node’s ID
• If a node with the same id exists, do not insert (avoid duplicates).
5. Insert the new node as the left or right child of the appropriate parent.
Total Node Function:
1. If root is NULL, return 0.
2. Else, return:
1 + totalNodes(left subtree) + totalNodes(right subtree)
Height Function:
1. If root is NULL, return 0.
2. Else, recursively find:
1 + max(height(left subtree), height(right subtree))
Traversal Functions:
1) Inorder:
1. Traverse left subtree
2. Visit root (print employee details)
3. Traverse right subtree
2) Preorder:
1. Visit root
2. Traverse left subtree
3. Traverse right subtree
3) Postorder:
1. Traverse left subtree
2. Traverse right subtree
3. Visit root

----------------------------------------
Question 2:
Algorithm:
1. Create a function to insert values in BST.
2. Create a function to traverse the tree inorderly and push values to queue.
3. Create a function to convert BST to doubly Linked List.
I. Call inorder(root) to fill the queue.
II. While the queue is not empty:
• Dequeue the front node.
• If DLL is empty:
o Set head and tail to the node.

• Else:
o Attach the node to the tail->right
o Set node->left = tail
o Update tail = node
4. Create a function to display Linked List in forward and reverse direction.
----------------------------------------
Question 3:
Algorithm:
1. Create a function to insert values in BST.
2. Create a function to traverse the tree and find sum of odd and even level:
a. If root is NULL, print Difference: 0 and return.
b. Initialize:
• odd = 0 for odd level sum
• even = 0 for even level sum
• level = 1
c. Use a queue to perform level-order traversal:
• Push root into the queue.
d. While the queue is not empty:
• Get number of nodes in the current level → levelSize
• Initialize levelSum = 0
• For each node at this level:
o Dequeue it
o Add its value to levelSum
o Push its left and right children to the queue (if they exist)
• If level is odd, add levelSum to odd
 • If level is even, add levelSum to even
• Increment level by 1
3. Compute the difference.
4. Print Result.
----------------------------------------
Question 4:
Algorithm:
Insertion:
1. Create function to find height, balance of tree and to rotate tree.
2. Create a function to insert values in AVL tree.
a. If root is NULL:
• Create a new node with the given ID.
b. If ID is less, insert in left subtree.
c. If ID is more, insert in right subtree.
d. Update height of current node.
e. Check balance factor.
f. Apply appropriate rotation based on balance:
• LL → Right Rotate
• RR → Left Rotate
• LR → Left Rotate child, then Right Rotate
• RL → Right Rotate child, then Left Rotate
g. Return the root.
Search:
1. Create a function for searching.
• If root is NULL, print not found.
• Traverse left or right depending on comparison.
• If match found, print the value.

Deletion:
1. Create a function for deleting an element from tree.
2. Perform standard BST deletion:
• No child → delete directly.
• One child → replace node with a child.
• Two children → replace with inorder successor (min in right subtree).
3. After deletion:
• Update height.
• Check balance.
 • Apply appropriate rotation based on balance.
4. Return updated root.
----------------------------------------
Question 5:
Algorithm:
1. Create a function to check validity of max heap.
a. Loop from i = n/2 down to 1:

• If left child exists (2*i <= n) and arr[i] < arr[2*i], it's not a Max Heap.
• If the right child exists (2*i+1 <= n) and arr[i] < arr[2*i+1], it's not a Max Heap.

b. Return true if all conditions are satisfied, otherwise false.

2. Create a function to check validity of min Heap.
a. Loop from i = n/2 down to 1:
• If a child left exists and arr[i] > arr[2*i], it's not a Min Heap.
• If the right child exists and arr[i] > arr[2*i+1], it's not a Min Heap.
b. Return true if all conditions are satisfied, otherwise false.
3. Create a function to evaluate heap type.
a. Call maxHeap() and minHeap() on the array.
b. Print:
• "All elements are equal (trivial heap)" if both return true.
• "Valid Max Heap" if only Max Heap is true.
• "Valid Min Heap" if only Min Heap is true.
• "Not a Valid Heap" otherwise.
c. If it's a valid heap (Min, Max, or both), display all tasks with priority less than the
provided value:
• Loop from i = 1 to n.
• If p[i] < value, print tasks[i] and its priority.
----------------------------------------
Question 6:
Algorithm:
Prim’s Algorithm:
1. Initialize a key[ ] array to store the minimum cost to connect each city. Set all keys to a large
value except the starting city (key[0] = 0).
2. Use a parent[] array to store which city connects to each city in the MST.
vector<int> key(V, 999999), parent(V, -1);
key[0] = 0;
3. Use a visited[] array to track which cities are already in the MST.
 vector<bool> inMST(V, false);
4. Repeat V - 1 times:
• Select the city with the smallest key[] value that’s not visited.
• Mark it as visited.
• For each adjacent city, if the cost is smaller than its current key[] and it's not visited, update
key[] and parent[].
5. After the loop, use parent[] to print the MST edges.
6. Sum all the selected edge costs from key[] to get the total MST cost.
Kruskal’s Algorithm:
1. Sort all edges (roads) by cost in ascending order.
2. Initialize a parent[] array for the Union-Find structure (initially, each city is its own parent).
3. Initialize an empty list for MST edges.
4. For each edge (u, v) in the sorted list:
• Use find(parent, u) and find(parent, v) to check if u and v belong to different sets.
• If they are in different sets (no cycle), include the edge in the MST and unite the sets.
5. Stop when V-1 edges have been added to the MST.
6. Output the total cost and all selected edges.
----------------------------------------
Question 7:
Algorithm:
Breadth First Search:
1. Initialize a 2D visited array of size m × n with all values false.
2. Initialize a queue q.
3. Mark the starting cell (startRow, startCol) as visited and pushed it into the queue.
4. Initialize defect = 0.
5. While the queue is not empty:
a. Pop the front cell (r, c) from the queue.
b. For each of the 4 directions:
i. Compute new rows and new column by:
nr = r + dr , nc = c + dc
ii. If (nr, nc) is within bounds and not visited:
• Visited[nr][nc]=true;
• If graph[nr][nc] == 1, increment defect.
• Push (nr, nc) into the queue.
6. Output the value of defect.
Depth First Search:
1. Initialize a 2D visited array of size m × n with all values false.
2. Initialize a stack s.
3. Mark the starting cell (startRow, startCol) as visited and push it onto the stack.
4. Initialize defect = 0.
5. While the stack is not empty:
a. Pop the top cell (r, c) from the stack.
b. For each of the 4 directions:
I. Compute new row nr = r + dr, and new column nc = c + dc.
II. If (nr, nc) is within bounds and not visited:
• Mark it as visited.
• If graph[nr][nc] == 1, increment defect.
• Push (nr, nc) onto the stack.
6. Output the value of defect.
----------------------------------------