Ashis Rahman
Batch: 242(43)
Dept: SWE
Data Structure Exam Solutions
Course Code: SE 1331 - Data Structure
Daffodil International University
Faculty of Science & Information Technology
Question 1(a): Binary Expression Tree Construction [4 Marks]
Problem: A software tool is parsing arithmetic expressions into a binary expression tree. The
tree stores operands and operators in nodes and uses different traversals to convert the
expression in different notations.
Given:
Inorder Traversal: 15, 20, 25, 30, 35, 40, 45
Preorder Traversal: 15, 25, 20, 35, 40, 30, 45
Task: Construct the preorder traversal of the binary tree.
Solution:
Since we have both Inorder and Preorder traversals, we can construct the binary tree step by
step.
Step 1: Identify the root from preorder traversal
Root = 15 (first element in preorder)
Step 2: Split inorder traversal around root
Left subtree (inorder): [] (empty - no elements before 15)
Right subtree (inorder): [20, 25, 30, 35, 40, 45]
Step 3: Continue recursively with remaining preorder elements
Tree Construction Process:
Preorder: [15, 25, 20, 35, 40, 30, 45]
Inorder: [15, 20, 25, 30, 35, 40, 45]
Root: 15
├── Left: NULL
└── Right: Process [25, 20, 35, 40, 30, 45] with inorder [20, 25, 30, 35, 40, 45]
Continuing the process:
For right subtree:
Preorder: [25, 20, 35, 40, 30, 45]
Inorder: [20, 25, 30, 35, 40, 45]
Root: 25
├── Left: [20] (from inorder: elements before 25)
└── Right: [30, 35, 40, 45] (from inorder: elements after 25)
Final Tree Structure:
15
\
25
/ \
20 35
/ \
30 40
\
45
Answer: The preorder traversal of the binary tree is: 15, 25, 20, 35, 30, 40, 45
Question 1(b): BST Operations for University Scheduling [4 Marks]
Problem: AI-powered scheduling system for university classes using Binary Search Tree (BST).
Given Classes:
401 (Math), 201 (Physics), 101 (English), 301 (Biology), 501 (Islamiyah), 701 (ICT)
Tasks:
1. Draw the BST after inserting class codes clearly
2. Draw the BST after deleting class 401 and explain which class replaces it and why
Solution:
Part 1: BST Construction
Step-by-Step BST Construction:
Initial: Empty BST
Step 1: Insert 401
401
Step 2: Insert 201 (201 < 401, goes left)
401
/
201
Step 3: Insert 101 (101 < 401, 101 < 201, goes left of 201)
401
/
201
/
101
Step 4: Insert 301 (301 < 401, 301 > 201, goes right of 201)
401
/
201
/ \
101 301
Step 5: Insert 501 (501 > 401, goes right of 401)
401
/ \
201 501
/ \
101 301
Step 6: Insert 701 (701 > 401, 701 > 501, goes right of 501)
401
/ \
201 501
/ \ \
101 301 701
Part 2: BST After Deleting Node 401
Before Deletion:
401
/ \
201 501
/ \ \
101 301 701
After Deleting 401:
Node 401 has two children, so we need to replace it with either:
Inorder Successor (leftmost node in right subtree): 501
Inorder Predecessor (rightmost node in left subtree): 301
Using Inorder Successor (501):
Step 1: Find successor of 401 = 501 (leftmost in right subtree)
Step 2: Replace 401 with 501
Step 3: Handle 501's original position (it had right child 701)
After Deletion:
501
/ \
201 701
/ \
101 301
Explanation: Class 501 replaces class 401 because it is the inorder successor of 401. The
inorder successor is the smallest element in the right subtree, which maintains the BST property
after replacement.
Question 3(i): Circular Queue Operations [6 Marks]
Problem: Circular Queue of Size 6 (Index 0 to 5). Initially empty with Front = -1 and Rear = -1.
Operations: Enqueue M, S, P, A, L. Show Front and Rear pointer values.
Solution:
Initial State:
Index: 0 1 2 3 4 5
Queue: [ ] [ ] [ ] [ ] [ ] [ ]
Front: -1
Rear: -1
Step 1: Enqueue M
Index: 0 1 2 3 4 5
Queue: [M] [ ] [ ] [ ] [ ] [ ]
Front: 0 (set to 0 for first element)
Rear: 0
Step 2: Enqueue S
Index: 0 1 2 3 4 5
Queue: [M] [S] [ ] [ ] [ ] [ ]
Front: 0
Rear: 1
Step 3: Enqueue P
Index: 0 1 2 3 4 5
Queue: [M] [S] [P] [ ] [ ] [ ]
Front: 0
Rear: 2
Step 4: Enqueue A
Index: 0 1 2 3 4 5
Queue: [M] [S] [P] [A] [ ] [ ]
Front: 0
Rear: 3
Step 5: Enqueue L
Index: 0 1 2 3 4 5
Queue: [M] [S] [P] [A] [L] [ ]
Front: 0
Rear: 4
Final State:
Front: 0
Rear: 4
Queue Contents: M, S, P, A, L
Question 3(ii): Queue Delete Operations [Same as above]
Continuing from previous state, perform operations:
Illustrate Queue after performing Delete operation for two elements:
Delete Operation 1:
Before:
Index: 0 1 2 3 4 5
Queue: [M] [S] [P] [A] [L] [ ]
Front: 0
Rear: 4
After Deleting M:
Index: 0 1 2 3 4 5
Queue: [ ] [S] [P] [A] [L] [ ]
Front: 1 (moved to next element)
Rear: 4
Delete Operation 2:
Before:
Index: 0 1 2 3 4 5
Queue: [ ] [S] [P] [A] [L] [ ]
Front: 1
Rear: 4
After Deleting S:
Index: 0 1 2 3 4 5
Queue: [ ] [ ] [P] [A] [L] [ ]
Front: 2 (moved to next element)
Rear: 4
Insert C, T, R, U operations:
Insert C:
Index: 0 1 2 3 4 5
Queue: [ ] [ ] [P] [A] [L] [C]
Front: 2
Rear: 5
Insert T (Circular wrap-around):
Index: 0 1 2 3 4 5
Queue: [T] [ ] [P] [A] [L] [C]
Front: 2
Rear: 0 (wrapped to index 0)
Insert R:
Index: 0 1 2 3 4 5
Queue: [T] [R] [P] [A] [L] [C]
Front: 2
Rear: 1
Insert U:
Queue is now full! Cannot insert U.
Index: 0 1 2 3 4 5
Queue: [T] [R] [P] [A] [L] [C]
Front: 2
Rear: 1
Status: OVERFLOW - Queue is Full
What happens when we try to delete from Circular Queue of Front = -1?
Answer: When Front = -1, it indicates the queue is empty. Attempting to delete from an empty
queue results in UNDERFLOW condition. The system should return an error message: "Queue is
empty - cannot delete."
Question 3(j): Linear Queue vs Circular Queue Demonstration [3 Marks]
Linear Queue Issues:
Problem with Linear Queue:
Initial: Front=0, Rear=-1, Size=5
Array: [ ][ ][ ][ ][ ]
After enqueue A,B,C:
Array: [A][B][C][ ][ ]
Front=0, Rear=2
After dequeue A,B:
Array: [ ][ ][C][ ][ ]
Front=2, Rear=2
Problem: Even though we have 4 empty spaces,
we cannot enqueue more than 2 elements because
Rear has reached near the end!
Linear Queue Limitation:
Wasted Space: Front positions become unusable after dequeue operations
False Full Condition: Queue appears full even when there are empty spaces
Memory Inefficiency: Cannot reuse deallocated front spaces
Circular Queue Solution:
Circular Queue Advantage:
Same scenario with Circular Queue:
Initial: Front=-1, Rear=-1, Size=5
After enqueue A,B,C:
Array: [A][B][C][ ][ ]
Front=0, Rear=2
After dequeue A,B:
Array: [ ][ ][C][ ][ ]
Front=2, Rear=2
Now we can enqueue D,E,F,G using circular wrapping:
Array: [D][E][C][F][G]
Front=2, Rear=1 (wrapped around)
Key Differences:
Aspect Linear Queue Circular Queue
Space Utilization Poor - wasted front space Excellent - reuses all space
Memory Efficiency Low High
Implementation Simple Moderate (uses modulo)
Real-world Usage Limited Preferred for most applications
Question 3(k): Double Ended Queue (Deque) [3 Marks]
Problem: Demonstrate Double Ended Queue operations with examples and mention restrictions.
What is a Deque?
A Double Ended Queue (Deque) is a linear data structure that allows insertion and deletion
operations at both ends - front and rear.
Deque Operations:
1. insertFront(x) - Insert element at front
2. insertRear(x) - Insert element at rear
3. deleteFront() - Delete element from front
4. deleteRear() - Delete element from rear
5. getFront() - Get front element
6. getRear() - Get rear element
Step-by-Step Demonstration:
Initial State:
Deque: [ ]
Front: -1, Rear: -1
Operation 1: insertRear(10)
Deque: [10]
Front: 0, Rear: 0
Operation 2: insertRear(20)
Deque: [10][20]
Front: 0, Rear: 1
Operation 3: insertFront(5)
Deque: [5][10][20]
Front: 0, Rear: 2
Operation 4: insertFront(2)
Deque: [2][5][10][20]
Front: 0, Rear: 3
Operation 5: deleteFront()
Deque: [5][10][20]
Front: 1, Rear: 3
Deleted: 2
Operation 6: deleteRear()
Deque: [5][10]
Front: 1, Rear: 2
Deleted: 20
Restrictions Associated with Deque:
1. Size Limitation: Fixed size in array implementation
2. Overflow Condition: Cannot insert when deque is full
3. Underflow Condition: Cannot delete from empty deque
4. Index Management: Complex front/rear pointer management in circular implementation
5. Memory Allocation: Dynamic memory management in linked list implementation
Types of Deque with Restrictions:
1. Input Restricted Deque:
Insertion: Only at one end (rear)
Deletion: Both ends allowed
Restriction: Cannot insert from front
2. Output Restricted Deque:
Insertion: Both ends allowed
Deletion: Only from one end (front)
Restriction: Cannot delete from rear
Question 4: Resource Tracking System with Linked Lists [5 Marks]
Problem: Emergency relief coordination platform using dynamic lists for Relief Center Names.
Given Relief Centers: Gaza, Rafah, Salfit, Nablus
Memory addresses for storing logistics data:
0x1782, 0x1783, 0x1784, 0x1785, 0x1786, 0x1787
Part (a): Doubly Linked List Construction
Step 1: Create Initial Linked List
After inserting Gaza, Rafah, Salfit, Nablus:
Structure of each node:
[PREV|DATA|NEXT]
Step-by-Step Construction:
Insert Gaza (First Node):
HEAD -> [NULL|Gaza|NULL]
Insert Rafah:
HEAD -> [NULL|Gaza|0x1782] <-> [0x1781|Rafah|NULL]
Insert Salfit:
HEAD -> [NULL|Gaza|0x1782] <-> [0x1781|Rafah|0x1783] <-> [0x1782|Salfit|NULL]
Insert Nablus:
HEAD -> [NULL|Gaza|0x1782] <-> [0x1781|Rafah|0x1783] <-> [0x1782|Salfit|0x1784] <-> [0x17
Memory Address Assignment:
Gaza: 0x1781
Rafah: 0x1782
Salfit: 0x1783
Nablus: 0x1784
Part (b): Insert "Jenin" as 1st element
Before Insertion:
HEAD -> [NULL|Gaza|0x1782] <-> [0x1781|Rafah|0x1783] <-> [0x1782|Salfit|0x1784] <-> [0x17
Step 1: Create new node for "Jenin" at address 0x1785
Step 2: Set Jenin's next to point to Gaza
Step 3: Set Gaza's prev to point to Jenin
Step 4: Update HEAD to point to Jenin
After Insertion:
HEAD -> [NULL|Jenin|0x1781] <-> [0x1785|Gaza|0x1782] <-> [0x1781|Rafah|0x1783] <-> [0x178
Part (c): Insert "Tulkarm" as 4th element
Position Analysis: 1st: Jenin, 2nd: Gaza, 3rd: Rafah, 4th: Tulkarm (between Rafah and Salfit)
Before Insertion:
HEAD -> [NULL|Jenin|0x1781] <-> [0x1785|Gaza|0x1782] <-> [0x1781|Rafah|0x1783] <-> [0x178
Insertion Steps:
1. Create new node for "Tulkarm" at address 0x1786
2. Set Tulkarm's prev to point to Rafah (0x1782)
3. Set Tulkarm's next to point to Salfit (0x1783)
4. Update Rafah's next to point to Tulkarm (0x1786)
5. Update Salfit's prev to point to Tulkarm (0x1786)
After Insertion:
HEAD -> [NULL|Jenin|0x1781] <-> [0x1785|Gaza|0x1782] <-> [0x1781|Rafah|0x1786] <-> [0x178
Part (d): Insert "Hebron" as last element
Before Insertion:
HEAD -> [NULL|Jenin|0x1781] <-> [0x1785|Gaza|0x1782] <-> [0x1781|Rafah|0x1786] <-> [0x178
Insertion Steps:
1. Create new node for "Hebron" at address 0x1787
2. Set Hebron's prev to point to Nablus (0x1784)
3. Set Hebron's next to NULL (last element)
4. Update Nablus's next to point to Hebron (0x1787)
After Insertion:
HEAD -> [NULL|Jenin|0x1781] <-> [0x1785|Gaza|0x1782] <-> [0x1781|Rafah|0x1786] <-> [0x178
Final Linked List Structure:
Jenin <-> Gaza <-> Rafah <-> Tulkarm <-> Salfit <-> Nablus <-> Hebron
Part (e): Convert to Circular Linked List
Steps to Convert:
1. Set Hebron's next pointer to point to Jenin (HEAD)
2. Set Jenin's prev pointer to point to Hebron (TAIL)
Circular Doubly Linked List:
┌─[NULL|Jenin|0x1781]──[0x1785|Gaza|0x1782]──[0x1781|Rafah|0x1786]──[0x1782|Tulkarm
│
└────────────────────────────────────────────────────────────────────
Modified Pointers:
Jenin's prev: 0x1787 (points to Hebron)
Hebron's next: 0x1785 (points to Jenin)
Part (f): Convert to Circular with Sentinel Value
Add "Bethlehem" as 3rd element:
Before Addition:
Circular: Jenin <-> Gaza <-> Rafah <-> Tulkarm <-> Salfit <-> Nablus <-> Hebron <-> (back
After Adding Bethlehem as 3rd element:
Circular: Jenin <-> Gaza <-> Bethlehem <-> Rafah <-> Tulkarm <-> Salfit <-> Nablus <-> He
Insertion Process:
1. Position: Between Gaza (2nd) and Rafah (current 3rd)
2. Create node for "Bethlehem"
3. Set Bethlehem's prev to Gaza
4. Set Bethlehem's next to Rafah
5. Update Gaza's next to Bethlehem
6. Update Rafah's prev to Bethlehem
Final Circular Doubly Linked List with 8 Relief Centers:
1. Jenin
2. Gaza
3. Bethlehem
4. Rafah
5. Tulkarm
6. Salfit
7. Nablus
8. Hebron
Summary
This solution covers all the major data structure operations from your syllabus:
Queue Operations (3.9-3.13):
✅ Circular queue implementation with enqueue/dequeue
✅ Linear vs circular queue comparison
✅ Double-ended queue (deque) operations
✅ Queue overflow/underflow conditions
Tree Operations (5.1-5.10):
✅ Binary tree construction from traversals
✅ Tree node relationships and properties
✅ Tree traversal methods (inorder, preorder)
BST Operations (6.1-6.7):
✅ BST construction and insertion
✅ BST deletion with successor/predecessor
✅ BST property maintenance after operations
Additional Covered Topics:
✅ Doubly linked list operations
✅ Circular linked list conversion
✅ Dynamic memory management
✅ Step-by-step visual representations
All solutions include detailed step-by-step drawings and explanations as requested, following
the format and depth expected for university-level data structure examinations.