📘 Data Structures Topics in CLRS 4th Edition

Topic Chapter Chapter Title Page Range

Stacks, Queues, and Lists Chapter 10 Elementary Data Structures pp. 247–266
Hashing Chapter 11 Hash Tables pp. 267–278
Binary Search Trees Chapter 12 Binary Search Trees pp. 279–290
Red-Black Trees Chapter 13 Red-Black Trees pp. 291–314
Heaps & Priority Queues Chapter 6 Heapsort (includes priority queues) pp. 157–181
Graphs Chapter 22 Elementary Graph Algorithms pp. 591–612
Chapter 23 Breadth-First Search pp. 613–628
Chapter 24 Depth-First Search pp. 629–652
Chapter 25 Minimum Spanning Trees pp. 653–676
Chapter 26 Single-Source Shortest Paths pp. 677–720

Notes:

 AVL Trees are not explicitly covered in CLRS 4th edition. You may need to
consult supplemental texts like "Algorithms" by Sedgewick or Weiss's Data
Structures.
 The implementation details of stacks, queues, and lists are foundational and
appear in Chapter 10 with examples using arrays and linked lists.
 Priority queues are handled via heaps, which are fully explored in Chapter 6.
 Graph theory is covered extensively in Chapters 22 through 26, including BFS,
DFS, MSTs, and shortest paths.

Data Structures – Comprehensive Learning Plan

Topics Covered:

1. Stacks
2. Queues
3. Linked Lists
4. Trees (Basic Concepts)
5. Priority Queues & Heaps
6. Hashing
7. Binary Search Trees (BSTs)
8. AVL Trees
 9. Red-Black Trees
10. Graphs

Each topic will include:

 ✅ Clear Definitions
 Operations and Their Complexities
 Visual Intuition (where applicable)
 Applications
 Practice Questions with Answers

Let's start with Topic 1: Stacks

1. Stacks
✅ Definition:

A stack is a linear data structure that follows the LIFO (Last In First Out) principle. The
last element inserted is the first to be removed.

Basic Operations:

Operation Description Time Complexity

push(x) Add element x to the top 𝑂(1)
pop() Remove the top element 𝑂(1)
top() or peek() Return the top element without removing it 𝑂(1)
isEmpty() Check if the stack is empty 𝑂(1)

Applications:

 Function call stack in recursion

 Expression evaluation and syntax parsing
  Undo features in software

Implementation (Array-based Stack - Pseudocode)

procedure push(stack, x)
if top == capacity - 1 then
error "Stack Overflow"
top ← top + 1
stack[top] ← x

procedure pop(stack)
if top == -1 then
error "Stack Underflow"
top ← top - 1

procedure peek(stack)
return stack[top]

Practice Questions

Q1: Suppose we push the following sequence onto a stack: 5, 10, 15, and then pop
twice. What will be the result of the next pop?

✅ Answer:

 Stack after push: [5, 10, 15]

 Pop → 15 (removed)
 Pop → 10 (removed)
 Next Pop → 5

Q2: True or False?

The peek() operation changes the contents of the stack.

✅ Answer:
❌ False — it returns the top element without modifying the stack.

Q3: What is the time complexity of pushing n elements onto an initially empty stack?
✅ Answer:
Each push is 𝑂(1), so for n elements:
Time = ( )

Q4: Trace the following operations on an empty stack:

push(1), push(2), pop(), push(3), peek(), pop(), pop()

Which values are popped, and what is the final state of the stack?

✅ Answer:

 push(1) → [1]
 push(2) → [1, 2]
 pop() → removes 2 → [1]
 push(3) → [1, 3]
 peek() → returns 3
 pop() → removes 3 → [1]
 pop() → removes 1 → []

Final Stack: Empty

Values popped: 2, 3, 1

Q5: Fill in the blanks (True/False):

1. A stack allows insertions and deletions only at the top. → ______

2. Using a stack, we can reverse a sequence efficiently. → ______
3. Stacks use FIFO behavior. → ______
4. The time complexity of accessing the bottom element of a stack is 𝑂(1). →
______

✅ Answers:

1. True
2. True
3. False
4. False (It’s 𝑂( ) if no direct access)

Topic 2: Queues
✅ Definition:
A queue is a linear data structure that follows the FIFO (First In First Out) principle. The
element that is added first is the one removed first.

Basic Operations of a Queue

Operation Description Time Complexity

enqueue(x) Insert an element at the rear 𝑂(1)
dequeue() Remove and return element from front 𝑂(1)
peek() Return the front element 𝑂(1)
isEmpty() Check whether the queue is empty 𝑂(1)

Visual Behavior:

Front → [ A B C D ] ← Rear
dequeue → removes A
enqueue(E) → [ B C D E ]

Applications of Queues

 CPU task scheduling

 Breadth-First Search (BFS) in graphs
 Print queues, keyboard buffer
 Simulation systems

Array-based Queue (Pseudocode)

procedure enqueue(Q, x)
if rear == capacity - 1 then
error "Queue Overflow"
rear ← rear + 1
Q[rear] ← x

procedure dequeue(Q)
if front > rear then
error "Queue Underflow"
x ← Q[front]
front ← front + 1
return x
Note: To make it more efficient, we often implement queues as circular arrays or linked
lists to avoid unused space.

Practice Questions – Queues

Q1: What is the result of the following queue operations on an empty

queue?

enqueue(10), enqueue(20), dequeue(), enqueue(30), dequeue()

✅ Answer:

 enqueue(10) → [10]
 enqueue(20) → [10, 20]
 dequeue() → removes 10 → [20]
 enqueue(30) → [20, 30]
 dequeue() → removes 20 → [30]

