DATA STRUCTURES USING PYTHON

Complete Unit-wise Q&A with Exam Answers

GE 4a · Generic Elective · NEP UGCF 2022 · Max Marks: 90

PRIORITY ORDER UNIT WEIGHTAGE

1st — Start Here Unit 2: Arrays, Linked Lists, Stacks, Queues ~40%

2nd — Learn Next Unit 4: Trees, BST, AVL ~25%

3rd — Then Cover Unit 1: Growth of Functions & Recurrences ~20%

4th — Quick Revision Unit 3: Recursion ~10%

5th — Last Unit 5: Binary Heap ~5%

 ★★★★★ | HIGHEST PRIORITY —
UNIT 2 · Arrays, Linked Lists, Stacks & 40% of Exam | 16 Credit Hours
Queues
Unit Introduction
Unit 2 is the largest and most heavily tested unit in this paper. It covers linear data structures — Arrays,
Singly/Doubly/Circular Linked Lists, Stacks, Queues, Circular Queues, Priority Queues, and Deques. Every
PYQ paper has 4–6 questions from this unit alone.
Key themes: Abstract Data Types (ADTs), LIFO vs FIFO, trace-based questions (step-by-step operation
sequences), time complexity of basic operations, infix-to-postfix conversion, and circular queue mechanics.

SECTION A — Short Answer Questions

U2 | Section A 1 marks

True/False: Stack uses FIFO access method. Justify.

FALSE. A Stack uses LIFO (Last In, First Out). The last element pushed onto the stack is the first one
popped out. FIFO (First In, First Out) is the principle used by Queues, not stacks. Example: Undo operations
in an editor use a stack — the most recent action is undone first.
■ Exam Tip: This exact True/False appears in Paper 4659 and 4955. Always write LIFO as justification.

U2 | Section A 1 marks

True/False: A doubly linked list uses more memory than a circular linked list. Justify.

TRUE. A Doubly Linked List (DLL) stores two pointers per node — one pointing to the next node and one
pointing to the previous node. A Circular Linked List (CLL) stores only one pointer (next), with the last node
pointing back to the first. Therefore DLL uses more memory per node.
■ Exam Tip: Memory per node: DLL = data + prev + next (3 fields). CLL = data + next (2 fields).

U2 | Section A 3 marks

What is an Abstract Data Type (ADT)? Give two advantages.

An Abstract Data Type (ADT) is a mathematical model for a data type that defines:
(1) The data it stores, (2) The operations it supports, and (3) The error conditions associated with those
operations — without specifying the implementation details.
Examples: Stack ADT supports push(), pop(), top(), is_empty(). The user does not need to know whether it
is implemented using an array or linked list.
• Advantage 1 — Encapsulation: Hides internal implementation; user only sees the interface.
• Advantage 2 — Reusability: The same ADT can be implemented differently and swapped without
changing user code.
• Advantage 3 — Modularity: Easier to design, test, and debug large programs.

U2 | Section A 3 marks

Choose the most appropriate data structure for: (i) Browser back/forward navigation (ii)
Hierarchical data (iii) LIFO manner storage.

• (i) Browser back/forward navigation → Stack (back uses pop; URLs stored on stack)
 • (ii) Hierarchical data (e.g., file system, org charts) → Tree
• (iii) Last-In-First-Out storage → Stack
■ Exam Tip: Also memorise: Traffic/ticket booking → Queue; Sorted search → BST; Priority tasks →
Heap/Priority Queue.

U2 | Section A 3 marks

How is a Priority Queue different from a normal Queue? Write one application.

Normal Queue: Elements are removed in FIFO order — the element that has been waiting longest is served
first, regardless of its value.
Priority Queue: Each element has an associated priority. The element with the highest (or lowest) priority is
served first, regardless of insertion order.
Key Difference: In a normal queue, order is determined by arrival time. In a priority queue, order is
determined by priority value.
• Application 1: CPU Scheduling — high-priority processes get CPU time first.
• Application 2: Emergency Room Triage — critical patients are attended before minor ones.
• Application 3: Dijkstra's Shortest Path Algorithm — uses a min-priority queue.
■ Exam Tip: Two types: Max-Priority Queue (largest priority served first) and Min-Priority Queue (smallest
first).

U2 | Section A 3 marks

Write a Python code snippet to insert an element at the front of an existing singly linked list.

A new node is created and its next pointer is set to the current head, then the head pointer is updated to the
new node. This is an O(1) operation.
class Node:
def __init__(self, data):
[Link] = data
[Link] = None

def insert_at_front(head, data):

new_node = Node(data) # Create new node
new_node.next = head # Point new node to old head
head = new_node # Update head to new node
return head # Return new head
■ Exam Tip: Always return the new head from the function. Time complexity: O(1).

SECTION B — Long Answer Questions

U2 | Section B 9 marks

Q(a) Convert infix A*(B+D)/E - F*(G+H/K) to postfix. Show all steps. Q(b) Trace stack S of
size 5: push(5), push(3), pop(), top(), push(9), pop(), push(4), push(15), is_empty()

Part (a): Infix to Postfix Conversion

Algorithm: Scan left to right. Operands → output directly. Operators → push to stack if higher precedence
than top; else pop and output until higher precedence found. '(' → push. ')' → pop until '('.
Precedence: /, * (higher, left-to-right) > +, - (lower, left-to-right)
 Step Character Stack (bottom→top) Output

1 A empty A