Final state: [30]

Values dequeued: 10, 20

Q2: True or False?

1. A queue supports both LIFO and FIFO behavior. → ______

2. The peek() operation changes the content of the queue. → ______
3. A queue is best suited for breadth-first search. → ______
4. A circular queue helps avoid unused memory. → ______

✅ Answers:

1. ❌ False
2. ❌ False
3. ✅ True
4. ✅ True
 Q3: Which data structure would you choose for each task?

Task Stack / Queue

Web browser back button Stack
Print jobs sent to a printer Queue
Undo operation in a text editor Stack
CPU job scheduling (round robin) Queue

✅ Answers: As listed in the second column.

Topic 3: Linked Lists

✅ Definition:

A linked list is a linear data structure where each element (called a node) contains:

 Data
 A reference (pointer) to the next node in the sequence

It is dynamic in size and ideal for frequent insertions/deletions.

Types of Linked Lists

Type Description
Singly Linked List Nodes point to the next node only
Each node points to both next and previous
Doubly Linked List
nodes
Circular Linked List Last node points back to the first, forming a circle

Basic Operations

Operation Description Time Complexity

insertAtBeginning(x) Insert x at head 𝑂(1)
insertAtEnd(x) Insert x at tail (without tail pointer: O(n)) 𝑂(1) or 𝑂( )
Operation Description Time Complexity
delete(x) Delete node with value x 𝑂( )
search(x) Find node with value x 𝑂( )

Singly Linked List Node (Pseudocode)

class Node
data
next

procedure insertAtBeginning(head, x)
newNode ← new Node(x)
newNode.next ← head
head ← newNode

📘 Example:

Let's build a list:

insertAtBeginning(5)
insertAtBeginning(10)
insertAtEnd(20)

Linked list becomes:

10 → 5 → 20 → NULL

Practice Questions – Linked Lists

Q1: Given the list head → 3 → 7 → 12 → NULL, what happens after

insertAtBeginning(1)?

✅ Answer:
New list: head → 1 → 3 → 7 → 12 → NULL

Q2: Suppose you want to delete node with value 7 in a singly linked list.
What must you know?
✅ Answer:
You need a pointer to the previous node (with value 3) to adjust its next pointer to skip
7.

Q3: Fill in the blanks:

1. The time complexity of inserting at the head of a singly linked list is ______
2. Searching for an element in a linked list is ______
3. A circular list connects the last node to the ______

✅ Answers:

1. 𝑂(1)
2. 𝑂( )
3. First node / Head

Q4: True or False?

1. Linked lists are better than arrays when insertions are frequent. → ______
2. A doubly linked list uses less memory than a singly linked list. → ______
3. It is easy to access the middle of a linked list in 𝑂(1) time. → ______
4. Each node in a doubly linked list has two pointers. → ______

✅ Answers:

1. ✅ True
2. ❌ False
3. ❌ False
4. ✅ True

Topic 4: Trees

✅ Definition:

A tree is a hierarchical data structure consisting of nodes, with the following

characteristics:
  One node is designated as the root.
 Every node (except root) has one parent.
 Nodes may have zero or more children.

Basic Terminology

Term Description
Root Topmost node
Parent A node that has children
Child A node connected below its parent
Leaf A node with no children
Subtree A tree formed by a node and its descendants
Height Longest path from node to a leaf
Depth Number of edges from root to the node

Types of Trees

Type Description
Binary Tree Each node has ≤ 2 children
Binary Search Tree (BST) Binary tree with left < root < right
Full Binary Tree Every node has 0 or 2 children
Complete Binary Tree All levels full except possibly last
Balanced Tree Height of left and right subtrees differ by ≤ 1

Basic Operations on Binary Trees

Operation Description Time Complexity

Insert Add new node 𝑂(ℎ)
Search Find a value 𝑂(ℎ)
Delete Remove a node 𝑂(ℎ)
Traversal Visit all nodes 𝑂(ℎ)

Where h = height of the tree, n = number of nodes

 Tree Traversals
Type Order
In-order Left → Root → Right (BST → sorted output)
Pre-order Root → Left → Right
Post-order Left → Right → Root
Level-order Breadth-first using a queue

📘 Example: Binary Tree

10
/ \
5 15
/\ \
2 7 20

 In-order traversal: 2, 5, 7, 10, 15, 20

 Pre-order traversal: 10, 5, 2, 7, 15, 20

Practice Questions – Trees

Q1: Given the binary tree above, what is the result of a post-order
traversal?

✅ Answer:
Post-order: 2, 7, 5, 20, 15, 10

Q2: Fill in the blanks:

1. The in-order traversal of a BST gives nodes in ______ order.

2. A node with no children is called a ______.
3. In a binary tree, each node has at most ______ children.

✅ Answers:
 1. Sorted
2. Leaf
3. 2

Q3: True or False?

1. A tree can have multiple roots. → ______

2. Pre-order traversal always visits the root first. → ______
3. Height of a tree with 1 node is 1. → ______
4. Level-order traversal uses a stack. → ______

✅ Answers:

1. ❌ False
2. ✅ True
3. ❌ False (It’s 0)
4. ❌ False (It uses a queue)

Topic 5: Priority Queues & Heaps

✅ What is a Priority Queue?

A priority queue is an abstract data type where:

 Each element has a priority.

 Elements are served based on priority, not just insertion order.
 Higher priority elements are dequeued before lower priority ones.

Unlike standard queues (FIFO), priority queues allow dynamic ordering.

✅ What is a Heap?

A heap is a binary tree-based data structure that satisfies the heap property and is
commonly used to implement priority queues.

There are two main types:

Heap Type Property
Max-Heap Parent ≥ Children (highest priority at root)
Min-Heap Parent ≤ Children (lowest priority at root)

Characteristics of a Binary Heap

 It is a complete binary tree: filled from left to right.

 Stored efficiently in an array, not pointers.

Indexing in an array-based heap:

If node is at index i:

 Left child = 2i
 Right child = 2i + 1
 Parent = ⌊i / 2⌋

Operations on a Heap (Min or Max)

Time
Operation Description
Complexity
insert(x) Add new element & restore heap 𝑂(log⁡ )
extractMin() or extractMax() Remove root element 𝑂(log⁡ )
heapify() Convert array to heap 𝑂( )
buildHeap() Build heap from unordered array 𝑂( )

📘 Example: Max-Heap (Array Representation)

Heap as Tree: Heap as Array:

50 [50, 30, 40, 10, 20, 35, 25]
/ \
30 40
/\ /\
10 20 35 25

Applications of Heaps
  Priority queues
 Heap sort
 Graph algorithms (e.g., Dijkstra, Prim)
 Median maintenance

Practice Questions – Heaps & Priority Queues

Q1: What will the array look like after inserting 60 into this max-heap?

Current heap array: [50, 30, 40, 10, 20, 35, 25]

✅ Answer:

 Insert 60 at the end → [50, 30, 40, 10, 20, 35, 25, 60]
 Bubble up (swap with 10, then 30, then 50) → [60, 50, 40, 30, 20, 35, 25, 10]

Q2: Fill in the blanks

1. A min-heap has the ______ value at the root.

2. In a complete binary tree with n nodes, height is ______.
3. The operation extractMax() in a max-heap takes ______ time.

✅ Answers:

1. Minimum
2. 𝑂(log⁡ )
3. 𝑂(log⁡ )

Q3: True or False?

1. A heap is a binary search tree. → ______

2. In a min-heap, every parent's value is ≤ its children. → ______
3. Heapify is faster than repeatedly calling insert. → ______
4. Max-heaps can be used for ascending order heap sort. → ______
✅ Answers:

1. ❌ False
2. ✅ True
3. ✅ True
4. ✅ True

Topic 6: Hashing

✅ Definition:

Hashing is a technique used to map data (keys) to fixed-size values called hash codes,
which are typically used as indexes in a hash table for efficient access.

Hash Table:

A hash table is a data structure that offers:

 Average-case time complexity: O(1) for insertion, deletion, and search.

 It uses a hash function to compute an index for storing data.

Hash Function

A hash function converts a key into an index:

index = hash(key) mod table_size

A good hash function distributes keys uniformly to minimize collisions.

Collisions in Hashing
A collision happens when two keys map to the same index.

Collision Resolution Techniques

Method Description
Chaining Store multiple elements at the same index using a linked list
Open Addressing Find another slot using probing strategies

Open Addressing Strategies

Strategy Formula
Linear Probing ℎ( , ) = (ℎ( ) + )mod
Quadratic Probing ℎ( , ) = (ℎ( ) + 1 + 2 2 )mod
Double Hashing ℎ( , ) = (ℎ1 ( ) + ⋅ ℎ2 ( ))mod

Hashing Time Complexity

Operation Average Case Worst Case (with collisions)

Insert 𝑂(1) 𝑂( )
Search 𝑂(1) 𝑂( )
Delete 𝑂(1) 𝑂( )

Practice Questions – Hashing

Q1: Suppose you use a hash function h(k) = k mod 10 and your table size is 10.

What index will the key 27 be inserted at?

✅ Answer:
27mod 10 = 7 → Insert at index 7

Q2: Fill in the blanks:

1. A good hash function distributes keys ______ across the table.

2. Chaining stores collided elements using a ______.
3. The main problem hashing solves is ______.
✅ Answers:

1. Uniformly
2. Linked List
3. Fast lookup (or searching)

Q3: True or False?

1. Open addressing requires a secondary hash function. → ______

2. Hashing guarantees 𝑂(1) time in all cases. → ______
3. In chaining, each slot of the hash table points to a linked list. → ______

✅ Answers:

1. ✅ True (for double hashing)

2. ❌ False
3. ✅ True

Q4: Which collision resolution strategy is most resistant to clustering?

A. Linear probing
B. Quadratic probing
C. Double hashing
D. Chaining

✅ Answer:
C. Double hashing

Topic 7: Binary Search Trees (BST)

✅ Definition:

A Binary Search Tree (BST) is a binary tree where each node has the following property:

For any node x:

  All nodes in its left subtree contain values < x
 All nodes in its right subtree contain values > x

BST Operations & Their Time Complexities

Operation Description Best/Average Case Worst Case

Search(x) Locate a node with value x 𝑂(log⁡ ) 𝑂( )
Insert(x) Insert a node 𝑂(log⁡ ) 𝑂( )
Delete(x) Remove a node 𝑂(log⁡ ) 𝑂( )
Traverse() Visit nodes (in-order = sorted) 𝑂( ) 𝑂( )

Worst case occurs when the tree is unbalanced, e.g., resembling a linked list.

Example: BST Insertion

Insert: 15, 10, 20, 8, 12

15
/ \
10 20
/ \
8 12

 In-order traversal (Left → Root → Right) gives: 8, 10, 12, 15, 20 (sorted)

BST Deletion Cases

To delete a node:

1. Leaf node: remove directly.

2. One child: bypass the node.
3. Two children:
o Replace with in-order successor (min value in right subtree)
o Or in-order predecessor (max value in left subtree)
 Pseudocode: Insert in BST

function insert(node, key)

if node is NULL
return newNode(key)
if key < node.key
node.left = insert(node.left, key)
else
node.right = insert(node.right, key)
return node