2 * * A

3 ( *( A

4 B *( AB

5 + *(+ AB

6 D *(+ ABD

7 ) * ABD+

8 / / (pops *) ABD+*

9 E / ABD+*E

10 - - (pops /) ABD+*E/

11 F -F ABD+*E/F

12 * -* ABD+*E/F

13 ( -*( ABD+*E/F

14 G -*( ABD+*E/FG

15 + -*(+ ABD+*E/FG

16 H -*(+ ABD+*E/FGH

17 / -*(+/ ABD+*E/FGH

18 K -*(+/ ABD+*E/FGHK

19 ) -* ABD+*E/FGHK/+

End empty ABD+*E/FGHK/+*-

Final Postfix: A B D + * E / F G H K / + * -

Part (b): Stack Trace (Size = 5)

Operation Stack State (bottom→top) Return Value

Initial [ ] (empty) —

push(5) [5] —

push(3) [ 5, 3 ] —

pop() [5] 3

top() [5] 5 (no removal)

push(9) [ 5, 9 ] —

pop() [5] 9

push(4) [ 5, 4 ] —

push(15) [ 5, 4, 15 ] —

is_empty() [ 5, 4, 15 ] False
■ Exam Tip: show is_empty() → False because stack has 3 elements. Stack is NOT full (size=5, only 3 used).

U2 | Section B 6 marks
Write the time complexity for: (i) push in stack using linked list (ii) pop in stack using linked
list (iii) delete all from end in singly linked list (iv) search in BST (best case).

Operation Time Complexity Justification

push() in Stack (Linked List) O(1) Insert at head — no traversal needed

pop() in Stack (Linked List) O(1) Remove head — direct pointer update

Delete all from end in Singly LL O(n) Must traverse to (n-1)th node each time; repeated = O(n²) for al

Search in BST (Best Case) O(1) Element found at root itself

■ Exam Tip: BST average search = O(log n); worst case (skewed tree) = O(n).

U2 | Section B 11 marks

Q(a) Queue Q had 32 enqueue, 10 first operations (5 raised Empty errors), 15 dequeue. What
is current size? Q(b) Drawbacks of linear queue and how circular queue resolves them. Q(c)
Circular queue of size 4 (array): enqueue(14), dequeue(), enqueue(3), enqueue(7),
enqueue(0), enqueue(9), enqueue(2). Show front and rear.

Part (a): Current Size of Queue

Effective enqueue operations = 32
Effective dequeue operations = 15 (the 5 first() calls that raised Empty errors did NOT remove elements)
Current Size = 32 - 15 = 17 elements

Part (b): Drawbacks of Linear Queue and Circular Queue Solution

• Drawback 1 — False Overflow: Even when front has moved (dequeues happened), rear reaches the
end and queue appears full even though slots at the front are free.
• Drawback 2 — Space Wastage: Dequeued positions cannot be reused in a linear array queue.
• Solution — Circular Queue: Uses modular arithmetic: rear = (rear + 1) % size and front = (front + 1) %
size. This wraps around and reuses freed slots.
• Full condition: (rear + 1) % size == front | Empty condition: front == rear

Part (c): Circular Queue Trace (Size = 4, indices 0–3)

Convention: front points to first element; rear points to next empty slot. Initial: front=0, rear=0 (empty)

Operation Queue Array [0..3] Front Rear Notes

Initial [_, _, _, _] 0 0 Empty: front==rear

enqueue(14) [14, _, _, _] 0 1 rear=(0+1)%4=1

dequeue() [_, _, _, _] 1 1 front=(0+1)%4=1; returns 14

enqueue(3) [_, 3, _, _] 1 2 —

enqueue(7) [_, 3, 7, _] 1 3 —

enqueue(0) [_, 3, 7, 0] 1 0 rear wraps: (3+1)%4=0

enqueue(9) FULL — (0+1)%4==1==front 1 0 Queue Full! Cannot insert

enqueue(2) FULL — Queue Full 1 0 Overflow error

■ Exam Tip: In a circular queue of size N (array), max N-1 elements can be stored (one slot kept empty to
distinguish full vs empty).
 U2 | Section B 5 marks

Differentiate Singly Linked List and Doubly Linked List. Write Python code to insert at
beginning of singly linked list.

Feature Singly Linked List Doubly Linked List

Pointers per node 1 (next only) 2 (prev + next)

Memory usage Less More (extra pointer)

Traversal Forward only Forward and Backward

Deletion (given node) O(n) — need prev node O(1) — has prev pointer

Insert at beginning O(1) O(1)

Use case Simple lists, stacks Browser history, LRU cache

def insert_at_beginning(head, data):
new_node = Node(data)
new_node.next = head # Link new node to existing list
return new_node # New node becomes new head

U2 | Section B 5 marks

Write Python code to delete a node from the end of a singly linked list.

To delete from end, traverse until the second-to-last node (whose [Link] is None), then set its next to
None.
def delete_from_end(head):
if head is None: # Empty list
return None
if [Link] is None: # Only one node
return None
current = head
while [Link] is not None:
current = [Link] # Stop at 2nd-to-last node
[Link] = None # Remove last node
return head
■ Exam Tip: Time complexity: O(n) — must traverse the entire list.

U2 | Section B 4 marks

Give two real-life applications each of Stack and Queue.

Data Structure Application 1 Application 2

Browser Back/Forward Navigation Undo/Redo in text editors

Stack
(visited pages stored as stack) (each action pushed; undo pops)

Printer Spooler CPU Process Scheduling

Queue
(print jobs processed in order received) (FCFS — first come first served)

U2 | Section B 5 marks

What is a Deque? How is it different from a Queue? List all operations.

Deque (Double-Ended Queue): A linear data structure that allows insertion and deletion from both the front
and the rear ends. It is more flexible than a standard queue.

Feature Queue Deque

Insertion Rear only Front OR Rear

Deletion Front only Front OR Rear

Flexibility Restricted Unrestricted (both ends)

Operations on Deque:
• insertFront(e) — Insert element at front
• insertRear(e) — Insert element at rear
• deleteFront() — Remove element from front
• deleteRear() — Remove element from rear
• first() — Return (but not remove) front element
• last() — Return (but not remove) rear element
• is_empty() — Returns True if deque is empty
• size() — Returns number of elements

U2 | Section B 4 marks

Doubly linked list operations: InsertBeginning(12), InsertBeginning(4), InsertEnd(3),

InsertEnd(1), DeleteBeginning(), Deletenode(1). Show content after each.

Operation List State (head → ... → tail) Notes

Initial [] Empty list

InsertBeginning(12) 12 head=12

InsertBeginning(4) 4 ↔ 12 4 becomes new head

InsertEnd(3) 4 ↔ 12 ↔ 3 3 added at tail

InsertEnd(1) 4 ↔ 12 ↔ 3 ↔ 1 1 added at tail

DeleteBeginning() 12 ↔ 3 ↔ 1 4 removed; 12 is new head

Deletenode(1) 12 ↔ 3 1 removed from tail

U2 | Section B 4 marks

Differences between Array and Linked List (any 2 points each); Stack and Queue (any 2
points each).

Array vs Linked List Array Linked List

Memory Contiguous block allocated at compile time

Non-contiguous; each node allocated dynamically

Size Fixed (static arrays) Dynamic — grows/shrinks at runtime

Access Random access O(1) using index Sequential access O(n) — must traverse

Insertion/Deletion O(n) — shifting required O(1) at head; O(n) at arbitrary position

Stack vs Queue Stack (LIFO) Queue (FIFO)

Access order Last inserted element removed first First inserted element removed first
 Operations push(), pop(), top() enqueue(), dequeue(), front()

Applications Undo, recursion, expression evaluationCPU scheduling, BFS, ticket booking

U2 | Section B 5 marks

Write Python code to implement a Stack using a Linked List (push and pop functions).

In a linked list-based stack, push inserts at the head (O(1)) and pop removes from the head (O(1)). The head
of the linked list serves as the top of the stack.
class Node:
def __init__(self, data):
[Link] = data
[Link] = None

class Stack:
def __init__(self):
[Link] = None # Head of linked list = top of stack
self._size = 0

def push(self, data):

new_node = Node(data)
new_node.next = [Link] # Link to existing stack
[Link] = new_node # Update top
self._size += 1

def pop(self):
if self.is_empty():
raise Exception("Stack is empty")
popped = [Link]
[Link] = [Link] # Move top to next node
self._size -= 1
return popped

def peek(self):
if self.is_empty():
raise Exception("Stack is empty")
return [Link]

def is_empty(self):
return [Link] is None

def size(self):
return self._size
 ★★★★■ | HIGH PRIORITY — 25%
UNIT 4 · Trees, BST & Balanced Search of Exam | 13 Credit Hours
Trees
Unit Introduction
Unit 4 covers tree data structures — from general binary trees to Binary Search Trees (BST) and AVL trees.
A dedicated multi-part BST question (insert/delete/traverse/balance-check) appears in every Section B. Tree
traversals (Inorder, Preorder, Postorder, BFS) and tree construction from traversals are repeatedly asked.
Key themes: Tree terminology, traversals, BST operations (insert/delete 3 cases/search), height-balance
check, AVL rotations, and constructing trees from given traversal sequences.

SECTION A — Short Answer Questions

U4 | Section A 1 marks

True/False: In-order traversal of a Binary Search Tree gives a sorted sequence. Justify.

TRUE. The BST property states that for every node: all keys in the left subtree < node key < all keys in right
subtree. In-order traversal visits nodes in Left → Root → Right order. Applying this recursively to a BST
always visits nodes in ascending sorted order.
Example: BST with keys {3, 5, 7} — in-order gives 3, 5, 7.
■ Exam Tip: This is a guaranteed True/False question. Always state the BST property as justification.

U4 | Section A 3 marks

What is an AVL Tree? Explain with a suitable example. Give one application.

AVL Tree (Adelson-Velsky and Landis Tree) is a self-balancing Binary Search Tree in which the difference
between the heights of the left and right subtrees of every node is at most 1. This difference is called the
Balance Factor.
Balance Factor (BF) = Height(Left Subtree) - Height(Right Subtree)
Valid BF values: -1, 0, or +1. If |BF| > 1 after insertion/deletion, rotations are performed to restore balance.

Rotation Type Trigger Condition Action

LL Rotation (Right) BF = +2, Left child BF = +1 Single right rotation at unbalanced node

RR Rotation (Left) BF = -2, Right child BF = -1 Single left rotation at unbalanced node

LR Rotation BF = +2, Left child BF = -1 Left rotate left child, then right rotate node

RL Rotation BF = -2, Right child BF = +1 Right rotate right child, then left rotate node

• Application: Database Indexing — AVL trees guarantee O(log n) search, insert, and delete, making
them ideal for database index structures.
• Application: In-memory sorted sets in programming language libraries.

U4 | Section A 6 marks

Differentiate: (i) BFS and DFS tree traversal (ii) Complete and Perfect Binary Tree.

Feature BFS (Breadth-First) DFS (Depth-First)

Order Level by level (left to right) Goes deep into one branch first
 Data structure used Queue Stack (or recursion)

Also called Level-order traversal Preorder / Inorder / Postorder

Application Finding shortest path Tree traversals, backtracking

Feature Complete Binary Tree Perfect Binary Tree

Definition All levels filled except possibly last; last level filledALL
left levels
to rightcompletely filled; every leaf at same depth

Leaf nodes Last level may be partially filled All leaves at same level

Nodes at height h Between 2^h and 2^(h+1)-1 Exactly 2^(h+1)-1

Example use Heap implementation Theoretical analysis

SECTION B — Long Answer Questions

U4 | Section B 15 marks

BST with root=7, left: 3→(1, 5→(4,6)), right: 11→(9→8, 13→(12,14)). (a) Write breadth-first
traversal. (b) Insert node 10. (c) Postorder and inorder of result. Is it height-balanced?

Original BST Structure:

7
/\
3 11
/\/\
1 5 9 13
/\\/\
4 6 8 12 14

Part (a): Breadth-First (Level-Order) Traversal

Process each level left to right using a queue:
• Level 0: 7
• Level 1: 3, 11
• Level 2: 1, 5, 9, 13
• Level 3: 4, 6, 8, 12, 14
BFS Result: 7, 3, 11, 1, 5, 9, 13, 4, 6, 8, 12, 14

Part (b): Insert Node 10

Compare 10 with root 7 → 10 > 7, go right → reach 11 → 10 < 11, go left → reach 9 → 10 > 9, go right → 9's
right has 8 ... wait: 9's only child is 8 (left). So 10 > 9 → go right → NULL → Insert 10 as right child of 9.
7
/\
3 11
/\/\
1 5 9 13
/\/\/\
4 6 8 10 12 14

Part (c): Traversals of Resultant Tree (after inserting 10)

Inorder (Left-Root-Right) — gives sorted sequence:
1, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14
Postorder (Left-Right-Root):
1, 4, 6, 5, 3, 8, 10, 9, 12, 14, 13, 11, 7

Height-Balance Check:
For each node, compute: BF = |h(left) - h(right)|

Node h(Left subtree) h(Right subtree) Balance Factor |L-R| Balanced?

7 3 (path:3→5→4 or 6) 3 (path:11→13→12 or 14)0 ✓

3 1 (node 1) 2 (3→5→4 or 6) 1 ✓

11 2 (9→8 or 10) 2 (13→12 or 14) 0 ✓

5 1 1 0 ✓

9 1 (node 8) 1 (node 10) 0 ✓

13 1 (node 12) 1 (node 14) 0 ✓

1,4,6,8,10,12,14
0 0 0 ✓ (leaves)
Conclusion: YES, the tree is height-balanced (AVL property satisfied at every node).
■ Exam Tip: Always check balance factor at every node, not just the root. Show your calculations.

U4 | Section B 5 marks

Create a binary tree given: Inorder: x y z a p q r; Preorder: a y x z q p r.

Algorithm: First element of Preorder = root. Find root in Inorder — elements to its left form left subtree,
elements to its right form right subtree. Recurse.
Step 1: Preorder[0] = a → Root = a
Step 2: In Inorder: x y z a p q r → Left subtree: {x, y, z} | Right subtree: {p, q, r}
Step 3: Next in Preorder for left subtree: y → Left root = y
In {x,y,z}: x y z → Left of y = {x}, Right of y = {z}
Step 4: Next in Preorder for right subtree: q → Right root = q
In {p,q,r}: p q r → Left of q = {p}, Right of q = {r}
Final Tree Structure:
a ← root
/\
yq
/\/\
xzpr
■ Exam Tip: Always start with Preorder to find roots, then split Inorder for subtrees. Practice this algorithm!

U4 | Section B 6 marks

Create BST with {7,5,1,8,3,6,0,9,4,2} and write in-order traversal.

BST Insertion (insert elements left to right):

 Insert Comparison path Position

7 Root Root = 7

5 5<7, go left Left child of 7

1 1<7→left, 1<5→left Left child of 5

8 8>7, go right Right child of 7

3 3<7→left, 3<5→left, 3>1→right Right child of 1

6 6<7→left, 6>5→right Right child of 5

0 0<7,0<5,0<1→left Left child of 1

9 9>7,9>8→right Right child of 8

4 4<7,4<5,4>1,4>3→right Right child of 3

2 2<7,2<5,2>1,2<3→left Left child of 3

In-order Traversal (sorted output): 0, 1, 2, 3, 4, 5, 6, 7, 8, 9
■ Exam Tip: In-order of BST always gives sorted sequence. Use this as a self-check.

U4 | Section B 6 marks

BST (root=8, 3→1,6→4,7; 10→14→13). Perform: (i) Insert 2 (ii) Delete 3 (iii) Post-order
traversal (iv) Height-balance check (v) Pre-order traversal.

Original BST:
8
/ \
3 10
/ \ \
1 6 14
/\ /
4 7 13
(i) Insert 2: 2 < 8 → left → 2 < 3 → left → 2 > 1 → right child of 1 → Insert 2 as right child of 1.
(ii) Delete 3 (has TWO children: 1 and 6) → Replace with Inorder Successor (smallest in right subtree of 3) =
4. Delete 4 from its original position. Node 3 is replaced by 4.
Tree after insert 2 and delete 3:
8
/ \
4 10
/ \ \
1 6 14
\ \ /
2 7 13
(iii) Post-order (Left-Right-Root): 2, 1, 7, 6, 4, 13, 14, 10, 8
(v) Pre-order (Root-Left-Right): 8, 4, 1, 2, 6, 7, 10, 14, 13
(iv) Height-balance check: Node 10: h(left)=0, h(right)=2 (10→14→13). BF = |0-2| = 2 > 1 → NOT
height-balanced.
■ Exam Tip: 3 cases for BST delete: (1) Leaf → simply remove. (2) One child → replace node with child. (3) Two
children → replace with inorder successor (or predecessor).
 ★★★★■ | HIGH PRIORITY — 20%
UNIT 1 · Growth of Functions & of Exam | 8 Credit Hours
Recurrence Relations
Unit Introduction
Unit 1 covers mathematical tools for analyzing algorithm efficiency. The three asymptotic notations (Big-O,
Big-Omega, Big-Theta) appear in every paper. Recurrence relation solving (Recurrence Tree and Master
Theorem) is highly formulaic — learn the methods and you can score full marks on any variant.
Key themes: Prove f(n) = O(g(n)), arrange functions by growth rate, solve T(n) using substitution/recurrence
tree/master theorem.

U1 | Section B 4 marks

Differentiate between Big-O, Big-Omega, and Big-Theta notations.

Notation Name Meaning Describes

O(g(n)) Big-O f(n) ≤ c·g(n) for all n ≥ n■ Upper bound (worst case)

Ω(g(n)) Big-Omega f(n) ≥ c·g(n) for all n ≥ n■ Lower bound (best case)

Θ(g(n)) Big-Theta c■·g(n) ≤ f(n) ≤ c■·g(n) for all n ≥ n■ Tight bound (average case)

Formal Definitions:
• f(n) = O(g(n)) if ∃ constants c > 0, n■ > 0 such that f(n) ≤ c·g(n) for all n ≥ n■
• f(n) = Ω(g(n)) if ∃ constants c > 0, n■ > 0 such that f(n) ≥ c·g(n) for all n ≥ n■
• f(n) = Θ(g(n)) if f(n) = O(g(n)) AND f(n) = Ω(g(n))
■ Exam Tip: If f(n) = Θ(g(n)), then g(n) is the EXACT growth rate of f(n). Big-O is most commonly used in
analysis.

U1 | Section B 6 marks

Explain what Big-O notation represents. Show that f(n) = 8n + 5 is O(n).

Big-O Notation: Big-O (O) gives the upper bound on the growth rate of a function. f(n) = O(g(n)) means the
function f(n) grows no faster than g(n) for sufficiently large n. It represents the worst-case time complexity
of an algorithm.
Proof that f(n) = 8n + 5 is O(n):
We need to find constants c > 0 and n■ > 0 such that: 8n + 5 ≤ c·n for all n ≥ n■
Choose c = 9 and n■ = 5:
8n + 5 ≤ 8n + n = 9n (valid when n ≥ 5, because 5 ≤ n)
So 8n + 5 ≤ 9·n for all n ≥ 5.
Therefore, f(n) = 8n + 5 = O(n) with c = 9 and n■ = 5. ✓
■ Exam Tip: Always state: the values of c and n■ explicitly. The examiner expects this proof format.

U1 | Section B 4 marks

Prove that T(n) = n³ + 20n + 1 is O(n³). Find c and n■.

We need: n³ + 20n + 1 ≤ c·n³ for all n ≥ n■

For n ≥ 1: 20n ≤ 20n³ and 1 ≤ n³
Therefore: n³ + 20n + 1 ≤ n³ + 20n³ + n³ = 22n³
So c = 22 and n■ = 1. Hence T(n) = O(n³). ✓
■ Exam Tip: Standard approach: bound each lower-order term by the highest-order term.

U1 | Section B 4 marks

Arrange f1(n) = 2^n, f2(n) = n^(2/3), f3(n) = n·log n, f4(n) = log n in increasing order of
asymptotic complexity.

Increasing order (slowest growing to fastest growing):

log n < n^(2/3) < n·log n < 2^n
i.e., f4 < f2 < f3 < f1

Function Growth Class Example: n=1000

log n (f4) Logarithmic — very slow ~10

n^(2/3) (f2) Sub-linear polynomial ~100

n·log n (f3) Linearithmic ~10,000

2^n (f1) Exponential — very fast Astronomically large

■ Exam Tip: Full complexity order: O(1) < O(log n) < O(n^(2/3)) < O(n) < O(n log n) < O(n²) < O(2^n)

U1 | Section B 4 marks

Use the Recurrence Tree Method to solve T(n) = T(n-1) + n.

Setting up the recurrence tree:

T(n) = T(n-1) + n
T(n-1) = T(n-2) + (n-1)
T(n-2) = T(n-3) + (n-2) ... and so on
Tree structure (each level shows cost at that level):
Level 0: cost = n
Level 1: cost = (n-1)
Level 2: cost = (n-2)
...
Level (n-1): cost = 1 [base case: T(1) = 1]
Total cost = sum of all levels:
T(n) = n + (n-1) + (n-2) + ... + 2 + 1
T(n) = n(n+1)/2
Therefore: T(n) = O(n²)
■ Exam Tip: This recurrence represents an iterative loop summing from 1 to n — hence O(n²).

U1 | Section B 5 marks

Solve T(n) = 2T(n/4) + n². Use Master Theorem.

Master Theorem: For T(n) = aT(n/b) + f(n):

 • Case 1: If f(n) = O(n^(log_b(a) - ε)) → T(n) = Θ(n^(log_b(a)))
• Case 2: If f(n) = Θ(n^(log_b(a))) → T(n) = Θ(n^(log_b(a)) · log n)
• Case 3: If f(n) = Ω(n^(log_b(a) + ε)) → T(n) = Θ(f(n))
Identify parameters:
a = 2, b = 4, f(n) = n²
log_b(a) = log■(2) = 1/2
n^(log_b(a)) = n^(1/2) = √n
Compare f(n) = n² with n^(1/2):
n² = Ω(n^(1/2 + ε)) for ε = 3/2 (since n² grows much faster than √n)
This is Case 3.
Verify regularity condition: a·f(n/b) ≤ c·f(n) → 2·(n/4)² = 2·n²/16 = n²/8 ≤ (1/8)·n² ✓
Therefore: T(n) = Θ(n²)
■ Exam Tip: Always: (1) identify a,b,f(n), (2) compute log_b(a), (3) compare f(n) with n^log_b(a), (4) state which
case, (5) write answer.

U1 | Section B 5 marks

Solve T(n) = 3T(n/2) + n² using Master Method.

a = 3, b = 2, f(n) = n²
log_b(a) = log■(3) ≈ 1.585
n^(log_b(a)) = n^(1.585)
Compare: f(n) = n² vs n^1.585 → n² grows faster → f(n) = Ω(n^(1.585 + ε)) for ε ≈ 0.415
Case 3 applies.
Regularity: 3·(n/2)² = 3n²/4 ≤ (3/4)·n² = c·f(n) with c = 3/4 < 1 ✓
T(n) = Θ(n²)

U1 | Section B 4 marks

Draw a Recurrence Tree for T(n) = 3T(n/4) + cn².

Tree structure:
Level 0: cn² (1 node)
Level 1: c(n/4)² each = cn²/16 (3 nodes) → Total: 3cn²/16
Level 2: c(n/16)² each (9 nodes) → Total: 9cn²/256 = (9/256)cn²
Pattern: at level i → (3/16)^i · cn² total cost
Number of levels: (n/4^k) = 1 → k = log■(n)
Total cost: Sum of geometric series:
T(n) = cn² · Σ(3/16)^i from i=0 to log■(n)
Since 3/16 < 1, series converges. T(n) = O(cn²) = O(n²)
The leaf level cost: 3^(log■(n)) = n^(log■(3)) ≈ n^0.79 — dominated by root level n².
■ Exam Tip: When the root cost dominates (r < 1 in geometric series), T(n) = Θ(f(n)) — this is Case 3 intuition.
 U1 | Section B 5 marks

Write a Python program to compute sum of n numbers in a list using recursion.

def recursive_sum(lst, n):
"""Returns sum of first n elements of list lst"""
if n == 0: # Base case: empty list has sum 0
return 0
else: # Recursive case
return lst[n-1] + recursive_sum(lst, n-1)

# Main program
n = int(input("Enter number of elements: "))
lst = []
for i in range(n):
[Link](int(input(f"Enter element {i+1}: ")))

result = recursive_sum(lst, n)
print(f"Sum of list = {result}")
■ Exam Tip: Always define base case first. Here base case is n=0 (empty list). Time complexity: O(n).
 ★★★■■ | MEDIUM PRIORITY —
UNIT 3 · Recursion 10% of Exam | 4 Credit Hours

Unit Introduction
Unit 3 is short but guaranteed to appear — usually 1 question in Section B involving Python code. Focus on:
Fibonacci (binary recursion), factorial/sum/power (linear recursion), and converting iterative code to
recursive. Know the base case and recursive case for each.

U3 | Section B 4 marks

Write a Python program to print Fibonacci numbers using Binary Recursion.

Binary Recursion: A function that makes TWO recursive calls per invocation. Fibonacci is the classic
example — each call splits into two sub-calls.
def fibonacci(n):
"""Returns nth Fibonacci number using binary recursion"""
if n == 0: # Base case 1
return 0
elif n == 1: # Base case 2
return 1
else: # Binary recursive case — two calls
return fibonacci(n-1) + fibonacci(n-2)

# Print first n Fibonacci numbers

n = int(input("Enter how many Fibonacci numbers to print: "))
print("Fibonacci Series:")
for i in range(n):
print(fibonacci(i), end=" ")
Example output for n=8: 0 1 1 2 3 5 8 13
■ Exam Tip: Time complexity of recursive Fibonacci: O(2^n) — exponential. Iterative is O(n). Examiner may
ask why it is "binary" recursion — answer: because fib(n) makes exactly 2 recursive calls.

U3 | Section B 4 marks

Convert the iterative power function to recursive: def power(base, exponent): result=1; for i
in range(exponent): result *= base; return result

Analysis of iterative function: Multiplies base by itself exponent times. The recursive equivalent reduces
exponent by 1 each call until exponent = 0 (base case = 1).
# Iterative version (given):
def power_iterative(base, exponent):
result = 1
for i in range(exponent):
result *= base
return result

# Recursive version:
def power(base, exponent):
if exponent == 0: # Base case: anything^0 = 1
return 1
else: # Recursive case: base^n = base * base^(n-1)
return base * power(base, exponent - 1)
 # Test
print(power(2, 5)) # Output: 32
print(power(3, 4)) # Output: 81
■ Exam Tip: Pattern for converting iterative to recursive: (1) identify loop termination → base case; (2) identify
loop body → recursive step; (3) return the combination.

U3 | Section B 4 marks

Write a recursive function to find factorial of n.

def factorial(n):
"""Returns n! using linear recursion"""
if n == 0 or n == 1: # Base case
return 1
else:
return n * factorial(n - 1) # Recursive case

# Test
n = int(input("Enter n: "))
print(f"{n}! = {factorial(n)}")
Trace for factorial(4): 4 × factorial(3) → 4 × 3 × factorial(2) → 4 × 3 × 2 × factorial(1) → 4 × 3 × 2 × 1 = 24

U3 | Section B 4 marks

When should recursion be used? Explain linear vs binary recursion.

When to use Recursion:

• When the problem can be broken into smaller sub-problems of the same type
• When dealing with tree traversal or hierarchical data structures
• When implementing LIFO (Last-In-First-Out) behavior naturally
• When the iterative solution is complex and recursion provides clarity
Type Definition Example Calls per step

Linear Recursion Function makes exactly ONE recursive call

Factorial, sum of list, power 1

Binary Recursion Function makes exactly TWO recursive calls

Fibonacci, binary search tree operations
2
 ★★■■■ | LOWER PRIORITY — 5%
UNIT 5 · Binary Heap of Exam | 4 Credit Hours

Unit Introduction
Unit 5 is the lowest-weightage unit but usually yields 3–6 easy marks in Section B. Focus on: heap
properties, max-heap vs min-heap, array representation, and building a max-heap. Also know how Binary
Heap differs from BST.

U5 | Section B 3 marks

Explain any two properties of Binary Heap. How is it different from a BST?

Binary Heap Properties:

• Property 1 — Shape Property: A binary heap is always a complete binary tree. All levels are
completely filled except possibly the last level, which is filled from left to right.
• Property 2 — Heap-Order Property: In a Max-Heap, the key of every node is ≥ keys of its children. In a
Min-Heap, the key of every node is ≤ keys of its children.
• Property 3 — Efficient array representation: Node at index i has left child at 2i+1, right child at 2i+2,
and parent at (i-1)//2.
Feature Binary Heap Binary Search Tree (BST)

Ordering Parent ≥ both children (max-heap) — NO left-right

Left ordering
subtree < node < right subtree — strict ordering

Shape Always complete binary tree Any shape (can be skewed)

Search O(n) — no ordering between siblings O(log n) average, O(n) worst

Find Max/Min O(1) — always at root O(n) or O(log n) for sorted path

Insert/Delete O(log n) with heapify O(log n) average

Primary use Priority Queue, Heap Sort Searching, sorting, ordered data

U5 | Section B 4 marks

For heap of height h, what is the maximum and minimum number of elements?

Height h means: root is at level 0, leaves at level h.

Formula Explanation

Minimum elements in height-h heap 2^h Only the last level has just 1 node (root at h=0: 1 node = 2^

Maximum elements in height-h heap 2^(h+1) - 1 All levels completely filled (perfect binary tree)

Examples:
• Height 0: min = 1, max = 1
• Height 1: min = 2, max = 3
• Height 2: min = 4, max = 7
• Height 3: min = 8, max = 15
■ Exam Tip: Formula to memorise: min = 2^h, max = 2^(h+1) - 1. These appear directly in exam questions.

U5 | Section B 6 marks

Construct max-heap for array A = [4,1,3,2,16,9,10,14,8,7]. Show all steps.

Initial array (0-indexed): [4, 1, 3, 2, 16, 9, 10, 14, 8, 7]
n = 10. Start heapify from last non-leaf node: index = (n//2) - 1 = 4
Step 1: Heapify at index 4 (value = 16)
Left child = 2×4+1 = 9 → value 7; Right child = 2×4+2 = 10 → out of range
16 > 7 → no swap. Array: [4, 1, 3, 2, 16, 9, 10, 14, 8, 7]
Step 2: Heapify at index 3 (value = 2)
Left child = 7 → value 14; Right child = 8 → value 8
Max child = 14 at index 7. 2 < 14 → Swap(2, 14)
Array: [4, 1, 3, 14, 16, 9, 10, 2, 8, 7]
Step 3: Heapify at index 2 (value = 3)
Left child = 5 → value 9; Right child = 6 → value 10
Max child = 10 at index 6. 3 < 10 → Swap(3, 10)
Array: [4, 1, 10, 14, 16, 9, 3, 2, 8, 7]
Step 4: Heapify at index 1 (value = 1)
Left child = 3 → value 14; Right child = 4 → value 16
Max child = 16 at index 4. 1 < 16 → Swap(1, 16)
Array: [4, 16, 10, 14, 1, 9, 3, 2, 8, 7]
Now heapify at index 4 (value = 1): Left = 9 → value 7; Right = 10 → out of range
1 < 7 → Swap(1, 7). Array: [4, 16, 10, 14, 7, 9, 3, 2, 8, 1]
Step 5: Heapify at index 0 (value = 4)
Left child = 1 → value 16; Right child = 2 → value 10
Max child = 16 at index 1. 4 < 16 → Swap(4, 16)
Array: [16, 4, 10, 14, 7, 9, 3, 2, 8, 1]
Now heapify at index 1 (value = 4): Left = 3 → value 14; Right = 4 → value 7
4 < 14 → Swap(4, 14). Array: [16, 14, 10, 4, 7, 9, 3, 2, 8, 1]
Heapify at index 3 (value = 4): Left = 7 → value 2; Right = 8 → value 8
4 < 8 → Swap(4, 8). Array: [16, 14, 10, 8, 7, 9, 3, 2, 4, 1]
Final Max-Heap Array: [16, 14, 10, 8, 7, 9, 3, 2, 4, 1]
Max-Heap Tree:
16
/ \
14 10
/ \ / \
8 7 9 3
/\ /
2 4 1
■ Exam Tip: Show every swap step with the array state. The examiner awards marks for intermediate steps.
 ■ | Read before exam — fills
UNIT BONUS · Additional Concepts & conceptual gaps
Important Facts Not in PYQs
Quick Reference: Key Formulas & Facts
Concept Key Fact / Formula

Stack (all ops) push / pop / top / is_empty → all O(1)

Queue (array-based) enqueue / dequeue → O(1) with front/rear pointers

Singly LL: insert front O(1)

Singly LL: insert/delete end O(n) — need traversal

Singly LL: search O(n)

BST: search (avg) O(log n) balanced; O(n) skewed

BST: in-order Always gives sorted ascending sequence

Height-balance check |h(left) - h(right)| ≤ 1 at EVERY node

Max nodes, binary tree height h 2^(h+1) - 1

Min nodes, binary tree height h h + 1 (one node per level)

Heap: node at index i Left child: 2i+1 | Right child: 2i+2 | Parent: (i-1)//2

Heap min elements (height h) 2^h

Heap max elements (height h) 2^(h+1) - 1

Big-O formal definition f(n) = O(g(n)) if ∃ c, n■ > 0 s.t. f(n) ≤ c·g(n) ∀ n ≥ n■

Master Theorem Case 1 f(n) = O(n^(log_b(a)-ε)) → T(n) = Θ(n^log_b(a))

Master Theorem Case 2 f(n) = Θ(n^(log_b(a))) → T(n) = Θ(n^log_b(a) · log n)

Master Theorem Case 3 f(n) = Ω(n^(log_b(a)+ε)) AND regularity → T(n) = Θ(f(n))

Circular Queue: full condition (rear + 1) % size == front

Circular Queue: empty condition front == rear

Infix to Postfix rule Higher/equal precedence pops before pushing new operator

Fibonacci recursion type Binary recursion — 2 recursive calls per invocation

AVL balance factor BF = h(left subtree) - h(right subtree); valid: -1, 0, +1

Guaranteed True/False — Memorise These

Statement Answer Reason

Stack uses FIFO FALSE Stack uses LIFO — Last In First Out

Queue uses LIFO FALSE Queue uses FIFO — First In First Out

In-order BST = sorted sequence TRUE BST property: left < root < right, traversed in order

Doubly LL uses more memory than singly LL TRUE Extra prev pointer per node

Doubly LL uses more memory than circular LL TRUE CLL has only one pointer; DLL has two

Recursive is always more efficient than iterative FALSE Recursion has function call overhead; iterative can be faster

O(n log n) is faster than O(n²) TRUE n log n grows slower than n² for large n
 Master method solves all recurrences FALSE Only works for T(n) = aT(n/b) + f(n) form

Array elements can be different data types FALSE (in typed

Python
languages)
lists can mix types, but arrays (array module) are typed

Time complexity of insertion sort is O(n log n) FALSE Insertion sort is O(n²) worst case; O(n) best case

Concepts Tested in PYQs but Needing Extra Attention

■ BST Delete — 3 Cases
Case 1: Node is a leaf → simply remove it.
Case 2: Node has one child → replace node with its child.
Case 3: Node has two children → find Inorder Successor (smallest in right subtree), copy its value to current
node, delete the inorder successor from its original position.

■ Circular Linked List vs Singly LL

In a Circular LL, the last node's next pointer points back to the first node (head), forming a circle. Key
advantage: can traverse the entire list starting from any node. Disadvantage: need careful termination
condition to avoid infinite loops.

■ Stack Application: Postfix Evaluation

Algorithm: Scan postfix expression left to right. If operand → push to stack. If operator → pop two operands,
apply operator, push result back. Final stack top = answer.

■ Priority Queue Types

Min-Priority Queue: Element with SMALLEST key has highest priority (extracted first). Max-Priority Queue:
Element with LARGEST key has highest priority. Implemented using Binary Heap for O(log n) insert and
extract.

■ Asymptotic Complexity Order (Full)

O(1) < O(log n) < O(√n) < O(n) < O(n log n) < O(n²) < O(n³) < O(2^n) < O(n!)

■ Tree Terminology
Root: topmost node. Leaf: node with no children. Height of tree: longest path from root to leaf. Depth of node:
distance from root. Degree of node: number of children. Height of leaf node = 0. Height of empty tree = -1.

Remember: Unit 2 (Stacks/Queues/Linked Lists) + Unit 4 (Trees/BST) = 65% of the paper. Show all
steps in trace questions. Draw diagrams for BST and Heap. All the best! ■