Practice Questions – BST

Q1: Insert the following keys into an empty BST: 25, 15, 50, 10, 22, 35, 70

What is the in-order traversal of the tree?

✅ Answer:
In-order: 10, 15, 22, 25, 35, 50, 70

Q2: Fill in the blanks:

1. In a BST, in-order traversal gives ______ values.

2. In the worst case, the height of a BST is ______.
3. Deleting a node with two children requires finding its ______ or ______.

✅ Answers:

1. Sorted
2. 𝑂( )
3. In-order successor or predecessor

Q3: True or False?

1. In a BST, every node must have two children. → ______

2. The smallest element in a BST is the leftmost leaf. → ______
3. Insertion in a BST can be done iteratively or recursively. → ______
 4. BSTs are always balanced. → ______

✅ Answers:

1. ❌ False
2. ✅ True
3. ✅ True
4. ❌ False

Topic 8: AVL Trees (Self-Balancing Binary Search Trees)

✅ What is an AVL Tree?

An AVL tree is a self-balancing binary search tree where the difference in height
(balance factor) between left and right subtrees for any node is at most 1.

Named after its inventors Adelson-Velsky and Landis (AVL).

Balance Factor (BF)

For any node:

Balance Factor = Height(left) − Height(right)

 If BF ∈ {−1, 0, +1} → Balanced

 If |BF| > 1 → Unbalanced → requires rotation

Rotations in AVL Trees

Rotations are used to restore balance after insertion or deletion.

Single Rotations

Type Description
Left Rotation (LL) Heavy on left-left side
Type Description
Right Rotation (RR) Heavy on right-right side

Double Rotations

Type Description
Left-Right (LR) Heavy on left-right → rotate left then right
Right-Left (RL) Heavy on right-left → rotate right then left

📘 Example

Insert the following into an AVL Tree: 30, 20, 10

 After inserting 30 → tree = 30

 Insert 20 → becomes left child
 Insert 10 → causes left-left (LL) imbalance
✅ Apply Right Rotation at 30

Result:

20
/ \
10 30

AVL Tree Operations

Operation Time Complexity

Insert 𝑂(log⁡ )
Delete 𝑂(log⁡ )
Search 𝑂(log⁡ )

Always 𝑂(log⁡ ) due to height-balancing

Pros and Cons

✅ Advantages:

 Fast and guaranteed logarithmic time

  Ensures optimal height

Disadvantages:

 Rotations add overhead during insert/delete

 More complex than regular BST

Practice Questions – AVL Trees

Q1: Which rotation is required after inserting 30, 20, 10 into an AVL tree?

✅ Answer:
Right Rotation (LL Case)

Q2: Fill in the blanks:

1. An AVL tree maintains balance by using ______.

2. The time complexity of insertion in an AVL tree is ______.
3. Balance factor must lie between ______ and ______.

✅ Answers:

1. Rotations
2. 𝑂(log⁡ )
3. −1 and +1

Q3: True or False?

1. AVL trees guarantee O(1) search time. → ______

2. Double rotations are more complex than single rotations. → ______
3. Every AVL tree is a BST. → ______

✅ Answers:

1. ❌ False
 2. ✅ True
3. ✅ True

⚫ Topic 9: Red-Black Trees

✅ What is a Red-Black Tree (RBT)?

A Red-Black Tree is a self-balancing binary search tree where each node contains an
extra bit for color (either Red or Black). It ensures balance through coloring and
rotations, guaranteeing 𝑂(log⁡ ) time complexity.

Red-Black Tree Properties

To maintain balance, RBTs follow 5 essential rules:

1. Every node is either red or black.

2. The root is always black.
3. All leaves (NIL nodes) are black.
4. If a node is red, its children must be black. (No two red nodes in a row)
5. Every path from a node to its descendant NIL nodes has the same number of
black nodes.

These properties guarantee that the longest path from the root to a leaf is no more than
twice as long as the shortest path.

Red-Black Tree Rotations

Just like AVL trees, RBTs use rotations to maintain balance.

 Left Rotation
 Right Rotation

They also include recoloring as part of balancing after insertion or deletion.

Time Complexities
Operation Time Complexity
Search 𝑂(log⁡ )
Insert 𝑂(log⁡ )
Delete 𝑂(log⁡ )

Insertion in RBT (High-Level Steps)

1. Insert the node as in a BST.
2. Color the new node red.
3. Fix violations of RBT properties using:
o Recoloring
o Rotations (left or right)

AVL vs Red-Black Trees

Feature AVL Tree Red-Black Tree
Balance Factor Strict (height difference ≤ 1) Less strict (color-based)
Rotations More frequent Less frequent
Lookup Speed Faster (more balanced) Slightly slower
Insertion/Deletion Slower (due to rebalancing) Faster
Use Case Read-heavy Write-heavy (OS, DB)

Practice Questions – Red-Black Trees

Q1: True or False?

1. A red-black tree can have two red nodes consecutively. → ______

2. Every AVL tree is a red-black tree. → ______
3. All leaves in a red-black tree are black. → ______
4. Red-black trees are more balanced than AVL trees. → ______

✅ Answers:

1. ❌ False
 2. ❌ False
3. ✅ True
4. ❌ False

Q2: Fill in the blanks:

1. The root of a red-black tree is always ______.

2. A red-black tree guarantees a height of at most ______ times the logarithm of
the number of nodes.
3. The color red in RBT allows ______ balance enforcement.

✅ Answers:

1. Black
2. 2
3. Flexible / Lazy

Q3: Match the Rotation Need

Insertion Sequence Rotation Required

10, 5, 1 Right Rotation
10, 20, 30 Left Rotation
10, 5, 8 Left-Right Rotation
10, 20, 15 Right-Left Rotation

✅ Answers:
As listed

Topic 10: Graphs

✅ What is a Graph?

A graph is a collection of:

 Vertices (or nodes)

  Edges (connections between nodes)

Graphs are used to model relationships and networks, such as roads, social networks, or
web links.

Types of Graphs

Type Description
Undirected Edges have no direction
Directed (Digraph) Edges have direction (A → B ≠ B → A)
Weighted Edges have weights or costs
Unweighted Edges are equal in value
Cyclic Contains at least one cycle
Acyclic No cycles (e.g., DAG = Directed Acyclic Graph)
Connected Path exists between every pair of nodes
Disconnected Some nodes are unreachable from others

Graph Representations

1. Adjacency Matrix – 2D array of size ×

o Space: 𝑂( 2 )
o Fast edge lookup
2. Adjacency List – Array of lists (each node points to list of neighbors)
o Space: 𝑂( + )
o Efficient for sparse graphs

Graph Traversal Algorithms

Time
Algorithm Type Description
Complexity
BFS Breadth-First Search Level-by-level using a queue 𝑂( + )
DFS Depth-First Search Depth-first using a stack (or recursion) 𝑂( + )

Applications of Graphs
  Social network analysis
 Routing and navigation (e.g., GPS)
 Dependency resolution (e.g., build systems)
 Web crawling and link analysis
 Network flow, scheduling

📘 Example – Graph (Undirected)

Graph:

A–B–C
| \
D E

Adjacency List:

A: B, D
B: A, C, E
C: B
D: A
E: B

Practice Questions – Graphs

Q1: What is the time complexity of BFS on a graph with n vertices and e
edges?

✅ Answer:
𝑂( + )

Q2: Fill in the blanks:

1. A graph with no cycles is called a ______.

2. DFS uses a ______ data structure internally.
3. An edge with direction is called a ______ edge.

✅ Answers:
 1. DAG (Directed Acyclic Graph)
2. Stack
3. Directed

Q3: True or False?

1. An adjacency matrix is efficient for dense graphs. → ______

2. BFS always uses recursion. → ______
3. DFS explores all neighbors of a node before moving deeper. → ______
4. In an undirected graph, edges go both ways. → ______

✅ Answers:

1. ✅ True
2. ❌ False
3. ❌ False
4. ✅ True

Q4: Graph Representation Matching

Graph Scenario Use which representation?

Dense graph with many connections Adjacency matrix
Sparse graph like road networks Adjacency list
Fast edge lookup is required Adjacency matrix
Memory-efficient representation Adjacency list

✅ Answers:
As listed

✅ Comprehensive MCQ & True/False Questions on Data

Structures

1. Stacks
MCQ 1:
Which of the following operations can be performed on a stack?
A. enqueue, dequeue
B. push, pop
C. insert, delete at end
D. traverse, peek at middle

✅ Answer: B. push, pop

TF 1:
In a stack, the last element inserted is the first to be removed.
✅ Answer: True

2. Queues

MCQ 2:
Which data structure allows insertion at one end and deletion from the other?
A. Stack
B. Array
C. Queue
D. Tree

✅ Answer: C. Queue

TF 2:
A circular queue helps in optimizing space usage.
✅ Answer: True

3. Linked Lists

MCQ 3:
Which of the following is true about singly linked lists?
A. They allow backward traversal
B. They waste memory
C. Each node stores data and a pointer to the next node
D. Insertion is always O(n)

✅ Answer: C. Each node stores data and a pointer to the next node
TF 3:
Doubly linked lists are more memory efficient than singly linked lists.
✅ Answer: False

4. Trees

MCQ 4:
What is the in-order traversal of a BST with nodes inserted in the order 10, 5, 15?
A. 10, 5, 15
B. 5, 10, 15
C. 15, 10, 5
D. 5, 15, 10

✅ Answer: B. 5, 10, 15

TF 4:
A binary tree is always a binary search tree.
✅ Answer: False

5. Priority Queues & Heaps

MCQ 5:
What is the time complexity of inserting into a binary heap?
A. O(1)
B. O(n)
C. O(log n)
D. O(n log n)

✅ Answer: C. O(log n)

TF 5:
In a max-heap, the smallest value is always at the root.
✅ Answer: False

6. Hashing
MCQ 6:
Which of these is a common collision resolution strategy?
A. Merging
B. Probing
C. Sorting
D. Balancing

✅ Answer: B. Probing

TF 6:
Open addressing and chaining are two methods to resolve collisions.
✅ Answer: True

7. Binary Search Trees (BST)

MCQ 7:
What is the worst-case time complexity of search in an unbalanced BST?
A. O(1)
B. O(log n)
C. O(n)
D. O(n log n)

✅ Answer: C. O(n)

TF 7:
In-order traversal of a BST always gives sorted output.
✅ Answer: True

8. AVL Trees

MCQ 8:
What is the maximum balance factor in an AVL tree?
A. 0
B. 1
C. 2
D. ∞

✅ Answer: B. 1
TF 8:
AVL trees may require multiple rotations after insertion.
✅ Answer: True

9. Red-Black Trees

MCQ 9:
Which of the following is not a red-black tree property?
A. Every node is either red or black
B. The tree is always height-balanced
C. Red nodes must have red children
D. All leaves (NILs) are black

✅ Answer: C. Red nodes must have red children (❌ it's the opposite)

TF 9:
The root of a red-black tree must always be black.
✅ Answer: True

10. Graphs

MCQ 10:
Which representation is best for sparse graphs?
A. Adjacency Matrix
B. Adjacency List
C. Incidence Matrix
D. List of Edges

✅ Answer: B. Adjacency List

TF 10:
Depth-first search uses a queue for traversal.
✅ Answer: False (uses stack)

Here's a large set of advanced graduate-level questions on all 10 data structure topics.
These questions are designed to test deep understanding, critical thinking, and
algorithmic application. Each question includes the correct answer or explanation.
 Advanced Graduate-Level Questions on Data
Structures

1. Stacks

Q1:
You are implementing a browser with Back and Forward buttons. Which data structures
are most appropriate to manage navigation history efficiently?

A. Queue
B. Stack and Queue
C. Two Stacks
D. Single Deque

✅ Answer: C. Two Stacks

One stack for Back, another for Forward.

Q2:
Given a stack with nnn elements, what is the minimum number of stack operations
(push, pop, peek) required to reverse it using only one additional stack?

✅ Answer: 𝑂( 2
)

Due to repeated transfers between stacks without using extra space.

2. Queues

Q3:
A circular queue has a front at position 2 and rear at position 6 in a size-10 array. How
many elements are currently in the queue?

✅ Answer: 5

Rear ≥ Front → count = rear - front + 1 = 6 − 2 + 1 = 5

Q4:
Which of the following queue implementations is ideal for scheduling algorithms in an
operating system?

A. Priority Queue
B. Deque
C. Circular Queue
D. FIFO Queue

✅ Answer: A. Priority Queue

Scheduling often depends on priority (not pure FIFO).

3. Linked Lists

Q5:
You want to delete the last node of a singly linked list in 𝑂(1) time. What modification is
necessary?

✅ Answer: Maintain a tail pointer and a previous pointer to the last node.

Otherwise, you need 𝑂( ) traversal.

Q6:
Which type of linked list is most efficient for implementing a deque?

A. Singly Linked List

B. Circular Linked List
C. Doubly Linked List
D. Array

✅ Answer: C. Doubly Linked List

Allows insert/delete at both ends in 𝑂(1).

4. Trees
Q7:
Prove or disprove: A binary tree with n internal nodes has exactly n + 1 leaves.

✅ Answer: True (for full binary trees)

Use structural induction or the formula: L = I + 1.

Q8:
What is the average depth of a node in a perfectly balanced binary tree of height hhh?

✅ Answer: 𝑂(log⁡ )

Tree depth grows logarithmically with number of nodes.

5. Heaps & Priority Queues

Q9:
How do you merge two binary heaps (max-heaps) efficiently?

A. Rebuild from scratch

B. Insert all elements from one into the other
C. Use a tournament tree
D. Use binomial heap or Fibonacci heap structure

✅ Answer: D. Use binomial or Fibonacci heap

Standard binary heaps don’t support efficient merging; others do.

Q10:
When inserting into a min-heap, under what condition is no bubbling required?

✅ Answer: When the new element is ≥ parent

Heap property holds, no need to bubble up.

6. Hashing
Q11:
In open addressing with linear probing, what is primary clustering, and how can it be
reduced?

✅ Answer:
Primary clustering refers to long runs of occupied slots causing poor performance.
Use quadratic probing or double hashing to mitigate it.

Q12:
Assuming a load factor α=0.75\alpha = 0.75α=0.75, what is the expected number of
probes in successful search under open addressing?

✅ Answer:

1 1 1 1
(1+1 − ) = (1+ ) = 2.5
2 2 0.25

7. Binary Search Trees (BST)

Q13:
Prove that the maximum number of comparisons for an unsuccessful search in a BST
with n nodes is h + 1, where h is the height.

✅ Answer:
True. Every unsuccessful search ends at a NULL pointer after traversing h + 1 nodes at
most.

Q14:
Which sequence of inserts produces the worst-case height in a BST?

A. Sorted ascending
B. Random
C. Balanced
D. Sorted alternating ends

✅ Answer: A. Sorted ascending

Leads to skewed tree (like a linked list).

 8. AVL Trees

Q15:
Insert 1, 2, 3 into an AVL tree. How many rotations are needed?

✅ Answer: One rotation

Right rotation (LL case)

Q16:
What is the maximum number of rotations required during a single insertion in an AVL
tree?

✅ Answer: 2 rotations

At most one double rotation.

9. Red-Black Trees

Q17:
What is the maximum height of a Red-Black Tree with n nodes?

✅ Answer:

2⁡log 2 ( + 1)

Due to relaxed balancing rules.

Q18:
During insertion into a red-black tree, how many nodes may require recoloring?

✅ Answer:
Up to ( ⁡ )

Traversal back to root may involve multiple recolorings.

 10. Graphs

Q19:
Which of the following statements about BFS and DFS is correct?

A. Both always visit all vertices

B. DFS uses a queue, BFS uses recursion
C. BFS guarantees shortest path in unweighted graphs
D. DFS is better for shortest path

✅ Answer: C. BFS guarantees shortest path in unweighted graphs

Q20:
Which graph representation is most efficient for computing in-degree and out-degree?

✅ Answer: Adjacency list

Can compute both efficiently; in-degree may need reverse edges or secondary data.

📘 Data Structures Summary Review Sheet

1. Stack
 Definition: LIFO (Last-In First-Out) data structure.
 Operations: push(x), pop(), peek(), isEmpty()
 Time Complexity: All operations 𝑂(1)
 Use Cases: Expression evaluation, backtracking, undo functionality
 Implementation: Array or Linked List

2. Queue
 Definition: FIFO (First-In First-Out) structure.
 Types: Simple Queue, Circular Queue, Double-Ended Queue (Deque), Priority
Queue
 Operations: enqueue(x), dequeue(), peek(), isEmpty()
 Time Complexity: All 𝑂(1)
 Use Cases: Scheduling, buffering, BFS traversal

3. Linked List
 Types:
o Singly Linked List (SLL)
o Doubly Linked List (DLL)
o Circular Linked List
 Operations: Insertion, deletion, traversal
 Time Complexity: Insertion/deletion at head 𝑂(1), at tail or middle 𝑂( )
 Use Cases: Dynamic memory allocation, implementing stacks, queues

4. Trees
 Binary Tree: Each node has up to 2 children
 Binary Search Tree (BST):
o Left < Root < Right
o In-order traversal yields sorted order
 Time Complexity:
o Insert/Search/Delete: Avg 𝑂(log⁡ ), Worst 𝑂( )

5. Priority Queues & Heaps

 Heap: Complete binary tree
o Max Heap: Root ≥ children
o Min Heap: Root ≤ children
 Operations:
o insert(x): 𝑂(log⁡ )
o extract-max / extract-min: 𝑂(log⁡ )
 Use Cases: Priority queues, scheduling, Dijkstra’s algorithm
6. Hashing
 Hash Table: Maps keys to indices
 Hash Function: ℎ( ) = mod
 Collision Resolution:
o Chaining: Linked list per bucket
o Open Addressing:
 Linear, Quadratic, Double Hashing
 Time Complexity:
o Average: 𝑂(1)
o Worst: 𝑂( )

7. Binary Search Trees (BST)

 Structure: Left < Root < Right
 Traversals:
o In-order: Sorted output
o Pre/Post-order: Tree structure
 Complexities:
o Avg: 𝑂(log⁡ ), Worst (unbalanced): 𝑂( )

8. AVL Trees
 Self-balancing BST
 Balance Factor ∈ {−1, 0, +1}
 Rotations: LL, RR, LR, RL
 Time Complexity: All operations 𝑂(log⁡ )
 Use Cases: Read-intensive apps requiring balanced trees

⚫ 9. Red-Black Trees
 Properties:
o Root is black
o Red node → black children
o Uniform black height
 Rotations & Recoloring to maintain balance
  Time Complexity: 𝑂(log⁡ ) for all operations
 Use Cases: Write-optimized systems (Linux kernel, databases)

10. Graphs
 Components: Nodes (vertices), Edges
 Types: Directed/Undirected, Weighted/Unweighted, Cyclic/Acyclic
 Representations:
o Adjacency List: 𝑂( + )
o Adjacency Matrix: 𝑂( 2 )
 Traversals:
o BFS (Queue): Level-wise
o DFS (Stack/Recursion): Depth-first
 Use Cases: Networking, social networks, compilers, scheduling

Let's now explore algorithms applied to data structures, categorized by type. Each
section includes brief theory, example, and complexity analysis. We'll cover:

1. Traversal Algorithms
2. Sorting Algorithms
3. Searching Algorithms
4. Graph Algorithms (Bonus)

1. Traversal Algorithms
✅ A. Tree Traversals

Method Order Use Cases

In-order Left → Root → Right BST: sorted output
Pre-order Root → Left → Right Expression trees, cloning trees
Post-order Left → Right → Root Deleting trees, expression eval
Level-order Level-by-level (uses queue) BFS-like traversal

Example (In-order):

10
 / \
5 15

➡ In-order: 5 10 15

Time Complexity: 𝑂( )
Space: 𝑂(ℎ) for recursion stack (h = height)

✅ B. Graph Traversals

 BFS: Breadth-first Search (Queue-based)

 DFS: Depth-first Search (Stack/Recursion)

Use Cases:

 BFS: Shortest path in unweighted graphs

 DFS: Topological sort, detecting cycles

Time Complexity: 𝑂( + )
Space: 𝑂( )

2. Sorting Algorithms
✅ A. Comparison-based

Algorithm Time Complexity Notes

Bubble Sort 𝑂( 2 ) Simple, inefficient
Insertion Sort 𝑂( 2 ), best 𝑂( ) Good for small/sorted data
Merge Sort 𝑂( log⁡ ) Stable, good for linked lists
2
Quick Sort Avg 𝑂( log⁡ ), worst 𝑂( ) Fast, but not stable
Heap Sort 𝑂( log⁡ ) In-place, not stable

✅ B. Non-Comparison (Linear Time)

Algorithm Time Use Case

Counting Sort 𝑂( + ) Small range of integers
Algorithm Time Use Case
Radix Sort 𝑂( ) Digits-based sorting
2
Bucket Sort 𝑂( + / + ) Uniformly distributed data

3. Searching Algorithms
✅ A. Array-based

Method Time Complexity Notes

Linear Search 𝑂( ) No sorting needed
Binary Search 𝑂(log⁡ ) Requires sorted array

✅ B. Tree-based

Structure Avg Case Worst Case

BST 𝑂(log⁡ ) 𝑂( ) (skewed tree)
AVL/Red-Black 𝑂(log⁡ ) Always balanced

✅ C. Hash-based

Operation Avg Case Worst Case

Hash Table Search 𝑂(1) 𝑂( ) (collision chains)

4. Graph Algorithms (Bonus)

Algorithm Use Case Time Complexity
Dijkstra's Shortest path (non-negative edges) 𝑂( log⁡ + )
Bellman-Ford Shortest path (handles negatives) 𝑂( )
Kruskal's Minimum Spanning Tree (MST) 𝑂( log⁡ )
Prim's MST using priority queue 𝑂( + log⁡ )
Topological Sort DAG ordering 𝑂( + )
Floyd-Warshall All-pairs shortest paths 𝑂( 3 )
Below is a curated problem set with detailed solutions for algorithms related to:

1. Tree Traversals
2. Sorting
3. Searching
4. Graph Algorithms

1. Tree Traversals
Problem 1:

Given the following binary tree:

A
/\
B C
/\ \
D E F

Q: What is the in-order, pre-order, and post-order traversal?

✅ Solution:

 In-order (Left, Root, Right): D, B, E, A, C, F

 Pre-order (Root, Left, Right): A, B, D, E, C, F
 Post-order (Left, Right, Root): D, E, B, F, C, A

Problem 2:

Implement level-order traversal using a queue.

✅ Solution in pseudocode:

function levelOrder(root):
if root == null: return
queue = new Queue()
queue.enqueue(root)
while not queue.isEmpty():
node = queue.dequeue()
print(node.value)
if node.left: queue.enqueue(node.left)
if node.right: queue.enqueue(node.right)
 2. Sorting Algorithms
Problem 3:

Sort the list [9, 5, 2, 8, 1] using Merge Sort.

✅ Solution (steps):

 Split: [9, 5], [2, 8], [1]

 Sort: [5, 9], [2, 8], [1]
 Merge: [2, 5, 8, 9], then [1, 2, 5, 8, 9]

➡ Final output: [1, 2, 5, 8, 9]

Time Complexity: 𝑂( log⁡ )

Problem 4:

Which sorting algorithm is stable and in-place?

✅ Answer: Insertion Sort is stable and in-place

(others: Merge Sort is stable but not in-place)

3. Searching Algorithms
Problem 5:

Given a sorted array:

arr = [2, 5, 8, 12, 16, 23, 38]
Search for 23 using Binary Search.

✅ Solution (binary search steps):

 mid = 3 → arr[3] = 12 → 23 > 12

 mid = 5 → arr[5] = 23 → Match found

Time: 𝑂(log⁡ )
Problem 6:

Explain how search is performed in a hash table with chaining.

✅ Answer:

 Compute hash(key) % table_size

 Follow the linked list at that index
 Traverse the list to find matching key

Avg Time: 𝑂(1), Worst: 𝑂( )

4. Graph Algorithms
Problem 7:

Given this undirected graph:

A -- B
| |
D -- C

Perform BFS traversal starting from node A.

✅ Solution:

 Queue: A
 Visit: A → B → D → C

Traversal order: A, B, D, C

Problem 8:

Find shortest path from A to E using Dijkstra’s algorithm:

Edges: A→B(1), A→C(4), B→C(2), B→D(5), C→D(1), D→E(3)

✅ Steps:
  Start from A: dist[A] = 0
 Update neighbors: B=1, C=4
 B next: update C=3, D=6
 C next: update D=4
 D next: update E=7

➡ Final distances: A=0, B=1, C=3, D=4, E=7

Here's a set of graduate-level problem sets on advanced data structure algorithms,

each with a detailed solution, targeting deep conceptual understanding and real-world
applications.

Advanced Graduate-Level Problem Set with Solutions

1. Tree Traversals & Applications

Problem 1:

Given the post-order and in-order traversals of a binary tree:

 Post-order: D, E, B, F, C, A
 In-order: D, B, E, A, F, C

Q: Reconstruct the tree.

✅ Solution:

 Last post-order element = Root = A

 In in-order: [D, B, E] → left subtree, [F, C] → right subtree
 Recursively repeat the process:

Final Tree:

A
/\
B C
/\ /
D EF
 2. Sorting with Constraints

Problem 2:

You are given an array of 10 million integers in the range [0, 1000].
Q: Design an optimal sorting algorithm.

✅ Solution:

 Use Counting Sort since the range is small and integers are non-negative.
 Time Complexity: 𝑂( + ) = 𝑂(107 + 103 )

Problem 3:

Why can’t comparison-based sorts outperform 𝑂( log⁡ ) in worst-case time?

✅ Solution:

 Decision-tree argument: There are ! possible orderings.

 Minimum height of binary decision tree is log⁡2 ( !) = Ω( log⁡ )

3. Searching & Indexing

Problem 4:

Design a search structure for real-time streaming logs that allows:

 𝑂(log⁡ ) insertions
 𝑂(log⁡ ) range queries
 Sorted traversal in 𝑂( )

✅ Solution: Use a Self-Balancing BST (AVL or Red-Black Tree)

  Insert: 𝑂(log⁡ )
 Range query: traverse subtree between bounds
 Sorted traversal: in-order

Problem 5:

You have a hash table with open addressing. What is the expected number of probes in
an unsuccessful search if the load factor is 0.9?

✅ Solution:
Using linear probing:

1 1
[unsuccessful probes] = = = 10
1− 1 − 0.9

4. Graph Algorithms

Problem 6:

Given a directed acyclic graph (DAG), design an algorithm to find all possible
topological sorts.

✅ Solution:

 Use Backtracking + DFS

 Maintain visited array and in-degree counts
 At each step, try all nodes with in-degree 0
 Recurse and backtrack

Time Complexity: 𝑂( ⋅ ), where k is number of topological orders

Problem 7:

Prove or disprove: Dijkstra’s algorithm fails when graph has negative edge weights,
even if no negative cycles exist.
✅ Answer: True

Example:

A → B (weight = 2)
A → C (weight = 1)
C → B (weight = -2)

Dijkstra will finalize A→B before discovering A→C→B is shorter.

Problem 8:

You need to find the minimum spanning tree of a dense graph with 1000 nodes and
495,000 edges. Choose the best algorithm.

✅ Solution:

 Use Prim's algorithm with a Fibonacci heap

 Time: 𝑂( + log⁡ ) — better for dense graphs