Introduction to Data Structures using C

Foundations of Efficient Programming

Dr. Dheeraj Kodati

Assistant Professor
IIITM Gwalior

January 1, 2026

Dr. Dheeraj Kodati (Assistant Professor IIITM Gwalior) Data Structures January 1, 2026 1 / 13
 What is a Data Structure?

A data structure is a way of organizing and storing data efficiently.

Enables fast access, modification, and processing of data.
Essential for writing optimized and scalable programs.

Dr. Dheeraj Kodati (Assistant Professor IIITM Gwalior) Data Structures January 1, 2026 2 / 13
 Why Study Data Structures?

Improves program efficiency and performance.

Helps solve complex real-world problems.
Forms the backbone of software systems.
Essential for interviews and competitive programming.

Dr. Dheeraj Kodati (Assistant Professor IIITM Gwalior) Data Structures January 1, 2026 3 / 13
 Role of C in Data Structures

Provides low-level memory control.

Helps understand pointers and memory allocation.
Ideal for implementing core data structures.

Dr. Dheeraj Kodati (Assistant Professor IIITM Gwalior) Data Structures January 1, 2026 4 / 13
 Basic Types of Data Structures

Primitive
int, char, float, double

Non-Primitive
Arrays, Linked Lists, Stacks, Queues, Trees, Graphs

Dr. Dheeraj Kodati (Assistant Professor IIITM Gwalior) Data Structures January 1, 2026 5 / 13
 Linear Data Structures

Array
Linked List
Stack
Queue

Dr. Dheeraj Kodati (Assistant Professor IIITM Gwalior) Data Structures January 1, 2026 6 / 13
 Non-Linear Data Structures

Trees
Binary Search Trees
Graphs
Heaps

Dr. Dheeraj Kodati (Assistant Professor IIITM Gwalior) Data Structures January 1, 2026 7 / 13
 Program Correctness and Efficiency

Correctness ensures accurate results.

Efficiency focuses on time and space usage.
Big-O notation is used for analysis.

Dr. Dheeraj Kodati (Assistant Professor IIITM Gwalior) Data Structures January 1, 2026 8 / 13
 Searching Techniques

Linear Search
Binary Search
Hash-based Searching

Dr. Dheeraj Kodati (Assistant Professor IIITM Gwalior) Data Structures January 1, 2026 9 / 13
 Sorting Techniques

Bubble Sort
Selection Sort
Insertion Sort
Merge and Quick Sort

Dr. Dheeraj Kodati (Assistant Professor IIITM Gwalior) Data Structures January 1, 2026 10 / 13
 Applications of Data Structures

Operating Systems
Databases
Compiler Design
Machine Learning and AI

Dr. Dheeraj Kodati (Assistant Professor IIITM Gwalior) Data Structures January 1, 2026 11 / 13
 About the Instructor

Dr. Dheeraj Kodati

Assistant Professor, IIITM Gwalior
Research: NLP, Explainable AI, Mental Health, Bioinformatics
Guides UG, PG, and PhD students
Focus on practical learning and research-driven teaching

Dr. Dheeraj Kodati (Assistant Professor IIITM Gwalior) Data Structures January 1, 2026 12 / 13
 Thank You

Dr. Dheeraj Kodati (Assistant Professor IIITM Gwalior) Data Structures January 1, 2026 13 / 13
Comprehensive Python Programming
Foundations of Python

Dr. Dheeraj Kodati, Ph.D.

February 2026
Lecture Roadmap

1. Fundamentals & Basic Syntax

2. Advanced Data Structures
3. Functional Programming & Comprehensions
4. Error Handling & File I/O
5. Object-Oriented Programming (OOP)
6. Advanced Patterns (Decorators/Generators)
7. Introduction to NumPy & Pandas

1
1. Why Python for Research?

• High-Level: Abstracted memory management (GC).

• Interpreted: Immediate feedback loop via REPL/Jupyter.
• Extensible: C/C++ backends for heavy computation (NumPy).
• Standards: PEP 8 style guide for collaborative research.

2
2. Dynamic Typing & Variables

# No explicit declaration needed

age = 35 # Integer
pi = 3.14159 # Float
research_area = " NLP " # String

# Multiple Assignment
a , b , c = 5 , 10 , 15

# Type checking at runtime

print ( type ( research_area ) )

3
3. String Interpolation (f-Strings)

name = " Dheeraj "

role = " Researcher "

# Modern f - strings ( Python 3.6+)

msg = f " Hello , I am { name } , working as a { role }. "

# Expressions inside strings

val = 10
print ( f " Result : { val * 2} " ) # Result : 20

4
4. Conditional Logic

status = " Admin "

if status == " Admin " :
print ( " Full Access " )
elif status == " User " :
print ( " Limited Access " )
else :
print ( " Access Denied " )

# Ternary Operator
result = " Pass " if 85 > 40 else " Fail "

5
5. Iteration: For Loops

# Iterating over a range

for i in range (0 , 10 , 2) : # Start , Stop , Step
print ( i ) # 0 , 2 , 4 , 6 , 8

# Iterating over a list

frameworks = [ " PyTorch " , " TensorFlow " , " Keras " ]
for fx in frameworks :
print ( fx . upper () )

6
6. Iteration: While Loops

count = 5
while count > 0:
print ( f " Countdown : { count } " )
count -= 1 # No count - - in Python

# break and continue

for x in range (10) :
if x == 5: break # Stops loop
if x % 2 == 0: continue # Skips iteration

7
7. Lists: The Workhorse

data = [10 , 20 , 30 , 40]

data . append (50)
data [0] = 99 # Mutable

# Slicing [ start : stop : step ]

print ( data [1:3]) # [20 , 30]
print ( data [:: -1]) # Reverse list

8
8. Tuples & Sets

# Tuples : Immutable ( Fast , Safe )

coordinates = (12.97 , 77.59)

# Sets : Unordered , Unique elements only

tags = { " AI " , " ML " , " AI " , " NLP " }
print ( tags ) # { ’ AI ’, ’ ML ’, ’ NLP ’}

# Set operations
A = {1 , 2 , 3}; B = {3 , 4 , 5}
print ( A | B ) # Union {1 , 2 , 3 , 4 , 5}

9
9. Dictionaries (JSON-like)

paper = {
" title " : " Explainable AI " ,
" year " : 2024 ,
" citations " : 150
}

print ( paper [ " title " ])

paper [ " authors " ] = [ " Kodati , D . " ]
print ( paper . keys () )

10
10. List Comprehensions

# Traditional way
evens = []
for x in range (10) :
if x % 2 == 0:
evens . append ( x **2)

# Pythonic way
evens = [ x **2 for x in range (10) if x % 2 == 0]

11
11. Functions & Default Arguments

def greet ( name , msg = " Welcome " ) :

return f " { msg } , { name }! "

print ( greet ( " Students " ) )

print ( greet ( " Dheeraj " , " Good Morning " ) )

# Variable number of arguments

def add_all (* args ) :
return sum ( args )

12
12. Lambda & Functional Tools

# Lambda : Anonymous functions

multiply = lambda x , y : x * y

# Map and Filter

nums = [1 , 2 , 3 , 4]
squared = list ( map ( lambda x : x **2 , nums ) )

13
13. Global vs Local Scope

x = 100 # Global

def func () :
global x
x = 200 # Modifies global variable
y = 50 # Local

func ()
print ( x ) # 200

14
14. OOP: Classes and Objects

class Agent :
def __init__ ( self , name , task ) :
self . name = name # Attribute
self . task = task

def run ( self ) : # Method

return f " { self . name } is performing { self . task } "

bot = Agent ( " ResearchBot " , " NLP Sifting " )

print ( bot . run () )

15
15. OOP: Inheritance

class LLM ( Agent ) :

def __init__ ( self , name , task , params ) :
super () . __init__ ( name , task )
self . params = params

def get_info ( self ) :

return f " { self . name } has { self . params } B parameters . "

16
16. Robust Error Handling

try :
with open ( " config . json " ) as f :
data = f . read ()
except F i leN otF oun dErr o r :
print ( " Error : File missing . " )
except Exception as e :
print ( f " Unexpected error : { e } " )

17
17. Generators (Memory Efficient)

# Generator function using ’ yield ’

def co u nt_to_million () :
n = 1
while n <= 1000000:
yield n
n += 1

gen = c o unt_to_million ()
print ( next ( gen ) ) # 1

18
18. Decorators

def my_decorator ( func ) :

def wrapper () :
print ( " Before function call " )
func ()
print ( " After function call " )
return wrapper

@my_decorator
def say_hello () :
print ( " Hello ! " )

19
19. Intro to NumPy (Numerical Python)

import numpy as np

arr = np . array ([1 , 2 , 3 , 4])

print ( arr * 2) # Vectorized operation : [2 , 4 , 6 , 8]

matrix = np . zeros ((3 , 3) )

print ( matrix . shape ) # (3 , 3)

20
Thank you

Thank You!
Email: dheeraj@[Link]

21
 Program Correctness and Analysis
Data Structures and Algorithms

Dr. Dheeraj

Assistant Professor
ABV-IIITM Gwalior

February 2026

Dr. Dheeraj Assistant Professor ABV-IIITM Gwalior

Program Correctness and Analysis
The Core Question

We know an algorithm works for some cases.

How do we know it works for EVERY case?
In mission-critical systems (AI in Healthcare, Space Tech), ”usually
works” is not enough.
Program Correctness is the mathematical proof that an algorithm
satisfies its specification.

Dr. Dheeraj Assistant Professor ABV-IIITM Gwalior

Program Correctness and Analysis
The Contract: Pre-conditions and Post-conditions

Think of an algorithm as a legal contract:

The ”If-Then” Rule
If the input meets the Pre-condition (P),
Then the output must meet the Post-condition (Q).

Real-world Example: Bank Withdrawal

P: Account balance ≥ Requested amount.
Q: New balance = Old balance - Requested amount.

Dr. Dheeraj Assistant Professor ABV-IIITM Gwalior

Program Correctness and Analysis
Hoare Logic Foundations

Developed by C.A.R. Hoare, we use the ”Hoare Triple”:

{P} S {Q}

{P}: Pre-condition
S: The Code/Statement
{Q}: Post-condition

If we start in a state where P is true and execute S, we end in a state

where Q is true.

Dr. Dheeraj Assistant Professor ABV-IIITM Gwalior

Program Correctness and Analysis
Partial vs. Total Correctness

1 Partial Correctness: If the program finishes, the answer is right. (It

might run forever, though!)
2 Total Correctness: Partial Correctness + Termination.

Infinite Loop Example

while(true) { print("Hello"); }
This can be partially correct but is never totally correct because it never
terminates.

Dr. Dheeraj Assistant Professor ABV-IIITM Gwalior

Program Correctness and Analysis
Loop Invariants: The ”Bridge” over Loops

A Loop Invariant is a statement about the variables that stays true before
and after every iteration.
The Analogy: Think of climbing a ladder. Your ”invariant” is that
your hands are always on a rung. Whether you are at the bottom,
middle, or top, that truth never changes.

Dr. Dheeraj Assistant Professor ABV-IIITM Gwalior

Program Correctness and Analysis
The Three Steps of Invariant Proof

To prove a loop is correct, you must show:

1 Initialization: It is true before the loop starts.
2 Maintenance: If it is true before iteration k, it remains true before
iteration k + 1.
3 Termination: When the loop ends, the invariant + the exit
condition = Proof of correctness.

Dr. Dheeraj Assistant Professor ABV-IIITM Gwalior

Program Correctness and Analysis
Example: Sum of First n Numbers

sum ← 0, i ← 1
while i ≤ n do
sum ← sum + i
i ←i +1
end while
Pi−1
Invariant: At the start of each loop, sum = j=1 j.
At Termination: i = n + 1.
Pn
Therefore, sum = j=1 j. (Correct!)

Dr. Dheeraj Assistant Professor ABV-IIITM Gwalior

Program Correctness and Analysis
Algorithm Analysis: Why Math?

We don’t measure ”seconds” because computers vary.

We measure the number of basic operations.
We focus on the Rate of Growth as input size n goes to infinity.

Dr. Dheeraj Assistant Professor ABV-IIITM Gwalior

Program Correctness and Analysis
Big-O: The ”Worst-Case” Safety Net

Formal: f (n) = O(g (n)) if f (n) ≤ c · g (n) for large n.

Easy Example: Finding a name in a phonebook. If there are n
names, and you check them one by one, it’s O(n).

Dr. Dheeraj Assistant Professor ABV-IIITM Gwalior

Program Correctness and Analysis
Common Complexities at a Glance

Big-O Name Example

O(1) Constant Accessing array index
O(log n) Logarithmic Binary Search
O(n) Linear Linear Search
O(n2 ) Quadratic Bubble Sort

Dr. Dheeraj Assistant Professor ABV-IIITM Gwalior

Program Correctness and Analysis
The Other Bounds

Big-Omega (Ω): The Best-Case (Lower bound). ”It will take at

least this much time.”
Big-Theta (Θ): The Tight Bound. ”It takes exactly this rate of
growth.”

Analogy
If a car’s top speed is 200 km/h:
O(200): Speed is ≤ 200.
Ω(10): Speed is ≥ 10 (it’s moving).
Θ(x): The car is cruising at exactly x.

Dr. Dheeraj Assistant Professor ABV-IIITM Gwalior

Program Correctness and Analysis
DS Operations Analysis

Array Access: O(1)

Linked List Search: O(n)
Balanced BST Search: O(log n)
Choice of DS depends on which operation (insert/delete/search) you do
most often.

Dr. Dheeraj Assistant Professor ABV-IIITM Gwalior

Program Correctness and Analysis
How to Analyze Code Quickly

Loops: A loop running n times is O(n).

Nested Loops: A loop inside a loop is O(n2 ).
Divide and Conquer: If you split the problem in half each time
(like Binary Search), it is usually O(log n).
Drop Constants: O(2n + 5) is just O(n).

Dr. Dheeraj Assistant Professor ABV-IIITM Gwalior

Program Correctness and Analysis
Conclusion

Correctness ensures your code is trustworthy.

Analysis ensures your code is scalable.

Questions?

Dr. Dheeraj Assistant Professor ABV-IIITM Gwalior

Program Correctness and Analysis
Lecture-3, Introduction to Abstract Data Types

January 6, 2026

Lecture-3, Introduction to Abstract Data Types January 6, 2026 1 / 20

Learning Objectives

After this lecture, students will be able to:

Understand the concept of Abstract Data Types (ADT)
Distinguish ADTs from data structures
Identify common ADTs and their operations
Write pseudo-code for basic ADT operations
Apply ADTs in problem-solving

Lecture-3, Introduction to Abstract Data Types January 6, 2026 2 / 20

What is a Data Type?

Definition
A Data Type defines:
The type of data
The operations allowed on that data

Examples:
Integer: addition, subtraction
Character: comparison, assignment

Lecture-3, Introduction to Abstract Data Types January 6, 2026 3 / 20

Motivation for ADTs

Large programs become difficult to manage

Mixing data representation and logic reduces clarity
Code maintenance becomes complex

Key Idea
ADT separates what an operation does from how it is implemented.

Lecture-3, Introduction to Abstract Data Types January 6, 2026 4 / 20

Abstract Data Type (ADT)

Definition
An Abstract Data Type is a mathematical model that defines:
A set of values
A set of operations on those values

Focus: Logical behavior, not physical storage.

Lecture-3, Introduction to Abstract Data Types January 6, 2026 5 / 20

ADT vs Data Structure

ADT Data Structure

Logical model Physical representation
Defines operations Implements operations
Stack, Queue Array, Linked List

Lecture-3, Introduction to Abstract Data Types January 6, 2026 6 / 20

Common Abstract Data Types

Stack
Queue
List
Deque
Set
Map (Dictionary)

Lecture-3, Introduction to Abstract Data Types January 6, 2026 7 / 20

Stack ADT

Definition
A Stack is an ADT that follows the LIFO principle.

Operations:
push()
pop()
peek()
isEmpty()

Lecture-3, Introduction to Abstract Data Types January 6, 2026 8 / 20

Stack ADT – Push Operation

Pseudo Code

PUSH(stack, item):
[Link] ← [Link] + 1
stack[[Link]] ← item

Example Output
Input: PUSH(10), PUSH(20)
Stack Content: [10, 20]

Lecture-3, Introduction to Abstract Data Types January 6, 2026 9 / 20

Stack ADT – Pop Operation

Pseudo Code

POP(stack):
if [Link] == -1:
return "Stack Underflow"
item ← stack[[Link]]
[Link] ← [Link] - 1
return item

Example Output
Stack before: [10, 20]
POP()
Output: 20
Stack after: [10]

Lecture-3, Introduction to Abstract Data Types January 6, 2026 10 / 20

Queue ADT

Definition
A Queue is an ADT that follows the FIFO principle.

Operations:
enqueue()
dequeue()
front()
isEmpty()

Lecture-3, Introduction to Abstract Data Types January 6, 2026 11 / 20

Queue ADT – Enqueue Operation

Pseudo Code

ENQUEUE(queue, item):
[Link] ← [Link] + 1
queue[[Link]] ← item

Example Output
ENQUEUE(5), ENQUEUE(15)
Queue Content: [5, 15]

Lecture-3, Introduction to Abstract Data Types January 6, 2026 12 / 20

Queue ADT – Dequeue Operation

Pseudo Code

DEQUEUE(queue):
if [Link] > [Link]:
return "Queue Empty"
item ← queue[[Link]]
[Link] ← [Link] + 1
return item

Example Output
Queue before: [5, 15]
DEQUEUE()
Output: 5
Queue after: [15]

Lecture-3, Introduction to Abstract Data Types January 6, 2026 13 / 20

List ADT

Definition
A List is an ordered collection of elements.
Operations:
insert(position, element)
delete(position)
retrieve(position)
size()

Lecture-3, Introduction to Abstract Data Types January 6, 2026 14 / 20

List ADT – Insert Operation

Pseudo Code

INSERT(list, pos, item):

for i ← [Link] down to pos:
list[i+1] ← list[i]
list[pos] ← item

Example Output
List before: [1, 2, 4]
INSERT(3, 3)
List after: [1, 2, 3, 4]

Lecture-3, Introduction to Abstract Data Types January 6, 2026 15 / 20

Advantages of ADTs

Improves modularity
Enhances code reusability
Simplifies maintenance
Implementation independent

Lecture-3, Introduction to Abstract Data Types January 6, 2026 16 / 20

Applications of ADTs

Stack: Function calls, expression evaluation

Queue: CPU scheduling, buffering
List: Dynamic data storage

Lecture-3, Introduction to Abstract Data Types January 6, 2026 17 / 20

Practice Problems

1 Write pseudo-code to check balanced parentheses using Stack ADT.

2 Implement Queue ADT using two stacks.
3 Explain insert and delete operations of List ADT.
4 Describe how Stack ADT is used in recursion.
5 Compare Stack ADT and Queue ADT with examples.

Lecture-3, Introduction to Abstract Data Types January 6, 2026 18 / 20

Summary

ADT defines logical behavior

Implementation details are hidden
Stack, Queue, and List are fundamental ADTs

Lecture-3, Introduction to Abstract Data Types January 6, 2026 19 / 20

 Thank You

Lecture-3, Introduction to Abstract Data Types January 6, 2026 20 / 20

 Arrays in Data Structures
IT102 – Data Structures

Dr. Dheeraj Kodati

IIITM Gwalior

Dr. Dheeraj Kodati (IIITM Gwalior) Arrays in Data Structures 1 / 10

What is an Array?

An array is a collection of similar data elements

Stored in continuous memory locations
Accessed using index values
Example:
Marks = {85, 90, 78, 92, 88}

Dr. Dheeraj Kodati (IIITM Gwalior) Arrays in Data Structures 2 / 10

Array Declaration

Syntax:
data type array name[size]
Example:
int marks[5];

Dr. Dheeraj Kodati (IIITM Gwalior) Arrays in Data Structures 3 / 10

Array Initialization in C

int marks [5] = {85 , 90 , 78 , 92 , 88};

Dr. Dheeraj Kodati (IIITM Gwalior) Arrays in Data Structures 4 / 10

Accessing Array Elements

# include < stdio .h >

int main () {
int marks [5] = {85 , 90 , 78 , 92 , 88};
printf ( " % d " , marks [2]) ;
return 0;
}

Output:
78

Dr. Dheeraj Kodati (IIITM Gwalior) Arrays in Data Structures 5 / 10

Traversing an Array

# include < stdio .h >

int main () {
int i ;
int a [5] = {10 , 20 , 30 , 40 , 50};

for ( i = 0; i < 5; i ++) {

printf ( " % d " , a [ i ]) ;
}
return 0;
}

Output:
10 20 30 40 50

Dr. Dheeraj Kodati (IIITM Gwalior) Arrays in Data Structures 6 / 10

Insertion in an Array

# include < stdio .h >

int main () {
int a [10] = {10 , 20 , 30 , 40 , 50};
int n = 5 , i , pos = 2 , value = 25;

for ( i = n ; i > pos ; i - -) {

a [ i ] = a [ i - 1];
}

a [ pos ] = value ;
n ++;

for ( i = 0; i < n ; i ++) {

printf ( " % d ␣ " , a [ i ]) ;
}
return 0;
}

Output:
10 20 25 30 40 50

Dr. Dheeraj Kodati (IIITM Gwalior) Arrays in Data Structures 7 / 10

Deletion from an Array

# include < stdio .h >

int main () {
int a [5] = {10 , 20 , 30 , 40 , 50};
int i , pos = 2;

for ( i = pos ; i < 4; i ++) {

a [ i ] = a [ i + 1];
}

for ( i = 0; i < 4; i ++) {

printf ( " % d " , a [ i ]) ;
}
return 0;
}

Output:
10 20 40 50
Dr. Dheeraj Kodati (IIITM Gwalior) Arrays in Data Structures 8 / 10
Practice Questions

1 Write a C program to find the sum of array elements.

2 Write a C program to find the largest element.
3 Write a C program to reverse an array.
4 Write a C program to search an element using linear search.

Dr. Dheeraj Kodati (IIITM Gwalior) Arrays in Data Structures 9 / 10

 Thank You

Dr. Dheeraj Kodati (IIITM Gwalior) Arrays in Data Structures 10 / 10

 Data Structures
Lists (Linked Lists)-Lecture 4

Dr. Dheeraj

Lecture Slides

January 8, 2026

Dr. Dheeraj (Lecture Slides) Data Structures January 8, 2026 1 / 18

Outline

1 Introduction to Lists
2 Array vs Linked List
3 Linked List Concept
4 Singly Linked List
5 Traversal Operation
6 Insertion Operations
7 Deletion Operation
8 Time Complexity
9 Advantages and Disadvantages
10 Practice Questions

Dr. Dheeraj (Lecture Slides) Data Structures January 8, 2026 2 / 18

What is a List?

A list is a linear data structure.

Elements are stored in a sequence.
Each element has a unique position.
Example:
[10, 20, 30, 40]

Dr. Dheeraj (Lecture Slides) Data Structures January 8, 2026 3 / 18

Types of Lists

Array List
Singly Linked List
Doubly Linked List
Circular Linked List

Dr. Dheeraj (Lecture Slides) Data Structures January 8, 2026 4 / 18

Array vs Linked List

Feature Array Linked List

Memory Contiguous Non-contiguous
Size Fixed Dynamic
Insertion Costly Easy
Deletion Costly Easy
Access Fast Slow

Dr. Dheeraj (Lecture Slides) Data Structures January 8, 2026 5 / 18

What is a Linked List?

A linked list is a collection of nodes.

Each node has:
Data
Address of next node
Nodes are connected using pointers.

Dr. Dheeraj (Lecture Slides) Data Structures January 8, 2026 6 / 18

Node Structure

|Data| → |Next|
Note: The last node always points to NULL.

Dr. Dheeraj (Lecture Slides) Data Structures January 8, 2026 7 / 18

Singly Linked List

Each node points to the next node.

Traversal is only in forward direction.
Example:
10 → 20 → 30 → NULL

Dr. Dheeraj (Lecture Slides) Data Structures January 8, 2026 8 / 18

Traversal Algorithm

Goal: Visit and print all nodes.

temp = head
while temp != NULL
print [Link]
temp = [Link]

Output:
10 20 30

Dr. Dheeraj (Lecture Slides) Data Structures January 8, 2026 9 / 18

Insertion at Beginning

Steps:
Create new node
Point new node to head
Update head

[Link] = head
head = new

Example:
Before:
10 → 20
After:
5 → 10 → 20

Dr. Dheeraj (Lecture Slides) Data Structures January 8, 2026 10 / 18

Insertion at End

Steps:
Traverse to last node
Attach new node

temp = head
while [Link] != NULL
temp = [Link]
[Link] = new
[Link] = NULL

Result:
10 → 20 → 30

Dr. Dheeraj (Lecture Slides) Data Structures January 8, 2026 11 / 18

Insertion at Given Position

Insert at position = 2

temp = head
for i = 1 to pos-1
temp = [Link]
[Link] = [Link]
[Link] = new

Example:
10 → 15 → 20

Dr. Dheeraj (Lecture Slides) Data Structures January 8, 2026 12 / 18

Deletion of a Node

Steps:
Search the node
Adjust links
Free memory

temp = head
prev = NULL
while [Link] != key
prev = temp
temp = [Link]
[Link] = [Link]

Output: Node with given value is deleted.

Dr. Dheeraj (Lecture Slides) Data Structures January 8, 2026 13 / 18

Time Complexity of Operations

Traversal: O(n)
Insertion at beginning: O(1)
Insertion at end: O(n)
Deletion: O(n)

Dr. Dheeraj (Lecture Slides) Data Structures January 8, 2026 14 / 18

Advantages of Linked List

Dynamic size
Easy insertion and deletion
Efficient memory usage

Dr. Dheeraj (Lecture Slides) Data Structures January 8, 2026 15 / 18

Disadvantages of Linked List

Extra memory for pointers

No direct access
Slower traversal

Dr. Dheeraj (Lecture Slides) Data Structures January 8, 2026 16 / 18

Practice Questions

1 Write an algorithm to traverse a linked list.

2 Insert 25 at position 3 in: 5 → 10 → 20 → NULL.
3 Write pseudocode to delete the first node.
4 What happens when the last node is deleted?
5 Compare array and linked list with an example.

Dr. Dheeraj (Lecture Slides) Data Structures January 8, 2026 17 / 18

 Thank You

Dr. Dheeraj (Lecture Slides) Data Structures January 8, 2026 18 / 18

 Data Structures
Types of Lists-Lecture 04-5

Dr. Dheeraj

Lecture Slides

January 8, 2026

Dr. Dheeraj (Lecture Slides) Data Structures January 8, 2026 1 / 17

Outline

1 Introduction
2 Types of Lists
3 Array List
4 Singly Linked List
5 Doubly Linked List
6 Circular Singly Linked List
7 Circular Doubly Linked List
8 Comparison
9 Practice Questions

Dr. Dheeraj (Lecture Slides) Data Structures January 8, 2026 2 / 17

What is a List?

A list is a linear data structure.

Elements are arranged sequentially.
Each element has a logical relationship with others.
General Example:
10, 20, 30, 40

Dr. Dheeraj (Lecture Slides) Data Structures January 8, 2026 3 / 17

Main Types of Lists

1 Array List
2 Singly Linked List
3 Doubly Linked List
4 Circular Singly Linked List
5 Circular Doubly Linked List

Dr. Dheeraj (Lecture Slides) Data Structures January 8, 2026 4 / 17

Array List

Elements stored in contiguous memory.

Fixed size.
Direct access using index.
Example:
A[0] = 10, A[1] = 20, A[2] = 30

Dr. Dheeraj (Lecture Slides) Data Structures January 8, 2026 5 / 17

Array List – Traversal

for i = 0 to n-1
print A[i]

Output:
10 20 30

Dr. Dheeraj (Lecture Slides) Data Structures January 8, 2026 6 / 17

Singly Linked List

Each node contains data and next pointer.

Traversal only in forward direction.
Example:
10 → 20 → 30 → NULL

Dr. Dheeraj (Lecture Slides) Data Structures January 8, 2026 7 / 17

Singly Linked List – Traversal

temp = head
while temp != NULL
print [Link]
temp = [Link]

Output:
10 20 30

Dr. Dheeraj (Lecture Slides) Data Structures January 8, 2026 8 / 17

Doubly Linked List

Each node has three fields:

Previous pointer
Data
Next pointer
Traversal possible in both directions.
Example:
NULL ← 10 ↔ 20 ↔ 30 → NULL

Dr. Dheeraj (Lecture Slides) Data Structures January 8, 2026 9 / 17

Doubly Linked List – Forward Traversal

temp = head
while temp != NULL
print [Link]
temp = [Link]

Output:
10 20 30

Dr. Dheeraj (Lecture Slides) Data Structures January 8, 2026 10 / 17

Circular Singly Linked List

Last node points to first node.

No NULL pointer.
Useful in round-robin scheduling.
Example:
10 → 20 → 30 → 10

Dr. Dheeraj (Lecture Slides) Data Structures January 8, 2026 11 / 17

Circular Singly Linked List – Traversal

temp = head
do
print [Link]
temp = [Link]
while temp != head

Output:
10 20 30

Dr. Dheeraj (Lecture Slides) Data Structures January 8, 2026 12 / 17

Circular Doubly Linked List

Combination of doubly and circular list.

No NULL pointers.
Efficient two-way circular traversal.
Example:
10 ↔ 20 ↔ 30 ↔ 10

Dr. Dheeraj (Lecture Slides) Data Structures January 8, 2026 13 / 17

Circular Doubly Linked List – Traversal

temp = head
do
print [Link]
temp = [Link]
while temp != head

Output:
10 20 30

Dr. Dheeraj (Lecture Slides) Data Structures January 8, 2026 14 / 17

Comparison of List Types

List Type NULL Pointer Traversal

Array List No Direct
Singly Linked List Yes One-way
Doubly Linked List Yes Two-way
Circular Singly List No One-way (circular)
Circular Doubly List No Two-way (circular)

Dr. Dheeraj (Lecture Slides) Data Structures January 8, 2026 15 / 17

Practice Questions

1 Write pseudocode to traverse a singly linked list.

2 Convert an array list into a singly linked list.
3 What is the advantage of circular linked lists?
4 Write an algorithm to insert a node in a doubly linked list.
5 Compare singly and doubly linked lists with examples.

Dr. Dheeraj (Lecture Slides) Data Structures January 8, 2026 16 / 17

 Thank You

Dr. Dheeraj (Lecture Slides) Data Structures January 8, 2026 17 / 17

 Stacks in Data Structures-lecture-4

Dr. Dheeraj, Assistant professor, IIITM

Dr. Dheeraj, Assistant professor, IIITM Stacks in Data Structures-lecture-4 1 / 20

Outline

Introduction to Stack
Stack Operations
Stack Implementation
Algorithms (Push, Pop, Peek)
Examples with Output
Problem Solving Examples
Practice Questions

Dr. Dheeraj, Assistant professor, IIITM Stacks in Data Structures-lecture-4 2 / 20

What is a Stack?

Stack is a linear data structure

Follows LIFO principle (Last In First Out)
Insertion and deletion happen at one end called TOP

Dr. Dheeraj, Assistant professor, IIITM Stacks in Data Structures-lecture-4 3 / 20

Real-Life Examples

Stack of plates
Undo/Redo operations
Function calls (Call Stack)

Dr. Dheeraj, Assistant professor, IIITM Stacks in Data Structures-lecture-4 4 / 20

Basic Stack Operations

Push – Insert element

Pop – Delete element
Peek / Top – View top element
isEmpty – Check if stack is empty
isFull – Check if stack is full

Dr. Dheeraj, Assistant professor, IIITM Stacks in Data Structures-lecture-4 5 / 20

Stack Representation

Stack can be implemented using:

Array
Linked List
TOP pointer indicates top element

Dr. Dheeraj, Assistant professor, IIITM Stacks in Data Structures-lecture-4 6 / 20

Push Operation – Algorithm

Algorithm 1 Push Operation

1: if TOP == MAX-1 then
2: Print ”Stack Overflow”
3: else
4: TOP = TOP + 1
5: STACK[TOP] = ITEM
6: end if

Dr. Dheeraj, Assistant professor, IIITM Stacks in Data Structures-lecture-4 7 / 20

Push Operation – Example

Initial Stack: [10, 20]

TOP = 1
Push 30
TOP becomes 2
Stack becomes [10, 20, 30]
Output: 30 inserted successfully

Dr. Dheeraj, Assistant professor, IIITM Stacks in Data Structures-lecture-4 8 / 20

Pop Operation – Algorithm

Algorithm 2 Pop Operation

1: if TOP == -1 then
2: Print ”Stack Underflow”
3: else
4: ITEM = STACK[TOP]
5: TOP = TOP - 1
6: end if

Dr. Dheeraj, Assistant professor, IIITM Stacks in Data Structures-lecture-4 9 / 20

Pop Operation – Example

Initial Stack: [10, 20, 30]

TOP = 2
Pop Operation
Removed element = 30
TOP becomes 1
Output: 30 deleted successfully

Dr. Dheeraj, Assistant professor, IIITM Stacks in Data Structures-lecture-4 10 / 20

Peek Operation – Algorithm

Algorithm 3 Peek Operation

1: if TOP == -1 then
2: Print ”Stack is Empty”
3: else
4: Print STACK[TOP]
5: end if

Dr. Dheeraj, Assistant professor, IIITM Stacks in Data Structures-lecture-4 11 / 20

Stack Using Array – Summary

Fixed size
Faster access
Possible overflow

Dr. Dheeraj, Assistant professor, IIITM Stacks in Data Structures-lecture-4 12 / 20

Stack Using Linked List – Summary

Dynamic size
No overflow (until memory full)
Extra memory for pointers

Dr. Dheeraj, Assistant professor, IIITM Stacks in Data Structures-lecture-4 13 / 20

Problem 1: Reverse a String

Input: ABCD
Steps:
Push A, B, C, D
Pop elements
Output: DCBA

Dr. Dheeraj, Assistant professor, IIITM Stacks in Data Structures-lecture-4 14 / 20

Problem 2: Check Balanced Parentheses

Input: (a+b)*(c-d)
Logic:
Push opening bracket
Pop on closing bracket
Output: Balanced

Dr. Dheeraj, Assistant professor, IIITM Stacks in Data Structures-lecture-4 15 / 20

Problem 3: Infix to Postfix Conversion

Input: A+B*C
Output: ABC*+

Dr. Dheeraj, Assistant professor, IIITM Stacks in Data Structures-lecture-4 16 / 20

Time Complexity

Push – O(1)
Pop – O(1)
Peek – O(1)

Dr. Dheeraj, Assistant professor, IIITM Stacks in Data Structures-lecture-4 17 / 20

Common Errors

Stack Overflow
Stack Underflow
Forgetting to update TOP

Dr. Dheeraj, Assistant professor, IIITM Stacks in Data Structures-lecture-4 18 / 20

Practice Questions

1 Implement stack using array

2 Reverse a number using stack
3 Evaluate postfix expression
4 Find minimum element in stack

Dr. Dheeraj, Assistant professor, IIITM Stacks in Data Structures-lecture-4 19 / 20

Conclusion

Stack is simple and powerful

Used in many real-world problems
Foundation for recursion and expressions

Dr. Dheeraj, Assistant professor, IIITM Stacks in Data Structures-lecture-4 20 / 20

 Expression Conversions Using Stack

Dr. Dheeraj

Dr. Dheeraj Expression Conversions Using Stack 1 / 30

Operator Precedence and Associativity

Operator Precedence Table (Highest to Lowest)

No. Operator Description Associativity
1 ( , [ , {} ) Parentheses (Round, Square, Curly) N/A
2 ˆ Exponentiation Right to Left
3 *,/ Multiplication, Division Left to Right
4 +,- Addition, Subtraction Left to Right

Parentheses have the highest precedence; expressions inside them are

evaluated first.
Exponentiation ˆis next and is right-to-left associative.
Multiplication ‘*‘ and Division ‘/‘ come next (left-to-right).
Addition ‘+‘ and Subtraction ‘-‘ have the lowest precedence
(left-to-right).

Dr. Dheeraj Expression Conversions Using Stack 2 / 30

Infix to Postfix – Example

Convert the following infix expression:

A + (B ∗ C − D)/E

Dr. Dheeraj Expression Conversions Using Stack 3 / 30

Infix to Postfix – Detailed Stack Solution

Scanned Stack Postfix

A – A
+ + A
( +( A
B +( AB
* +(* AB
C +(* ABC
- +(- ABC*
D +(- ABC*D
) + ABC*D-
/ +/ ABC*D-
E +/ ABC*D-E
End – ABC*D-E/+

Dr. Dheeraj Expression Conversions Using Stack 4 / 30

Practice Question

Convert infix to postfix:

(X − Y ) ∗ (Z + W )

Dr. Dheeraj Expression Conversions Using Stack 5 / 30

Final Answer

XY − ZW + ∗

Dr. Dheeraj Expression Conversions Using Stack 6 / 30

Infix to Prefix – Example

Convert:
(A − B) ∗ (C + D)

Dr. Dheeraj Expression Conversions Using Stack 7 / 30

Step 1: Reverse the Infix Expression

Original Infix:
(A − B) ∗ (C + D)
After reversing and swapping brackets:

(D + C ) ∗ (B − A)

Dr. Dheeraj Expression Conversions Using Stack 8 / 30

Step 2: Stack Conversion (Reversed Infix to Postfix)

Scanned Stack Postfix Output

( ( –
D ( D
+ (+ D
C (+ DC
) – DC+
* * DC+
( *( DC+
B *( DC+B
- *(- DC+B
A *(- DC+BA
) * DC+BA-
End – DC+BA-*

Dr. Dheeraj Expression Conversions Using Stack 9 / 30

Step 3: Reverse Postfix to Get Prefix

Postfix obtained:
DC + BA − ∗
After reversing:
∗ − AB + CD
Final Prefix Expression:
∗ − AB + CD

Dr. Dheeraj Expression Conversions Using Stack 10 / 30

Final Answer

(A − B) ∗ (C + D) ⇒ ∗ − AB + CD

Dr. Dheeraj Expression Conversions Using Stack 11 / 30

Practice Question

Convert the following infix expression into prefix form:

(A + B) ∗ (C − D/E ) ˆ(F + G ∗ H) − I

Note:
Operator precedence must be strictly followed
Use stack-based conversion

Dr. Dheeraj Expression Conversions Using Stack 12 / 30

Final Answer

− ∗ +AB ˆ− C /DE + F ∗ GHI

Dr. Dheeraj Expression Conversions Using Stack 13 / 30

Prefix to Infix – Example

Convert:
∗ + AB − CD

Dr. Dheeraj Expression Conversions Using Stack 14 / 30

Prefix to Infix – Detailed Stack Solution

Symbol Stack
D D
C C, D
- (C-D)
Scan right to left
B B, (C-D)
A A, B, (C-D)
+ (A+B), (C-D)
* (A+B)*(C-D)

Dr. Dheeraj Expression Conversions Using Stack 15 / 30

Practice Question

Convert prefix to infix:

− ∗ ABC

Dr. Dheeraj Expression Conversions Using Stack 16 / 30

Final Answer

(A ∗ B) − C

Dr. Dheeraj Expression Conversions Using Stack 17 / 30

Prefix to Postfix – Example

Convert:
− ∗ AB/CD

Dr. Dheeraj Expression Conversions Using Stack 18 / 30

Prefix to Postfix – Detailed Stack Solution

Symbol Stack
D D
C C, D
/ CD/
Scan right to left
B B, CD/
A A, B, CD/
* AB*, CD/
- AB*CD/-

Dr. Dheeraj Expression Conversions Using Stack 19 / 30

Practice Question

Convert prefix to postfix:

+A ∗ BC

Dr. Dheeraj Expression Conversions Using Stack 20 / 30

Final Answer

ABC ∗ +

Dr. Dheeraj Expression Conversions Using Stack 21 / 30

Postfix to Infix – Example

Convert:
AB + CD − ∗

Dr. Dheeraj Expression Conversions Using Stack 22 / 30

Postfix to Infix – Detailed Stack Solution

Symbol Stack
A A
B A, B
+ (A+B)
C (A+B), C
D (A+B), C, D
- (A+B), (C-D)
* (A+B)*(C-D)

Dr. Dheeraj Expression Conversions Using Stack 23 / 30

Practice Question

Convert postfix to infix:

AB ∗ C +

Dr. Dheeraj Expression Conversions Using Stack 24 / 30

Final Answer

(A ∗ B) + C

Dr. Dheeraj Expression Conversions Using Stack 25 / 30

Postfix to Prefix – Example

Convert:
AB + CD − ∗

Dr. Dheeraj Expression Conversions Using Stack 26 / 30

Postfix to Prefix – Detailed Stack Solution

Symbol Stack
A A
B A, B
+ +AB
C +AB, C
D +AB, C, D
- -CD
* *+AB-CD

Dr. Dheeraj Expression Conversions Using Stack 27 / 30

Practice Question

Convert the following postfix expression into prefix form:

ABCD ˆ∗ +EF / − +

Hint:
Use a stack
Process operands left to right
Carefully handle operator precedence

Dr. Dheeraj Expression Conversions Using Stack 28 / 30

Final Answer

+ + A ∗ B ˆCD − E /F

Dr. Dheeraj Expression Conversions Using Stack 29 / 30

 Thank You

Dr. Dheeraj Expression Conversions Using Stack 30 / 30

 Data Structures: The Queue ADT
Theory, Implementation, and Applications

Dr. Dheeraj
Assistant Professor

ABV-Indian Institute of Information Technology and Management, Gwalior

January 2026

Dr. Dheeraj Assistant Professor (ABV-Indian

Data Structures:
Institute ofThe
Information
Queue ADT
Technology and Management,
January 2026
Gwalior) 1 / 22
 Learning Objectives

Define Queue as an Abstract Data Type (ADT).

Understand the First-In-First-Out (FIFO) principle.
Explore Linear and Circular Queue implementations.
Analyze time complexities of operations.
Solve real-world and competitive programming problems.

Dr. Dheeraj Assistant Professor (ABV-Indian

Data Structures:
Institute ofThe
Information
Queue ADT
Technology and Management,
January 2026
Gwalior) 2 / 22
 What is a Queue?

A linear data structure that follows the FIFO (First-In-First-Out)

principle.
Insertion happens at one end (Rear/Back).
Deletion happens at the other end (Front/Head).
Analogous to a line at a ticket counter.

Dr. Dheeraj Assistant Professor (ABV-Indian

Data Structures:
Institute ofThe
Information
Queue ADT
Technology and Management,
January 2026
Gwalior) 3 / 22
 Real-world Analogies

Printer Queue: Documents waiting to be printed.

Call Center: Calls placed on hold.
CPU Scheduling: Processes waiting for execution.
Breadth-First Search (BFS): Exploring nodes in layers.

Dr. Dheeraj Assistant Professor (ABV-Indian

Data Structures:
Institute ofThe
Information
Queue ADT
Technology and Management,
January 2026
Gwalior) 4 / 22
 Queue Operations (The ADT)

enqueue(x): Add element x to the Rear.

dequeue(): Remove and return the element at the Front.
peek() / front(): Get the front element without removing it.
isEmpty(): Check if the queue is empty.
isFull(): Check if the queue is at capacity.

Dr. Dheeraj Assistant Professor (ABV-Indian

Data Structures:
Institute ofThe
Information
Queue ADT
Technology and Management,
January 2026
Gwalior) 5 / 22
 Visualizing a Queue

Elements enter from the Rear and leave from the Front.

Dr. Dheeraj Assistant Professor (ABV-Indian

Data Structures:
Institute ofThe
Information
Queue ADT
Technology and Management,
January 2026
Gwalior) 6 / 22
 Array Implementation: Linear Queue

Uses an array arr[SIZE].

Two pointers: front and rear.
Initially, front = -1, rear = -1.
Problem: Once rear reaches SIZE-1, we cannot insert even if
spaces are free at the front. (Memory wastage).

Dr. Dheeraj Assistant Professor (ABV-Indian

Data Structures:
Institute ofThe
Information
Queue ADT
Technology and Management,
January 2026
Gwalior) 7 / 22
 Algorithm: Enqueue(x)

if rear == SIZE - 1 then

return ”Queue Overflow”
else
if front == -1 then
front = 0
end if
rear = rear + 1
arr[rear] = x
end if

Dr. Dheeraj Assistant Professor (ABV-Indian

Data Structures:
Institute ofThe
Information
Queue ADT
Technology and Management,
January 2026
Gwalior) 8 / 22
 Algorithm: Dequeue()

if front == -1 OR front >rear then

return “Queue Underflow”
else
val = arr[front]
front = front + 1
return val
end if

Dr. Dheeraj Assistant Professor (ABV-Indian

Data Structures:
Institute ofThe
Information
Queue ADT
Technology and Management,
January 2026
Gwalior) 9 / 22
 The ”Stale Space” Problem

As we dequeue, the front pointer moves forward.

The memory indices before front become unusable.
Solution: Circular Queues.

Dr. Dheeraj Assistant Professor (ABV-Indian

Data Structures:
Institute ofThe
Information
Queue ADT
Technology and Management,
January 2026
Gwalior) 10 / 22
 Circular Queues

The last position is connected back to the first position.

Uses modulo arithmetic: (i + 1) % SIZE.

Dr. Dheeraj Assistant Professor (ABV-Indian

Data Structures:
Institute ofThe
Information
Queue ADT
Technology and Management,
January 2026
Gwalior) 11 / 22
 Circular Queue: Enqueue Logic

if (rear + 1) % SIZE == front then

return ”Queue Full”
else if front == -1 then
front = rear = 0
else
rear = (rear + 1) % SIZE
end if
arr[rear] = x

Dr. Dheeraj Assistant Professor (ABV-Indian

Data Structures:
Institute ofThe
Information
Queue ADT
Technology and Management,
January 2026
Gwalior) 12 / 22
 Linked List Implementation

No fixed size.
Enqueue: Add node to the tail.
Dequeue: Remove node from the head.
front points to Head, rear points to Tail.

Dr. Dheeraj Assistant Professor (ABV-Indian

Data Structures:
Institute ofThe
Information
Queue ADT
Technology and Management,
January 2026
Gwalior) 13 / 22
 Complexity Analysis

Operation Time Complexity Space

Enqueue O(1) O(1)
Dequeue O(1) O(1)
Peek O(1) O(1)
Search O(n) O(1)

Dr. Dheeraj Assistant Professor (ABV-Indian

Data Structures:
Institute ofThe
Information
Queue ADT
Technology and Management,
January 2026
Gwalior) 14 / 22
 Double Ended Queue (Deque)

Insertion and deletion possible from both ends.

Types:
1 Input Restricted Deque.
2 Output Restricted Deque.

Dr. Dheeraj Assistant Professor (ABV-Indian

Data Structures:
Institute ofThe
Information
Queue ADT
Technology and Management,
January 2026
Gwalior) 15 / 22
 Priority Queue

Each element has a priority.

Elements with higher priority are dequeued first.
Implementation: Heaps or Ordered Lists.

Dr. Dheeraj Assistant Professor (ABV-Indian

Data Structures:
Institute ofThe
Information
Queue ADT
Technology and Management,
January 2026
Gwalior) 16 / 22
 Application 1: CPU Scheduling

Round Robin Scheduling uses a Queue to manage processes.

Each process gets a fixed time slice.

Dr. Dheeraj Assistant Professor (ABV-Indian

Data Structures:
Institute ofThe
Information
Queue ADT
Technology and Management,
January 2026
Gwalior) 17 / 22
 Practice Problem 1: Trace the Queue

Given a Queue of size 5, perform: 1. Enqueue(10) 2. Enqueue(20) 3.

Dequeue() 4. Enqueue(30) 5. Enqueue(40) 6. Dequeue() What are the
values of Front and Rear pointers?

Dr. Dheeraj Assistant Professor (ABV-Indian

Data Structures:
Institute ofThe
Information
Queue ADT
Technology and Management,
January 2026
Gwalior) 18 / 22
 Output: Practice Problem 1

Initial: F=-1, R=-1

Enq(10): F=0, R=0 [10]
Enq(20): F=0, R=1 [10, 20]
Deq(): F=1, R=1 [20]
Enq(30): F=1, R=2 [20, 30]
Enq(40): F=1, R=3 [20, 30, 40]
Deq(): F=2, R=3 [30, 40]
Final: Front Index = 2, Rear Index = 3

Dr. Dheeraj Assistant Professor (ABV-Indian

Data Structures:
Institute ofThe
Information
Queue ADT
Technology and Management,
January 2026
Gwalior) 19 / 22
 Practice Problem 2: Reverse a Queue

Problem: Reverse the elements of a queue using only one additional

Stack.
Input: [1, 2, 3, 4, 5]
Output: [5, 4, 3, 2, 1]

Dr. Dheeraj Assistant Professor (ABV-Indian

Data Structures:
Institute ofThe
Information
Queue ADT
Technology and Management,
January 2026
Gwalior) 20 / 22
 Algorithm: Reverse Queue

while Queue is not empty do

[Link]([Link]())
end while
while Stack is not empty do
[Link]([Link]())
end while

Dr. Dheeraj Assistant Professor (ABV-Indian

Data Structures:
Institute ofThe
Information
Queue ADT
Technology and Management,
January 2026
Gwalior) 21 / 22
 Summary

Queue is essential for ordered processing.

Circular queues prevent memory wastage.
Priority queues are used in complex algorithms like Dijkstra’s.
Always check for Overflow/Underflow.

Questions?

Dr. Dheeraj Assistant Professor (ABV-Indian

Data Structures:
Institute ofThe
Information
Queue ADT
Technology and Management,
January 2026
Gwalior) 22 / 22
 Data Structures: The Queue ADT
Theory, Implementation, and Applications

Dr. Dheeraj
Assistant Professor

ABV-Indian Institute of Information Technology and Management, Gwalior

January 2026

Dr. Dheeraj Assistant Professor (ABV-Indian

Data Structures:
Institute ofThe
Information
Queue ADT
Technology and Management,
January 2026
Gwalior) 1 / 22
 Learning Objectives

Define Queue as an Abstract Data Type (ADT).

Understand the First-In-First-Out (FIFO) principle.
Explore Linear and Circular Queue implementations.
Analyze time complexities of operations.
Solve real-world and competitive programming problems.

Dr. Dheeraj Assistant Professor (ABV-Indian

Data Structures:
Institute ofThe
Information
Queue ADT
Technology and Management,
January 2026
Gwalior) 2 / 22
 What is a Queue?

A linear data structure that follows the FIFO (First-In-First-Out)

principle.
Insertion happens at one end (Rear/Back).
Deletion happens at the other end (Front/Head).
Analogous to a line at a ticket counter.

Dr. Dheeraj Assistant Professor (ABV-Indian

Data Structures:
Institute ofThe
Information
Queue ADT
Technology and Management,
January 2026
Gwalior) 3 / 22
 Real-world Analogies

Printer Queue: Documents waiting to be printed.

Call Center: Calls placed on hold.
CPU Scheduling: Processes waiting for execution.
Breadth-First Search (BFS): Exploring nodes in layers.

Dr. Dheeraj Assistant Professor (ABV-Indian

Data Structures:
Institute ofThe
Information
Queue ADT
Technology and Management,
January 2026
Gwalior) 4 / 22
 Queue Operations (The ADT)

enqueue(x): Add element x to the Rear.

dequeue(): Remove and return the element at the Front.
peek() / front(): Get the front element without removing it.
isEmpty(): Check if the queue is empty.
isFull(): Check if the queue is at capacity.

Dr. Dheeraj Assistant Professor (ABV-Indian

Data Structures:
Institute ofThe
Information
Queue ADT
Technology and Management,
January 2026
Gwalior) 5 / 22
 Visualizing a Queue

Elements enter from the Rear and leave from the Front.

Dr. Dheeraj Assistant Professor (ABV-Indian

Data Structures:
Institute ofThe
Information
Queue ADT
Technology and Management,
January 2026
Gwalior) 6 / 22
 Array Implementation: Linear Queue

Uses an array arr[SIZE].

Two pointers: front and rear.
Initially, front = -1, rear = -1.
Problem: Once rear reaches SIZE-1, we cannot insert even if
spaces are free at the front. (Memory wastage).

Dr. Dheeraj Assistant Professor (ABV-Indian

Data Structures:
Institute ofThe
Information
Queue ADT
Technology and Management,
January 2026
Gwalior) 7 / 22
 Algorithm: Enqueue(x)

if rear == SIZE - 1 then

return ”Queue Overflow”
else
if front == -1 then
front = 0
end if
rear = rear + 1
arr[rear] = x
end if

Dr. Dheeraj Assistant Professor (ABV-Indian

Data Structures:
Institute ofThe
Information
Queue ADT
Technology and Management,
January 2026
Gwalior) 8 / 22
 Algorithm: Dequeue()

if front == -1 OR front >rear then

return “Queue Underflow”
else
val = arr[front]
front = front + 1
return val
end if

Dr. Dheeraj Assistant Professor (ABV-Indian

Data Structures:
Institute ofThe
Information
Queue ADT
Technology and Management,
January 2026
Gwalior) 9 / 22
 The ”Stale Space” Problem

As we dequeue, the front pointer moves forward.

The memory indices before front become unusable.
Solution: Circular Queues.

Dr. Dheeraj Assistant Professor (ABV-Indian

Data Structures:
Institute ofThe
Information
Queue ADT
Technology and Management,
January 2026
Gwalior) 10 / 22
 Circular Queues

The last position is connected back to the first position.

Uses modulo arithmetic: (i + 1) % SIZE.

Dr. Dheeraj Assistant Professor (ABV-Indian

Data Structures:
Institute ofThe
Information
Queue ADT
Technology and Management,
January 2026
Gwalior) 11 / 22
 Circular Queue: Enqueue Logic

if (rear + 1) % SIZE == front then

return ”Queue Full”
else if front == -1 then
front = rear = 0
else
rear = (rear + 1) % SIZE
end if
arr[rear] = x

Dr. Dheeraj Assistant Professor (ABV-Indian

Data Structures:
Institute ofThe
Information
Queue ADT
Technology and Management,
January 2026
Gwalior) 12 / 22
 Linked List Implementation

No fixed size.
Enqueue: Add node to the tail.
Dequeue: Remove node from the head.
front points to Head, rear points to Tail.

Dr. Dheeraj Assistant Professor (ABV-Indian

Data Structures:
Institute ofThe
Information
Queue ADT
Technology and Management,
January 2026
Gwalior) 13 / 22
 Complexity Analysis

Operation Time Complexity Space

Enqueue O(1) O(1)
Dequeue O(1) O(1)
Peek O(1) O(1)
Search O(n) O(1)

Dr. Dheeraj Assistant Professor (ABV-Indian

Data Structures:
Institute ofThe
Information
Queue ADT
Technology and Management,
January 2026
Gwalior) 14 / 22
 Double Ended Queue (Deque)

Insertion and deletion possible from both ends.

Types:
1 Input Restricted Deque.
2 Output Restricted Deque.

Dr. Dheeraj Assistant Professor (ABV-Indian

Data Structures:
Institute ofThe
Information
Queue ADT
Technology and Management,
January 2026
Gwalior) 15 / 22
 Priority Queue

Each element has a priority.

Elements with higher priority are dequeued first.
Implementation: Heaps or Ordered Lists.

Dr. Dheeraj Assistant Professor (ABV-Indian

Data Structures:
Institute ofThe
Information
Queue ADT
Technology and Management,
January 2026
Gwalior) 16 / 22
 Application 1: CPU Scheduling

Round Robin Scheduling uses a Queue to manage processes.

Each process gets a fixed time slice.

Dr. Dheeraj Assistant Professor (ABV-Indian

Data Structures:
Institute ofThe
Information
Queue ADT
Technology and Management,
January 2026
Gwalior) 17 / 22
 Practice Problem 1: Trace the Queue

Given a Queue of size 5, perform: 1. Enqueue(10) 2. Enqueue(20) 3.

Dequeue() 4. Enqueue(30) 5. Enqueue(40) 6. Dequeue() What are the
values of Front and Rear pointers?

Dr. Dheeraj Assistant Professor (ABV-Indian

Data Structures:
Institute ofThe
Information
Queue ADT
Technology and Management,
January 2026
Gwalior) 18 / 22
 Output: Practice Problem 1

Initial: F=-1, R=-1

Enq(10): F=0, R=0 [10]
Enq(20): F=0, R=1 [10, 20]
Deq(): F=1, R=1 [20]
Enq(30): F=1, R=2 [20, 30]
Enq(40): F=1, R=3 [20, 30, 40]
Deq(): F=2, R=3 [30, 40]
Final: Front Index = 2, Rear Index = 3

Dr. Dheeraj Assistant Professor (ABV-Indian

Data Structures:
Institute ofThe
Information
Queue ADT
Technology and Management,
January 2026
Gwalior) 19 / 22
 Practice Problem 2: Reverse a Queue

Problem: Reverse the elements of a queue using only one additional

Stack.
Input: [1, 2, 3, 4, 5]
Output: [5, 4, 3, 2, 1]

Dr. Dheeraj Assistant Professor (ABV-Indian

Data Structures:
Institute ofThe
Information
Queue ADT
Technology and Management,
January 2026
Gwalior) 20 / 22
 Algorithm: Reverse Queue

while Queue is not empty do

[Link]([Link]())
end while
while Stack is not empty do
[Link]([Link]())
end while

Dr. Dheeraj Assistant Professor (ABV-Indian

Data Structures:
Institute ofThe
Information
Queue ADT
Technology and Management,
January 2026
Gwalior) 21 / 22
 Summary

Queue is essential for ordered processing.

Circular queues prevent memory wastage.
Priority queues are used in complex algorithms like Dijkstra’s.
Always check for Overflow/Underflow.

Questions?

Dr. Dheeraj Assistant Professor (ABV-Indian

Data Structures:
Institute ofThe
Information
Queue ADT
Technology and Management,
January 2026
Gwalior) 22 / 22
Comprehensive Searching Algorithms in Data Structures

Dr. Dheeraj

ABV-IIITM Gwalior

February 2026

Dr. Dheeraj (ABV-IIITM Gwalior) Searching Algorithms February 2026 1 / 25

What is Searching?

Searching is the process of finding the location of a target element in a

collection.
Efficiency Matters: As n → ∞, the choice of algorithm determines whether
a system is fast or unusable.
Classification:
1 Sequential Search: Unsorted data (e.g., Linear Search).
2 Interval Search: Sorted data (e.g., Binary Search).

Dr. Dheeraj (ABV-IIITM Gwalior) Searching Algorithms February 2026 2 / 25

1. Linear Search (Sequential Search)

Logic: Check every element one by one from start to end.

Best For: Small or unsorted datasets.
Complexity: O(n).

Real-World Example
Looking for a specific face in a crowd or finding a tool in a messy toolbox.

Dr. Dheeraj (ABV-IIITM Gwalior) Searching Algorithms February 2026 3 / 25

Linear Search: Pseudocode

function LinearSearch(arr , target)

for i = 0 to length(arr ) − 1 do
if arr [i] == target then
return i
end if
end for
return −1
end function

Input: [10, 5, 20, 8], Target: 20 → Output: 2

Dr. Dheeraj (ABV-IIITM Gwalior) Searching Algorithms February 2026 4 / 25

Practice: Linear Search

Question: Trace the steps to find 42 in [12, 5, 8, 42, 10]. How many comparisons
are made?

Dr. Dheeraj (ABV-IIITM Gwalior) Searching Algorithms February 2026 5 / 25

Output: Linear Search Practice

Step 1: 12 == 42 (False)
Step 2: 5 == 42 (False)
Step 3: 8 == 42 (False)
Step 4: 42 == 42 (True!)
Result: Index 3, Total Comparisons: 4.

Dr. Dheeraj (ABV-IIITM Gwalior) Searching Algorithms February 2026 6 / 25

2. Binary Search

Requirement: Data MUST be sorted.

Logic: Divide and Conquer. Look at the middle; discard half the search
space.
Complexity: O(log n).

Real-World Example
Finding a word in a physical Dictionary or finding a page in a textbook.

Dr. Dheeraj (ABV-IIITM Gwalior) Searching Algorithms February 2026 7 / 25

Binary Search: Pseudocode

function BinarySearch(arr , target)

low ← 0, high ← len(arr ) − 1
while low ≤ high do
mid ← low + (high − low )/2
if arr [mid] == target then
return mid
arr [mid] < target
low ← mid + 1
else high ← mid − 1
end if
end whilereturn −1
end function

Dr. Dheeraj (ABV-IIITM Gwalior) Searching Algorithms February 2026 8 / 25

Practice: Binary Search

Question: Find 70 in sorted array [10, 20, 30, 40, 50, 60, 70, 80].

Dr. Dheeraj (ABV-IIITM Gwalior) Searching Algorithms February 2026 9 / 25

Output: Binary Search Practice

Initial: low = 0, high = 7, mid = 3 (Value 40). 70 > 40.

Step 2: low = 4, high = 7, mid = 5 (Value 60). 70 > 60.
Step 3: low = 6, high = 7, mid = 6 (Value 70). Found!
Result: Index 6.

Dr. Dheeraj (ABV-IIITM Gwalior) Searching Algorithms February 2026 10 / 25

3. Jump Search

√
Logic: Jump ahead by fixed blocks of size n. When target is passed, do
Linear Search backward.
√
Complexity: O( n).

Real-World Example
Checking a long sorted list of files by skipping 10 files at a time.

Dr. Dheeraj (ABV-IIITM Gwalior) Searching Algorithms February 2026 11 / 25

Practice: Jump Search

Question: Array size n = 16, Target is at index 13. How many ”jumps” of size
√
16 = 4 are made?

Dr. Dheeraj (ABV-IIITM Gwalior) Searching Algorithms February 2026 12 / 25

Output: Jump Search Practice

Jump 1: Index 0 to 4.
Jump 2: Index 4 to 8.
Jump 3: Index 8 to 12.
Jump 4: Index 12 to 16 (Passed target).
Linear Search starts from Index 12.
Result: 4 Jumps + Linear Search.

Dr. Dheeraj (ABV-IIITM Gwalior) Searching Algorithms February 2026 13 / 25

4. Interpolation Search

Condition: Sorted and Uniformly Distributed data.

Logic: Estimates position based on value (Probing).
Complexity: Average O(log(log n)), Worst O(n).

Real-World Example
Finding the name ”Brown” in a Phonebook. You don’t start in the middle; you
start near the front because ’B’ is early.

Dr. Dheeraj (ABV-IIITM Gwalior) Searching Algorithms February 2026 14 / 25

Interpolation Probe Formula

Instead of mid = (low + high)/2, use:

 
(target − arr [low ]) × (high − low )
pos = low +
arr [high] − arr [low ]

Practice: If arr = [10, 20, 30, 40, 50] and target = 40, what is pos?

Dr. Dheeraj (ABV-IIITM Gwalior) Searching Algorithms February 2026 15 / 25

Output: Interpolation Practice

 
(40 − 10) × (4 − 0) 30 × 4
pos = 0 + = =3
50 − 10 40
Result: Index 3. It found the element in one hit!

Dr. Dheeraj (ABV-IIITM Gwalior) Searching Algorithms February 2026 16 / 25

5. Exponential Search

Logic: Find the range where the element exists by doubling the index
(1, 2, 4, 8 . . . ). Then do Binary Search in that range.
Best For: Unbounded/Infinite arrays.

Real-World Example
Searching for a specific timestamp in a massive, ongoing server log.

Dr. Dheeraj (ABV-IIITM Gwalior) Searching Algorithms February 2026 17 / 25

Practice: Exponential Search

Question: If the target is at index 10, what are the ranges checked during the
”doubling” phase?

Dr. Dheeraj (ABV-IIITM Gwalior) Searching Algorithms February 2026 18 / 25

Output: Exponential Search Practice

Check index 1.
Check index 2.
Check index 4.
Check index 8.
Check index 16 (Beyond 10).
Range for Binary Search: [8, 16].

Dr. Dheeraj (ABV-IIITM Gwalior) Searching Algorithms February 2026 19 / 25

6. Ternary Search

Logic: Divide the array into three parts using two midpoints (m1, m2).
Complexity: O(log3 n).

Real-World Example
Finding the peak of a unimodal function (e.g., finding the maximum brightness in
a video frame).

Dr. Dheeraj (ABV-IIITM Gwalior) Searching Algorithms February 2026 20 / 25

Practice: Ternary Search

Question: How many comparisons per step in Ternary Search vs Binary Search?

Dr. Dheeraj (ABV-IIITM Gwalior) Searching Algorithms February 2026 21 / 25

Output: Ternary Search Practice

Binary Search: 1 comparison to split into 2 parts.

Ternary Search: 2 comparisons to split into 3 parts.
Note: Though log3 n < log2 n, the extra comparisons often make Ternary search
slower in practice for simple arrays.

Dr. Dheeraj (ABV-IIITM Gwalior) Searching Algorithms February 2026 22 / 25

7. Fibonacci Search

Logic: Uses Fibonacci numbers to divide the array into unequal parts.
Advantage: Uses only addition and subtraction (no division), which is
faster on some CPUs.

Real-World Example
You need to find a specific mark on a long ribbon, but your calculator’s ”Division”
button is broken. You can only add or subtract.

Dr. Dheeraj (ABV-IIITM Gwalior) Searching Algorithms February 2026 23 / 25

Final Review: 4 Practice Questions

1 Which search is best for a small, totally unsorted array?

2 What is the pre-requisite for Interpolation Search to be faster than Binary
Search?
3 If n = 100, what is the block size for Jump Search?
4 Does Binary Search work on a Linked List? Why?

Dr. Dheeraj (ABV-IIITM Gwalior) Searching Algorithms February 2026 24 / 25

Output: Final Review

1 Linear Search.
2 Data must be uniformly distributed (gaps between values are similar).
√
3 Block size = 10 ( 100).
4 No. Binary search requires ”Random Access” (O(1) to middle). Linked lists
are O(n) to reach the middle.
Thank You! Questions?

Dr. Dheeraj (ABV-IIITM Gwalior) Searching Algorithms February 2026 25 / 25

 IT102: Sorting Techniques in Data Structures
Comprehensive Guide with Real-World Applications

Dr. Dheeraj Kodati

Assistant Professor

ABV-Indian Institute of Information Technology and Management, Gwalior

Batch: BEE and IMG

March 27, 2026

Dr. Dheeraj (IIITM Gwalior) Sorting in Data Structures March 27, 2026 1 / 21
Lecture Overview

1 Introduction to Sorting
2 Bubble Sort
3 Selection Sort
4 Insertion Sort
5 Merge Sort
6 Quick Sort
7 Heap Sort
8 Real World Examples
9 Comparison Summary
10 Practice Sessions

Dr. Dheeraj (IIITM Gwalior) Sorting in Data Structures March 27, 2026 2 / 21
What is Sorting?

Definition: Arranging elements in a specific order (Numerical or

Lexicographical).
Internal vs. External: Sorting in RAM vs. Secondary Storage.
Stability: Does the relative order of equal keys remain the same?
In-place: Does it require extra memory?

Real-World Example:
E-commerce: Sorting products by price (Low to High).
Contact List: Sorting names alphabetically.

Dr. Dheeraj (IIITM Gwalior) Sorting in Data Structures March 27, 2026 3 / 21
Bubble Sort: The Concept

Repeatedly steps through the list, compares adjacent elements, and

swaps them if they are in the wrong order.
The largest element ”bubbles up” to its correct position in each pass.
Complexity:
Best Case: O(n) (Optimized)
Average/Worst Case: O(n2 )

Dr. Dheeraj (IIITM Gwalior) Sorting in Data Structures March 27, 2026 4 / 21
Problem 1: Bubble Sort Trace

Problem: Sort the array A = [5, 1, 4, 2] using Bubble Sort. Show the state
after each swap in the first pass.

Dr. Dheeraj (IIITM Gwalior) Sorting in Data Structures March 27, 2026 5 / 21
Solution 1: Bubble Sort Trace

Step-by-Step:
1 Compare (5, 1): 5 > 1 → Swap: [1, 5, 4, 2]
2 Compare (5, 4): 5 > 4 → Swap: [1, 4, 5, 2]
3 Compare (5, 2): 5 > 2 → Swap: [1, 4, 2, 5]
After Pass 1, 5 is at the correct position.

Dr. Dheeraj (IIITM Gwalior) Sorting in Data Structures March 27, 2026 6 / 21
Selection Sort

Maintains two subarrays: one sorted and one unsorted.

Repeatedly finds the minimum element from the unsorted part and
puts it at the beginning.
Complexity: O(n2 ) for all cases.

Dr. Dheeraj (IIITM Gwalior) Sorting in Data Structures March 27, 2026 7 / 21
Problem 2: Selection Sort Analysis

Problem: In an array of 100 elements, how many comparisons are made

by Selection Sort?

Dr. Dheeraj (IIITM Gwalior) Sorting in Data Structures March 27, 2026 8 / 21
Solution 2: Selection Sort Analysis

Selection Sort comparisons are independent of the initial order:

n(n − 1)
Total Comparisons =
2
For n = 100:
100 × 99
= 4950 comparisons
2

Dr. Dheeraj (IIITM Gwalior) Sorting in Data Structures March 27, 2026 9 / 21
Insertion Sort: The ”Card Player” Method

Build the sorted array one item at a time.

Efficient for small data sets or nearly sorted data.
Complexity: Best O(n), Worst O(n2 ).

Dr. Dheeraj (IIITM Gwalior) Sorting in Data Structures March 27, 2026 10 / 21
Merge Sort: Divide and Conquer

1 Divide: Split the array into two halves.

2 Conquer: Recursively sort the halves.
3 Combine: Merge the two sorted halves into one.
Complexity: O(n log n) always.

Dr. Dheeraj (IIITM Gwalior) Sorting in Data Structures March 27, 2026 11 / 21
Problem 3: Merge Sort Space

Problem: Why is Merge Sort generally not preferred for sorting in-place
arrays, and what is its space complexity?

Dr. Dheeraj (IIITM Gwalior) Sorting in Data Structures March 27, 2026 12 / 21
Solution 3: Merge Sort Space

Space Complexity: O(n) because of the temporary arrays used

during the merge step.
It is not ”in-place,” making it less ideal when memory is strictly
limited compared to Heapsort or Quicksort.

Dr. Dheeraj (IIITM Gwalior) Sorting in Data Structures March 27, 2026 13 / 21
Quick Sort: Partitioning

Pick a Pivot element.

Partition the array such that elements < Pivot are on the left and >
Pivot are on the right.
Recursively apply to sub-arrays.
Complexity: Average O(n log n), Worst O(n2 ) (when pivot is the
smallest/largest element).

Dr. Dheeraj (IIITM Gwalior) Sorting in Data Structures March 27, 2026 14 / 21
Problem 4: Quick Sort Pivot

Problem: Given A = [10, 80, 30, 90, 40, 50, 70]. Perform the first partition
using the last element (70) as the pivot.

Dr. Dheeraj (IIITM Gwalior) Sorting in Data Structures March 27, 2026 15 / 21
Solution 4: Quick Sort Pivot

Result of first partition: [10, 30, 40, 50, 70, 90, 80]
70 is now in its final sorted position.
Left: {10, 30, 40, 50}, Right: {90, 80}.

Dr. Dheeraj (IIITM Gwalior) Sorting in Data Structures March 27, 2026 16 / 21
Heap Sort

Uses a Binary Heap data structure.

Build a Max-Heap, then repeatedly extract the maximum element.
Complexity: O(n log n).

Dr. Dheeraj (IIITM Gwalior) Sorting in Data Structures March 27, 2026 17 / 21
Which Algorithm to Use?

Scenario Best Choice

Nearly sorted data Insertion Sort
Large datasets, guaranteed speed Merge Sort
Limited Memory (Embedded) Heap Sort / Quick Sort
Stability is required Merge Sort / Bubble Sort

Dr. Dheeraj (IIITM Gwalior) Sorting in Data Structures March 27, 2026 18 / 21
Complexity Comparison

Algorithm Best Average Worst

Bubble O(n) O(n2 ) O(n2 )
Selection O(n2 ) O(n2 ) O(n2 )
Insertion O(n) O(n2 ) O(n2 )
Merge O(n log n) O(n log n) O(n log n)
Quick O(n log n) O(n log n) O(n2 )

Dr. Dheeraj (IIITM Gwalior) Sorting in Data Structures March 27, 2026 19 / 21
Practice Questions for Students

1 Stability: Prove why Selection Sort is inherently unstable with a

3-element example.
2 Hybrid Sorting: Research ”Timsort.” Why does Python use a mix of
Merge and Insertion sort?
3 Optimization: Write the pseudo-code for a Bubble Sort that stops
early if the array is already sorted.
4 External Sorting: If you have 100GB of data and only 8GB of RAM,
which sorting strategy would you employ? Explain the phases.

Dr. Dheeraj (IIITM Gwalior) Sorting in Data Structures March 27, 2026 20 / 21
Thank You

Questions?
Dr. Dheeraj Kodati
dkodati@[Link]

Dr. Dheeraj (IIITM Gwalior) Sorting in Data Structures March 27, 2026 21 / 21
 Data Structures: Dictionaries (Hash Maps)

Dr. Dheeraj
Assistant Professor

ABV-IIITM, Gwalior

February 10, 2026

Dr. Dheeraj Assistant Professor (ABV-IIITM,

Data Structures:
Gwalior)
Dictionaries (Hash Maps) February 10, 2026 1 / 25
 What is a Dictionary?

A Dictionary is an abstract data type (ADT).

It stores data in Key-Value pairs.
Unlike arrays (indexed by numbers), Dictionaries are indexed by
unique keys (Strings, Integers, etc.).
Analogy: A real-life language dictionary.
Key: The word (e.g., ”Apple”)
Value: The definition (e.g., ”A red crunchy fruit”)

Dr. Dheeraj Assistant Professor (ABV-IIITM,

Data Structures:
Gwalior)
Dictionaries (Hash Maps) February 10, 2026 2 / 25
 Example: Contact List

The Problem: How does your phone find ”Mom’s” number instantly?
Key: Contact Name (e.g., ”Mom”)
Value: Phone Number (e.g., ”+1-555-0199”)
Instead of searching every name, the phone uses a Dictionary structure to
jump straight to the number.

Dr. Dheeraj Assistant Professor (ABV-IIITM,

Data Structures:
Gwalior)
Dictionaries (Hash Maps) February 10, 2026 3 / 25
 Example: Social Media

Platform: Instagram/X
Key: Username (e.g., @DrDheeraj)
Value: User Profile Object (Bio, Followers, Posts)
Usernames must be unique because they act as keys.

Dr. Dheeraj Assistant Professor (ABV-IIITM,

Data Structures:
Gwalior)
Dictionaries (Hash Maps) February 10, 2026 4 / 25
 Core Operations

A Dictionary typically supports three main operations:

1 Insert(key, value): Add a new pair.
2 Delete(key): Remove a pair using its key.
3 Lookup/Search(key): Retrieve the value associated with the key.

Dr. Dheeraj Assistant Professor (ABV-IIITM,

Data Structures:
Gwalior)
Dictionaries (Hash Maps) February 10, 2026 5 / 25
 The Rule of Keys

1. Uniqueness
Keys must be unique. You cannot have two identical keys in one dictionary.

2. Immutability
In most languages (like Python), keys must be of a type that cannot
change (like strings or integers).

Dr. Dheeraj Assistant Professor (ABV-IIITM,

Data Structures:
Gwalior)
Dictionaries (Hash Maps) February 10, 2026 6 / 25
 Under the Hood: Hashing

How do we find a key instantly?

Hash Function: Takes a key and turns it into a math index (a
number).
Index = HashFunction(Key ) (mod ArraySize)
This allows O(1) average time complexity for searching!

Dr. Dheeraj Assistant Professor (ABV-IIITM,

Data Structures:
Gwalior)
Dictionaries (Hash Maps) February 10, 2026 7 / 25
 Pseudocode: Creating a Dictionary

// Initialize empty dictionary

myDict = CreateDictionary()

// Adding values
[Link]("Apple", 50)
[Link]("Banana", 20)

Output: {"Apple": 50, "Banana": 20}

Dr. Dheeraj Assistant Professor (ABV-IIITM,

Data Structures:
Gwalior)
Dictionaries (Hash Maps) February 10, 2026 8 / 25
 Pseudocode: Updating a Key

myDict = {"Pizza": 10, "Burger": 5}

// Updating the value of an existing key

[Link]("Pizza", 12)

Output: {"Pizza": 12, "Burger": 5}

Dr. Dheeraj Assistant Professor (ABV-IIITM,

Data Structures:
Gwalior)
Dictionaries (Hash Maps) February 10, 2026 9 / 25
 Performance Comparison

Operation List/Array Dictionary

Search O(n) O(1)
Insert O(1) O(1)
Delete O(n) O(1)
Table: Average Time Complexities

Dr. Dheeraj Assistant Professor (ABV-IIITM,

Data Structures:
Gwalior)
Dictionaries (Hash Maps) February 10, 2026 10 / 25
 Practice Question 1

Scenario: You are building a student database. You want to store Student
IDs and Student Names.

Question: Which should be the Key and which should be the Value?
Why?

Dr. Dheeraj Assistant Professor (ABV-IIITM,

Data Structures:
Gwalior)
Dictionaries (Hash Maps) February 10, 2026 11 / 25
 Answer 1

Answer:
Key: Student ID (e.g., Roll Number)
Value: Student Name
Reasoning: Multiple students can have the same name (e.g., ”Rahul”), so
Names cannot be keys. Student IDs are unique and permanent.

Dr. Dheeraj Assistant Professor (ABV-IIITM,

Data Structures:
Gwalior)
Dictionaries (Hash Maps) February 10, 2026 12 / 25
 Practice Question 2

What will be the output of the following pseudocode?

D = CreateDictionary()
[Link]("A", 100)
[Link]("B", 200)
[Link]("A", 300)
print([Link]("A"))

Dr. Dheeraj Assistant Professor (ABV-IIITM,

Data Structures:
Gwalior)
Dictionaries (Hash Maps) February 10, 2026 13 / 25
 Answer 2

Output: 300

Explanation: Dictionaries do not allow duplicate keys. When you

put("A", 300), it overwrites the previous value of 100 associated with
key ”A”.

Dr. Dheeraj Assistant Professor (ABV-IIITM,

Data Structures:
Gwalior)
Dictionaries (Hash Maps) February 10, 2026 14 / 25
 Practice Question 3

True or False?

”A dictionary can have two different keys that point to the same value.”

Dr. Dheeraj Assistant Professor (ABV-IIITM,

Data Structures:
Gwalior)
Dictionaries (Hash Maps) February 10, 2026 15 / 25
 Answer 3

Answer: TRUE

Explanation: While Keys must be unique, Values do not have to be.

Example: {"Item1": 10, "Item2": 10} is perfectly valid.

Dr. Dheeraj Assistant Professor (ABV-IIITM,

Data Structures:
Gwalior)
Dictionaries (Hash Maps) February 10, 2026 16 / 25
 Practice Question 4

Trace the output:

D = {"Red": 1, "Blue": 2}
[Link]("Red")
print([Link]("Red"))

Dr. Dheeraj Assistant Professor (ABV-IIITM,

Data Structures:
Gwalior)
Dictionaries (Hash Maps) February 10, 2026 17 / 25
 Answer 4

Output: False (or 0)

Explanation: Once a key is removed, the dictionary no longer contains

that key-value pair.

Dr. Dheeraj Assistant Professor (ABV-IIITM,

Data Structures:
Gwalior)
Dictionaries (Hash Maps) February 10, 2026 18 / 25
 Practice Question 5

If a dictionary has 1,000,000 items, roughly how many steps does it take
to find a specific key if there are no collisions?

Dr. Dheeraj Assistant Professor (ABV-IIITM,

Data Structures:
Gwalior)
Dictionaries (Hash Maps) February 10, 2026 19 / 25
 Answer 5

Answer: 1 Step

Explanation: Dictionaries use Hashing to achieve O(1) time complexity.

The size of the dictionary doesn’t significantly change the search time.

Dr. Dheeraj Assistant Professor (ABV-IIITM,

Data Structures:
Gwalior)
Dictionaries (Hash Maps) February 10, 2026 20 / 25
 Common Errors to Avoid

KeyError: Trying to look up a key that doesn’t exist.

Mutable Keys: Trying to use a list as a key (most languages won’t
allow this).
Collisions: When two different keys produce the same hash (handled
internally by the data structure).

Dr. Dheeraj Assistant Professor (ABV-IIITM,

Data Structures:
Gwalior)
Dictionaries (Hash Maps) February 10, 2026 21 / 25
 Dictionary in Python (The most common usage)

# Creation
my_car = {"brand": "Tesla", "model": "S"}

# Access
print(my_car["brand"]) # Output: Tesla

# Adding
my_car["year"] = 2024

Dr. Dheeraj Assistant Professor (ABV-IIITM,

Data Structures:
Gwalior)
Dictionaries (Hash Maps) February 10, 2026 22 / 25
 When to use Dictionaries?

When you need to count occurrences (e.g., word frequency in a book).

When you need fast data retrieval by a specific label.
When storing configuration settings for an app.

Dr. Dheeraj Assistant Professor (ABV-IIITM,

Data Structures:
Gwalior)
Dictionaries (Hash Maps) February 10, 2026 23 / 25
 Summary

Dictionaries = Key-Value pairs.

Keys must be Unique.
Highly efficient (O(1) search).
Fundamental for modern web APIs and databases.

Dr. Dheeraj Assistant Professor (ABV-IIITM,

Data Structures:
Gwalior)
Dictionaries (Hash Maps) February 10, 2026 24 / 25
 Thank You!

Questions?

Dr. Dheeraj
Assistant Professor, IIITM

Dr. Dheeraj Assistant Professor (ABV-IIITM,

Data Structures:
Gwalior)
Dictionaries (Hash Maps) February 10, 2026 25 / 25
 Data Structures: Trees in the Real World
Industrial Applications and Problem Solving

Dr. Dheeraj
Assistant Professor, IIITM

February 12, 2026

Dr. Dheeraj Assistant Professor, IIITM Data Structures: Trees in the Real World February 12, 2026 1 / 21
1. What are Trees?

Definition: A non-linear hierarchical data structure consisting of

nodes connected by edges.
Industry Context: Used when data isn’t a simple list but has a
”Parent-Child” relationship.
Real World: Organization charts, Folder structures in
Windows/Linux.

Dr. Dheeraj Assistant Professor, IIITM Data Structures: Trees in the Real World February 12, 2026 2 / 21
2. Tree Anatomy

Root: The top node (e.g., C:/ drive).

Leaf: Nodes with no children (e.g., a .txt file).
Height/Depth: Critical for measuring performance in databases.

Dr. Dheeraj Assistant Professor, IIITM Data Structures: Trees in the Real World February 12, 2026 3 / 21
3. Binary Trees

Each node has at most two children.

Why? It simplifies search logic to a ”Yes/No” or ”Left/Right”
decision.
Industry Use: Decision Trees in Machine Learning (e.g., Credit Card
Approval).

Dr. Dheeraj Assistant Professor, IIITM Data Structures: Trees in the Real World February 12, 2026 4 / 21
4. Real World Scenario: File Systems

Problem: How does your OS find a file in a million folders?

Structure: N-ary Tree.
Optimization: B-Trees are used in file systems like NTFS and EXT4
to minimize disk reads.

Dr. Dheeraj Assistant Professor, IIITM Data Structures: Trees in the Real World February 12, 2026 5 / 21
5. Pseudo Code: Pre-order Traversal

Scenario: Creating a backup of a directory (Root first, then contents).

Pre-order Algorithm
Procedure PreOrder(node)
If node is null: return
Print([Link]) // Visit Root
PreOrder([Link])
PreOrder([Link])
End Procedure

Dr. Dheeraj Assistant Professor, IIITM Data Structures: Trees in the Real World February 12, 2026 6 / 21
6. Industry Challenge: Question 1

Scenario: You are building an E-commerce category menu (Electronics

− > Mobile − > Brand). The items are sorted alphabetically.
Question: Which traversal would you use to print the categories in a
sorted list from A to Z?

Dr. Dheeraj Assistant Professor, IIITM Data Structures: Trees in the Real World February 12, 2026 7 / 21
7. Answer 1: In-order Traversal

Answer: In-order Traversal on a Binary Search Tree (BST).

Logic: In-order visits (Left, Root, Right). In a BST, this always yields
a sorted sequence.
Real World: Used by SQL databases to return sorted query results
efficiently.

Dr. Dheeraj Assistant Professor, IIITM Data Structures: Trees in the Real World February 12, 2026 8 / 21
8. Binary Search Tree (BST)

Rule: Left Child < Root < Right Child.

Efficiency: Searching takes O(log N) time.
Comparison: Searching 1 million items takes only 20 steps!

Dr. Dheeraj Assistant Professor, IIITM Data Structures: Trees in the Real World February 12, 2026 9 / 21
9. Pseudo Code: Searching a Database

Search Algorithm
Function Search(root, target)
If root is null or [Link] == target:
return root
If target < [Link]:
return Search([Link], target)
Else:
return Search([Link], target)
End Function

Dr. Dheeraj Assistant Professor, IIITM Data Structures: Trees in the Real World February 12, 2026 10 / 21
10. Industry Challenge: Question 2

Scenario: You are designing a ”Undo” feature for a coding IDE where you
need to delete a specific version of code but keep the history structure
intact.
Question: If the versions are stored in a tree, what is the most complex
part of deleting a ”Parent” version?

Dr. Dheeraj Assistant Professor, IIITM Data Structures: Trees in the Real World February 12, 2026 11 / 21
11. Answer 2: Node Deletion with Two Children

The Problem: If you delete a node with two children, the tree
”breaks.”
Solution: Replace the deleted node with its In-order Successor (the
smallest value in the right subtree).
Industry Context: Essential in dynamic memory management and
database indexing.

Dr. Dheeraj Assistant Professor, IIITM Data Structures: Trees in the Real World February 12, 2026 12 / 21
12. AVL Trees (Self-Balancing)

The Issue: If we insert items in sorted order (1, 2, 3), the tree
becomes a Linked List (O(N)).
AVL Solution: Rotates itself to stay balanced.
Real World: High-frequency trading platforms where search latency
must be consistent.

Dr. Dheeraj Assistant Professor, IIITM Data Structures: Trees in the Real World February 12, 2026 13 / 21
13. Heaps in Industry

A special tree where the root is always the Max (or Min).
Real World: Task Scheduling in OS, Network traffic prioritization
(Priority Queues).
Industry Use: Uber/Ola finding the ”Nearest Driver.”

Dr. Dheeraj Assistant Professor, IIITM Data Structures: Trees in the Real World February 12, 2026 14 / 21
14. Industry Challenge: Question 3

Scenario: You are working at Google Search. When a user starts typing
”Tree...”, you want to suggest ”Treehouse”, ”Treenet”, etc.
Question: Is a standard Binary Tree efficient for this ”Auto-complete”
feature? If not, what is?

Dr. Dheeraj Assistant Professor, IIITM Data Structures: Trees in the Real World February 12, 2026 15 / 21
15. Answer 3: Trie (Prefix Tree)

Answer: No, use a Trie.

How it works: Each node represents a character. A path from root
to node represents a prefix.
Efficiency: Search depends on word length, not the number of total
words!

Dr. Dheeraj Assistant Professor, IIITM Data Structures: Trees in the Real World February 12, 2026 16 / 21
16. Trees in Web Development: The DOM

Every website is a tree called the Document Object Model.

<html> is the root; <body> and <head> are children.
Optimization: [Link] uses ”Virtual DOM” trees to find differences
and update only what’s needed.

Dr. Dheeraj Assistant Professor, IIITM Data Structures: Trees in the Real World February 12, 2026 17 / 21
17. Performance at Scale

Operation Average Worst Case

Search O(log N) O(N)
Insertion O(log N) O(N)
Deletion O(log N) O(N)
Table: Time Complexity for BST

Dr. Dheeraj Assistant Professor, IIITM Data Structures: Trees in the Real World February 12, 2026 18 / 21
18. Practice Problems for Students

1 The Router Problem: Routers use trees to store IP prefixes. If a

router has 50,000 routes, what tree type would you choose for the
fastest ”Longest Prefix Match”?
2 The Game AI: In a Chess game, the AI predicts future moves. This
”Game Tree” can be billions of nodes. How would you limit the tree
depth to ensure the computer moves within 5 seconds?

Dr. Dheeraj Assistant Professor, IIITM Data Structures: Trees in the Real World February 12, 2026 19 / 21
19. Conclusion

Trees are the backbone of hierarchical data.

Choice of tree (BST vs Trie vs B-Tree) depends on what you do
most: Search, Sort, or Prefix matching.
Next Step: Lab exercise on implementing an AVL tree rotation.

Dr. Dheeraj Assistant Professor, IIITM Data Structures: Trees in the Real World February 12, 2026 20 / 21
 Questions?
Thank You!
Dr. Dheeraj, IIITM

Dr. Dheeraj Assistant Professor, IIITM Data Structures: Trees in the Real World February 12, 2026 21 / 21
Data Structure Traversals: From Theory to Industry
Lecture Series - Data Structures & Algorithms

Dr. Dheeraj
Assistant Professor, IIITM

18-02-2026

Dr. Dheeraj DS Traversals 18-02-2026 1 / 20

What is Traversal?

Definition: The process of visiting every node in a data structure

exactly once in a specific order.
Importance: Foundation for searching, sorting, and reporting data.
Industry Context: Used in social media feeds (graphs), file systems
(trees), and network routing.

Dr. Dheeraj DS Traversals 18-02-2026 2 / 20

Tree Traversals

There are two main categories:

1 Depth-First Search (DFS)

Pre-order (Root, Left, Right)

In-order (Left, Root, Right)
Post-order (Left, Right, Root)
2 Breadth-First Search (BFS)
Level-order traversal

Dr. Dheeraj DS Traversals 18-02-2026 3 / 20

Scenario 1: File Systems (Pre-order)

Real-World Context: How does Windows Explorer or macOS Finder list

folders and files?
It visits the Parent Folder first, then dives into the Sub-folders.
This is a classic Pre-order Traversal.

Dr. Dheeraj DS Traversals 18-02-2026 4 / 20

Pseudo Code: Pre-order (Recursive)

Algorithm Preorder(node)
if node == NULL return
VISIT([Link]) // Process Root
Preorder([Link]) // Move Left
Preorder([Link]) // Move Right

Complexity: O(n) where n is the number of nodes.

Dr. Dheeraj DS Traversals 18-02-2026 5 / 20

Scenario 2: Excel Calculators (Post-order)

Real-World Context: To evaluate an expression like (3 + 5) ∗ 2, a

computer needs to solve the ”leaves” (3 and 5) before it can solve the
”root” (+).
This ”Bottom-Up” approach is Post-order Traversal.
Used in Compiler Design for Abstract Syntax Trees (AST).

Dr. Dheeraj DS Traversals 18-02-2026 6 / 20

Pseudo Code: Post-order (Recursive)

Algorithm Postorder(node)
if node == NULL return
Postorder([Link])
Postorder([Link])
VISIT([Link]) // Process Root last

Dr. Dheeraj DS Traversals 18-02-2026 7 / 20

Scenario 3: LinkedIn Connections (BFS)

Real-World Context: Finding ”1st-degree” connections, then

”2nd-degree.”
This explores level-by-level.
Breadth-First Search (BFS) uses a Queue data structure.

Dr. Dheeraj DS Traversals 18-02-2026 8 / 20

Pseudo Code: BFS (Iterative)

Algorithm BFS(root)
Create empty Queue Q
[Link](root)
while Q is not empty:
current = [Link]()
VISIT([Link])
if [Link]: [Link]([Link])
if [Link]: [Link]([Link])

Dr. Dheeraj DS Traversals 18-02-2026 9 / 20

Question 1: The Sorted Database

Problem: You have a Binary Search Tree (BST) containing employee IDs.
You need to print all IDs in ascending order to generate a payroll report.

Which traversal technique will you use and why?

Dr. Dheeraj DS Traversals 18-02-2026 10 / 20

Answer 1: In-order Traversal

Answer: **In-order Traversal** (Left, Root, Right).

Logic: In a BST, the left child is always smaller and the right child is
larger.
Visiting ”Left → Root → Right” naturally retrieves elements in
non-decreasing order.
Industry Use: Database indexing (B-Trees) uses variations of this for
range queries.

Dr. Dheeraj DS Traversals 18-02-2026 11 / 20

Question 2: Dependency Resolving

Problem: You are building a build-tool like ”Maven” or ”npm”. Package

A depends on B, and B depends on C. You must install C, then B, then A.

If these dependencies are modeled as a tree, which traversal ensures

children are processed before parents?

Dr. Dheeraj DS Traversals 18-02-2026 12 / 20

Answer 2: Post-order Traversal

Answer: **Post-order Traversal**.

Logic: It processes all sub-trees (dependencies) before visiting the
current node (the main package).
Industry Use: This is effectively a ”Topological Sort” in many
automation workflows.

Dr. Dheeraj DS Traversals 18-02-2026 13 / 20

Question 3: GPS Navigation

Problem: Google Maps needs to find the shortest path (minimum number
of turns) between two intersections in a city grid.

Would you use DFS or BFS to find the shortest path in an

unweighted graph?

Dr. Dheeraj DS Traversals 18-02-2026 14 / 20

Answer 3: Breadth-First Search (BFS)

Answer: **BFS**.
Logic: BFS explores all neighbors at distance 1, then distance 2. The
first time it hits the destination, it is guaranteed to be the shortest
path in terms of steps.
Industry Use: Peer-to-peer (P2P) networks use BFS to find the
nearest neighbor with a specific file chunk.

Dr. Dheeraj DS Traversals 18-02-2026 15 / 20

Graph Traversals

Graphs can have cycles, unlike trees.

Crucial Step: We must keep a ”Visited” set to avoid infinite loops.
DFS (Graph): Uses Stack (or recursion).
BFS (Graph): Uses Queue.

Dr. Dheeraj DS Traversals 18-02-2026 16 / 20

Industry Perspective: Stack Overflow

Recursive Traversals: Easier to write but can cause ”Stack

Overflow” errors if the tree is very deep (e.g., 1 million nodes).
Iterative Traversals: More robust for production-grade code.
Morris Traversal: A specialized O(1) space traversal used when
memory is extremely limited (embedded systems).

Dr. Dheeraj DS Traversals 18-02-2026 17 / 20

Quick Comparison

Traversal Structure Key Use Case

Pre-order Tree Copying directories
In-order BST Sorting data
Post-order Tree Deleting trees, Math
BFS Graph/Tree Shortest Path, Networking

Dr. Dheeraj DS Traversals 18-02-2026 18 / 20

Practice Questions

1 Scenario: A web crawler visits a page and finds 5 links. It follows the
first link, finds 5 more, and continues following the first link until it
hits a dead end.
Which traversal is this web crawler mimicking?

2 Coding Challenge: Write a pseudo-code for an **In-order traversal

without using recursion**. (Hint: You will need an explicit Stack).

Dr. Dheeraj DS Traversals 18-02-2026 19 / 20

Thank You!

Questions?

Contact: Dr. Dheeraj, Assistant Professor, IIITM

Dr. Dheeraj DS Traversals 18-02-2026 20 / 20

 Data Structures: Binary Trees Masterclass
Properties, Traversals, and Reconstruction

Dr. Dheeraj

Assistant Professor, IIITM

February 17, 2026

Dr. Dheeraj (Assistant Professor, IIITM) Data Structures: Binary Trees Masterclass February 17, 2026 1 / 20
 Lecture Overview

1 Basic Terminology & Visual Anatomy

2 Binary Tree Properties (Height, Edges, Nodes)
3 Traversal Techniques (Pre, In, Post)
4 The ”Why” of Conversions
5 Step-by-Step Reconstruction Problems
6 Practice Exercises

Dr. Dheeraj (Assistant Professor, IIITM) Data Structures: Binary Trees Masterclass February 17, 2026 2 / 20
 Tree Terminology

Root: Node with no parent (Origin).

Leaf: Node with no children (Terminal).
Internal Node: Node with at least one child.
Ancestors: All nodes on the path from root to that node.
Descendants: All nodes in the subtrees of that node.

Dr. Dheeraj (Assistant Professor, IIITM) Data Structures: Binary Trees Masterclass February 17, 2026 3 / 20
 Problem: Edges and Height

Question
1. If a tree has N nodes, how many edges does it have?
2. What is the maximum height of a tree with N nodes?
3. What is the minimum height?

Dr. Dheeraj (Assistant Professor, IIITM) Data Structures: Binary Trees Masterclass February 17, 2026 4 / 20
 Solution: Edges and Height

Edges: Always N − 1 (every node except root has 1 incoming edge).

Max Height: N (happens in a skewed/degenerate tree).
Min Height: ⌈log2 (N + 1)⌉ (happens in a complete binary tree).
Complexity: Finding height takes O(N) as we must visit every node.

Dr. Dheeraj (Assistant Professor, IIITM) Data Structures: Binary Trees Masterclass February 17, 2026 5 / 20
 Problem: Internal vs Leaf Nodes

Question
In a strictly binary tree (every node has 0 or 2 children), if there are L leaf
nodes, how many internal nodes (I ) are there?

Dr. Dheeraj (Assistant Professor, IIITM) Data Structures: Binary Trees Masterclass February 17, 2026 6 / 20
 Solution: Internal vs Leaf Nodes

Formula: L = I + 1
Proof:
For 1 leaf, I = 0 (Root only).
For 2 leaves, I = 1.
Therefore, I = L − 1.
Total Nodes: N = L + I = 2L − 1.

Dr. Dheeraj (Assistant Professor, IIITM) Data Structures: Binary Trees Masterclass February 17, 2026 7 / 20
 Binary Tree Traversals

To visit every node exactly once:

Preorder (NLR): Root → Left → Right.
Inorder (LNR): Left → Root → Right.
Postorder (LRN): Left → Right → Root.

2 3

4 5

Dr. Dheeraj (Assistant Professor, IIITM) Data Structures: Binary Trees Masterclass February 17, 2026 8 / 20
 Why move to Conversions?

Problem: Linear arrays/strings don’t naturally show hierarchy.

Storage: We need to save trees in files/databases.
Uniqueness: One traversal (like Inorder) is not enough to rebuild the
original tree.
Recovery: If we have two specific traversals, we can mathematically
”reconstruct” the exact structure.

Dr. Dheeraj (Assistant Professor, IIITM) Data Structures: Binary Trees Masterclass February 17, 2026 9 / 20
 Type 1: Inorder to Preorder

Problem Statement
Reconstruct the tree:
Inorder: D, B, E, A, F, C
Preorder: A, B, D, E, C, F

Dr. Dheeraj (Assistant Professor, IIITM) Data Structures: Binary Trees Masterclass February 17, 2026 10 / 20
 Solution: Inorder to Preorder

Root is A (First in Preorder).

Left Subtree (Inorder): {D, B, E}.
Right Subtree (Inorder): {F, C}.
Final Tree:
A

B C

D E F

Dr. Dheeraj (Assistant Professor, IIITM) Data Structures: Binary Trees Masterclass February 17, 2026 11 / 20
 Type 2: Inorder to Postorder

Problem Statement
Reconstruct the tree:
Inorder: 4, 2, 5, 1, 3
Postorder: 4, 5, 2, 3, 1

Dr. Dheeraj (Assistant Professor, IIITM) Data Structures: Binary Trees Masterclass February 17, 2026 12 / 20
 Solution: Inorder to Postorder

Root is 1 (Last in Postorder).

In Inorder: Left={4,2,5}, Right={3}.
In Postorder: Left={4,5,2}, Right={3}.

2 3

4 5

Dr. Dheeraj (Assistant Professor, IIITM) Data Structures: Binary Trees Masterclass February 17, 2026 13 / 20
 Type 3: Preorder to Postorder

Problem Statement
Given Preorder and Postorder, can we always find a unique tree?

Dr. Dheeraj (Assistant Professor, IIITM) Data Structures: Binary Trees Masterclass February 17, 2026 14 / 20
 Solution: Preorder to Postorder

Answer: NO.
Without Inorder, we cannot distinguish between a left-child and a
right-child.
Example: Preorder: AB, Postorder: BA. Could be A as root with B
as left child OR right child.
Exception: Only possible for Full Binary Trees.

Dr. Dheeraj (Assistant Professor, IIITM) Data Structures: Binary Trees Masterclass February 17, 2026 15 / 20
 Type 4: Postorder to Inorder

Problem Statement
Postorder: D, E, B, F, C, A
Inorder: D, B, E, A, F, C

Dr. Dheeraj (Assistant Professor, IIITM) Data Structures: Binary Trees Masterclass February 17, 2026 16 / 20
 Solution: Postorder to Inorder

Root = A.
Since B is to the left of A in Inorder, B is the root of the left subtree.
Structure:
A

B C

D E F

Dr. Dheeraj (Assistant Professor, IIITM) Data Structures: Binary Trees Masterclass February 17, 2026 17 / 20
 Type 5: Postorder to Preorder

Problem Statement
Reconstruct from:
Postorder: 8, 9, 4, 10, 5, 2, 6, 7, 3, 1
Preorder: 1, 2, 4, 8, 9, 5, 10, 3, 6, 7

Dr. Dheeraj (Assistant Professor, IIITM) Data Structures: Binary Trees Masterclass February 17, 2026 18 / 20
 Solution: Postorder to Preorder

Note: Only works for Full Binary Trees.

Root = 1.
Next in Preorder is 2 (Left Root).
In Postorder, 2 appears after 8, 9, 4, 10, 5. So these are the left
subtree.
1

2 3

4 5 6 7

8 9 10

Dr. Dheeraj (Assistant Professor, IIITM) Data Structures: Binary Trees Masterclass February 17, 2026 19 / 20
 Summary and Complexity

Operation Complexity
Traversal (All) O(N)
Height Calculation O(N)
Reconstruction O(N 2 ) (or O(N) with Hashmap)

Key Takeaway: Inorder is the anchor for unique reconstruction!

Dr. Dheeraj (Assistant Professor, IIITM) Data Structures: Binary Trees Masterclass February 17, 2026 20 / 20
 Binary Search Tree Traversals

Dr. Dheeraj

ABV-IIITM Gwalior
BEE and IMG

March 15, 2026

Dr. Dheeraj (ABV-IIITM Gwalior BEE and IMG) Binary Search Tree Traversals March 15, 2026 1 / 19
 What is Tree Traversal?

Traversal means **visiting every node of a tree exactly once**.

Types of traversal:
Inorder
Preorder
Postorder

Dr. Dheeraj (ABV-IIITM Gwalior BEE and IMG) Binary Search Tree Traversals March 15, 2026 2 / 19
 Example Tree

We will use the following tree for all examples.

B C

D E F G

Dr. Dheeraj (ABV-IIITM Gwalior BEE and IMG) Binary Search Tree Traversals March 15, 2026 3 / 19
 Inorder Traversal

Rule:

Left → Root → Right

Steps:
Visit left subtree
Visit root
Visit right subtree

Dr. Dheeraj (ABV-IIITM Gwalior BEE and IMG) Binary Search Tree Traversals March 15, 2026 4 / 19
 Inorder Example

Tree:

B C

D E F G

Inorder Output:

D B E AF C G

Dr. Dheeraj (ABV-IIITM Gwalior BEE and IMG) Binary Search Tree Traversals March 15, 2026 5 / 19
 Preorder Traversal

Rule:

Root → Left → Right

Steps:
Visit root
Visit left subtree
Visit right subtree

Dr. Dheeraj (ABV-IIITM Gwalior BEE and IMG) Binary Search Tree Traversals March 15, 2026 6 / 19
 Preorder Example

Using the same tree.

Preorder Output:

AB D E C F G

Dr. Dheeraj (ABV-IIITM Gwalior BEE and IMG) Binary Search Tree Traversals March 15, 2026 7 / 19
 Postorder Traversal

Rule:

Left → Right → Root

Steps:
Visit left subtree
Visit right subtree
Visit root

Dr. Dheeraj (ABV-IIITM Gwalior BEE and IMG) Binary Search Tree Traversals March 15, 2026 8 / 19
 Postorder Example

Postorder Output:

D E B F G C A

Dr. Dheeraj (ABV-IIITM Gwalior BEE and IMG) Binary Search Tree Traversals March 15, 2026 9 / 19
 Inorder Algorithm

1: if node ̸= NULL then

2: inorder(left)
3: print(node)
4: inorder(right)
5: end if

Dr. Dheeraj (ABV-IIITM Gwalior BEE and IMG) Binary Search Tree Traversals March 15, 2026 10 / 19
 Preorder Algorithm

1: if node ̸= NULL then

2: print(node)
3: preorder(left)
4: preorder(right)
5: end if

Dr. Dheeraj (ABV-IIITM Gwalior BEE and IMG) Binary Search Tree Traversals March 15, 2026 11 / 19
 Postorder Algorithm

1: if node ̸= NULL then

2: postorder(left)
3: postorder(right)
4: print(node)
5: end if

Dr. Dheeraj (ABV-IIITM Gwalior BEE and IMG) Binary Search Tree Traversals March 15, 2026 12 / 19
 Real World Examples

Inorder
Produces sorted order in BST
Used in database indexing
Preorder
Used to copy tree structures
Used in prefix expressions
Postorder
Used in postfix expression evaluation
Used for deleting trees

Dr. Dheeraj (ABV-IIITM Gwalior BEE and IMG) Binary Search Tree Traversals March 15, 2026 13 / 19
 Problem 1

Given Tree

2 3

4 5

Find Inorder traversal.

Dr. Dheeraj (ABV-IIITM Gwalior BEE and IMG) Binary Search Tree Traversals March 15, 2026 14 / 19
 Solution 1

Tree:

1
Steps:
Left subtree → Root → Right subtree
Answer:

42513

Dr. Dheeraj (ABV-IIITM Gwalior BEE and IMG) Binary Search Tree Traversals March 15, 2026 15 / 19
 Problem 2

Given preorder:

AB D E C F G
Find postorder.

Dr. Dheeraj (ABV-IIITM Gwalior BEE and IMG) Binary Search Tree Traversals March 15, 2026 16 / 19
 Solution 2

Postorder:

D E B F G C A

Dr. Dheeraj (ABV-IIITM Gwalior BEE and IMG) Binary Search Tree Traversals March 15, 2026 17 / 19
 Practice Questions

1 Find preorder traversal.

2 Convert preorder to postorder.
3 Convert inorder to preorder.
4 Why inorder traversal gives sorted output in BST?

Dr. Dheeraj (ABV-IIITM Gwalior BEE and IMG) Binary Search Tree Traversals March 15, 2026 18 / 19
 Thank You

Dr. Dheeraj (ABV-IIITM Gwalior BEE and IMG) Binary Search Tree Traversals March 15, 2026 19 / 19
Balanced BST: AVL Trees and 2-4 Trees

Dr. Dheeraj

IIITM Gwalior
Motivation

10

20

30

40
Skewed BST (Worst Case)
Search Time = O(n)
Balanced BST Idea

30

20 40

10 25
Balanced Tree
Height = O(log n)
AVL Tree Concept

30

20 40

10 25
Balance Factor = Height(left) - Height(right)
Unbalanced AVL Example

10

20

30
BF = -2 → Rotation required
LL Rotation

30

20

Before: 10
20

After: 10 30
RR Rotation

10

20

Before: 30
20

After: 10 30
LR Rotation

30

10

Before: 20
20

After: 10 30
RL Rotation

10

30

Before: 20
20

After: 10 30
AVL Insertion Example

Insert: 10 → 20 → 30
10

20

30
RR Rotation applied
AVL Deletion

30

20 40

35 50
Rebalance after deletion
AVL Complexity

30

20 40
All operations: O(log n)
2-4 Tree Structure

20 40

10 30 50
Multi-key nodes
2-4 Tree Balanced Property

20 40

10 30 50 60
All leaves same level
Insertion in 2-4 Tree

10 20 30
Overflow → Split
Split Operation

Before: 10 20 30
20

After: 10 30
Real World Problem 1

Sorted insertion in DB index

10

20

30
What to do?
Answer

20

10 30
Use AVL rotations
Real World Problem 2

Insert: 10,20,30,40 in 2-4 tree

10 20 30
Answer

20

10 30 40
Comparison

AVL

2-4

Strict Rotations O(log n)

Multi Split Disk

Strict Balance Disk Friendly

Summary

Balanced BST

AVL 2-4 Tree

Efficient: O(log n)
 Data Structures: Red-Black Trees
In-Depth Analysis and Operations

Dr. Dheeraj

ABV-IIITM, Gwalior
BEE and IMG Batches

March 22, 2026

Dr. Dheeraj (ABV-IIITM) Red-Black Trees March 22, 2026 1 / 15

Introduction to Red-Black Trees

A Red-Black Tree is a self-balancing Binary Search Tree (BST).

Why do we need it? Standard BSTs can become skewed (O(n)),
losing efficiency.
RBTs ensure the tree height remains O(log n) by applying specific
coloring rules.
Used extensively in system libraries (e.g., C++ STL std::map, Java
TreeMap).

Dr. Dheeraj (ABV-IIITM) Red-Black Trees March 22, 2026 2 / 15

The 5 Critical Properties

To be a valid Red-Black Tree, every node must follow these rules:

1 Every node is either Red or Black.
2 The root is always Black.
3 Every leaf (NIL) is Black.
4 If a node is Red, then both its children are Black (No two reds in a
row).
5 For each node, all simple paths from the node to descendant leaves
contain the same number of black nodes (Black Height).

Dr. Dheeraj (ABV-IIITM) Red-Black Trees March 22, 2026 3 / 15

Concept of Black Height (bh)

bh(x) is the number of black nodes on any path from node x to a

leaf, not counting x itself.
Theorem: A red-black tree with n internal nodes has height
h ≤ 2 log(n + 1).
This logarithmic bound is what guarantees performance.

Dr. Dheeraj (ABV-IIITM) Red-Black Trees March 22, 2026 4 / 15

Real-World Applications

Linux Kernel
Completely Fair Scheduler (CFS) uses RBTs to manage timeline-ordered
process execution.

Database Indexing
Used in memory-resident databases where predictable search time is more
critical than disk I/O optimization (where B-Trees shine).

Network Routing
Used in high-speed routers to store and retrieve IP prefixes efficiently.

Dr. Dheeraj (ABV-IIITM) Red-Black Trees March 22, 2026 5 / 15

Visualizing a Red-Black Tree

13

8 17

1 11 15 25

Note: All NIL children (not shown) are black. Black height from root = 2.

Dr. Dheeraj (ABV-IIITM) Red-Black Trees March 22, 2026 6 / 15

Tree Operations: Left Rotation

Rotations are used to decrease the height of a subtree.

Left-Rotate(T, x):
x y
Rotate

α y x γ

β γ α β

Dr. Dheeraj (ABV-IIITM) Red-Black Trees March 22, 2026 7 / 15

Insertion: The Strategy

1 Perform a standard BST insertion.

2 Color the new node Red.
3 Fix any violations of RBT properties (specifically property 4: no two
reds).
Why Red? Because adding a red node doesn’t change the black height
(Prop 5), which is the hardest property to maintain.

Dr. Dheeraj (ABV-IIITM) Red-Black Trees March 22, 2026 8 / 15

Insertion Case 1: Uncle is Red

Scenario: Node z is red, Parent p is red, and Uncle y is red.

Action: Recolor parent and uncle to Black; recolor grandparent to
Red.
Move the ”problem” up to the grandparent.

Dr. Dheeraj (ABV-IIITM) Red-Black Trees March 22, 2026 9 / 15

Insertion Case 2 & 3: Uncle is Black

Case 2 (Triangle): z is an inner grandchild. Perform a rotation to

turn it into Case 3.
Case 3 (Line): z is an outer grandchild. Rotate the grandparent and
swap colors of parent and grandparent.

Dr. Dheeraj (ABV-IIITM) Red-Black Trees March 22, 2026 10 / 15

Problem 1: Identification

Is the following tree a valid Red-Black Tree? Why or why not?

10

5 15

2 7

Dr. Dheeraj (ABV-IIITM) Red-Black Trees March 22, 2026 11 / 15

Solution 1: Identification

Answer: No.
Violation: Property 4. Node 5 and its child Node 2 are both Red.
Red-Red conflicts are not allowed.

Dr. Dheeraj (ABV-IIITM) Red-Black Trees March 22, 2026 12 / 15

Problem 2: Insertion

Insert the value 15 into an empty Red-Black Tree. Then insert 10. What
are the colors?

Dr. Dheeraj (ABV-IIITM) Red-Black Trees March 22, 2026 13 / 15

Solution 2: Insertion

Step 1: Insert 15. It is the root. By Property 2, it must be Black.

Step 2: Insert 10. Standard BST puts it to the left. It starts Red.
Check: No properties violated.
15

10

Dr. Dheeraj (ABV-IIITM) Red-Black Trees March 22, 2026 14 / 15

Final Practice Problems

1 Draw the RBT resulting from inserting {10, 20, 30, 15} in order.
2 What is the maximum possible height of a Red-Black Tree with 7
internal nodes?
3 If a Red-Black Tree has a black height of 3, what is the minimum
number of nodes it can have?
4 Explain why the root of a Red-Black Tree can never be red even after
a rotation.

Dr. Dheeraj (ABV-IIITM) Red-Black Trees March 22, 2026 15 / 15

2-4 Trees in Data Structures

Dr. Dheeraj
Assistant Professor
IIITM Gwalior

Batch: BEE and IMG

March 2026
Introduction

▶ 2-4 Trees are self-balancing multi-way search trees.

▶ Each node can contain 1 to 3 keys.
▶ Ensures all leaves remain at the same level.
▶ Used in databases and file systems.
Basic Structure

A node can have multiple keys and children.

20 — 40

10 30 50 — 60
Types of Nodes

Different node types in 2-4 Trees:

10 10 — 20 10 — 20 — 30

▶ 2-node → 1 key
▶ 3-node → 2 keys
▶ 4-node → 3 keys
Balanced Property

All leaves are at the same depth.

20

10 30
Insertion Step 1

Insert first element:

10
Insertion Step 2

Insert 20 into same node:

10 — 20
Insertion Step 3

Insert 30 → Node becomes full:

10 — 20 — 30
Problem 1

Insert 40 into the tree. What happens?

Solution 1

Split occurs: middle element moves up

20

10 30 — 40
Insertion Continued

Insert 50 into right subtree:

20

10 30 — 40 — 50
Problem 2

Insert 60. What will happen?

Solution 2

Split again and promote key

20 — 40

10 30 50 — 60
Search Operation

Example: Search for 50

▶ Compare with root (20, 40)
▶ Move to right subtree
▶ Found in node (50, 60)
Deletion Concept

▶ Delete from leaf if possible

▶ Borrow from sibling if underflow
▶ Merge nodes if borrowing fails
Problem 3

Delete 10 from the tree

Solution 3

Handle underflow using borrow/merge

20 — 40

15 30 50 — 60
Real World Applications

▶ Database indexing (B-Trees)

▶ File systems
▶ Efficient searching systems
Advantages

▶ Always balanced
▶ Fast operations
▶ Efficient storage
Complexity

▶ Search: O(log n)
▶ Insert: O(log n)
▶ Delete: O(log n)
Problem 4

Insert: 5, 15, 25
Solution 4

15

5 25
Key Insight

▶ Splitting keeps tree balanced

▶ Height grows slowly
▶ Guarantees efficient operations
Practice Questions

1. Insert sequence: 10, 20, 30, 40, 50

2. Show all splits
3. Perform deletion
4. Draw final tree
Conclusion

▶ 2-4 Trees maintain balance

▶ Used in real systems
▶ Foundation for B-Trees
 B-Trees in Data Structures

Dr. Dheeraj
Assistant Professor, IIITM Gwalior

Data Structures - BEE and IMG Batch

25 March 2026

Dr. Dheeraj Assistant Professor, IIITM Gwalior (DataB-Trees

Structures
in Data
- BEE
Structures
and IMG Batch) 25 March 2026 1 / 26
 Motivation (Real World)

Databases store millions of records on disk

Disk access is slow compared to RAM
Goal: minimize disk reads (I/O operations)
Solution: B-Trees (wide nodes, small height)

Dr. Dheeraj Assistant Professor, IIITM Gwalior (DataB-Trees

Structures
in Data
- BEE
Structures
and IMG Batch) 25 March 2026 2 / 26
 Where B-Trees are Used

Database Indexing (MySQL, PostgreSQL)

File Systems (NTFS, EXT4)
Search Engines (index lookup)
Key-Value Stores

Dr. Dheeraj Assistant Professor, IIITM Gwalior (DataB-Trees

Structures
in Data
- BEE
Structures
and IMG Batch) 25 March 2026 3 / 26
 Definition

B-Tree of order m:
Max children = m
Min children = ⌈m/2⌉
Keys = children - 1
All leaves at same level

Dr. Dheeraj Assistant Professor, IIITM Gwalior (DataB-Trees

Structures
in Data
- BEE
Structures
and IMG Batch) 25 March 2026 4 / 26
 Search Algorithm

1 Start at root
2 Compare key with node values
3 Move to appropriate child
4 Repeat until found or NULL

Dr. Dheeraj Assistant Professor, IIITM Gwalior (DataB-Trees

Structures
in Data
- BEE
Structures
and IMG Batch) 25 March 2026 5 / 26
 Insertion Algorithm

1 Insert key in leaf node

2 If overflow:
Split node
Promote middle key
3 Repeat upwards if needed

Dr. Dheeraj Assistant Professor, IIITM Gwalior (DataB-Trees

Structures
in Data
- BEE
Structures
and IMG Batch) 25 March 2026 6 / 26
 Deletion Algorithm

Case 1: Leaf deletion

Case 2: Borrow from sibling
Case 3: Merge nodes

Dr. Dheeraj Assistant Professor, IIITM Gwalior (DataB-Trees

Structures
in Data
- BEE
Structures
and IMG Batch) 25 March 2026 7 / 26
 Problem 1: Insertion

Insert: 10, 20, 5 into B-Tree (order 3)

Dr. Dheeraj Assistant Professor, IIITM Gwalior (DataB-Trees

Structures
in Data
- BEE
Structures
and IMG Batch) 25 March 2026 8 / 26
 Solution 1 Step 1

5 — 10 — 20

Overflow occurs

Dr. Dheeraj Assistant Professor, IIITM Gwalior (DataB-Trees

Structures
in Data
- BEE
Structures
and IMG Batch) 25 March 2026 9 / 26
 Solution 1 Step 2 (Split)

10

5 20

Dr. Dheeraj Assistant Professor, IIITM Gwalior (DataB-Trees

Structures
in Data
- BEE
Structures
and IMG Batch) 25 March 2026 10 / 26
 Problem 2: Insertion

Insert: 10, 20, 30, 40, 50

Dr. Dheeraj Assistant Professor, IIITM Gwalior (DataB-Trees

Structures
in Data
- BEE
Structures
and IMG Batch) 25 March 2026 11 / 26
 Solution 2 Step 1

10 — 20 — 30

Dr. Dheeraj Assistant Professor, IIITM Gwalior (DataB-Trees

Structures
in Data
- BEE
Structures
and IMG Batch) 25 March 2026 12 / 26
 Solution 2 Step 2

20

10 30 — 40 — 50

Dr. Dheeraj Assistant Professor, IIITM Gwalior (DataB-Trees

Structures
in Data
- BEE
Structures
and IMG Batch) 25 March 2026 13 / 26
 Problem 3: Deletion

Delete 40 from tree

Dr. Dheeraj Assistant Professor, IIITM Gwalior (DataB-Trees

Structures
in Data
- BEE
Structures
and IMG Batch) 25 March 2026 14 / 26
 Solution 3

20

10 30

Simple leaf deletion

Dr. Dheeraj Assistant Professor, IIITM Gwalior (DataB-Trees

Structures
in Data
- BEE
Structures
and IMG Batch) 25 March 2026 15 / 26
 Problem 4: Deletion with Borrow

Delete 10

Dr. Dheeraj Assistant Professor, IIITM Gwalior (DataB-Trees

Structures
in Data
- BEE
Structures
and IMG Batch) 25 March 2026 16 / 26
 Solution 4

Borrow from sibling

Adjust parent key

Dr. Dheeraj Assistant Professor, IIITM Gwalior (DataB-Trees

Structures
in Data
- BEE
Structures
and IMG Batch) 25 March 2026 17 / 26
 Problem 5: Deletion with Merge

Delete 30

Dr. Dheeraj Assistant Professor, IIITM Gwalior (DataB-Trees

Structures
in Data
- BEE
Structures
and IMG Batch) 25 March 2026 18 / 26
 Solution 5

Merge nodes
Reduce tree height

Dr. Dheeraj Assistant Professor, IIITM Gwalior (DataB-Trees

Structures
in Data
- BEE
Structures
and IMG Batch) 25 March 2026 19 / 26
 Problem 6: Update

Update key 20 to 25

Dr. Dheeraj Assistant Professor, IIITM Gwalior (DataB-Trees

Structures
in Data
- BEE
Structures
and IMG Batch) 25 March 2026 20 / 26
 Solution 6

Search key 20
Replace with 25
Structure unchanged

Dr. Dheeraj Assistant Professor, IIITM Gwalior (DataB-Trees

Structures
in Data
- BEE
Structures
and IMG Batch) 25 March 2026 21 / 26
 Real World Scenario

Searching student record in university database

Each node = disk block
Keys = student IDs
Fast lookup using B-Tree index

Dr. Dheeraj Assistant Professor, IIITM Gwalior (DataB-Trees

Structures
in Data
- BEE
Structures
and IMG Batch) 25 March 2026 22 / 26
 Another Real World Example

Banking system transaction lookup

File systems directory search
Google indexing large datasets

Dr. Dheeraj Assistant Professor, IIITM Gwalior (DataB-Trees

Structures
in Data
- BEE
Structures
and IMG Batch) 25 March 2026 23 / 26
 Complexity

Search: O(log n)
Insert: O(log n)
Delete: O(log n)

Dr. Dheeraj Assistant Professor, IIITM Gwalior (DataB-Trees

Structures
in Data
- BEE
Structures
and IMG Batch) 25 March 2026 24 / 26
 Practice Questions

1 Insert: 15, 25, 35, 45, 55 and draw tree

2 Delete: 25 and show all steps
3 Construct B-Tree of order 4
4 Explain real-world usage of B-Trees

Dr. Dheeraj Assistant Professor, IIITM Gwalior (DataB-Trees

Structures
in Data
- BEE
Structures
and IMG Batch) 25 March 2026 25 / 26
 Summary

B-Trees reduce disk I/O

Balanced and efficient
Core concept in databases

Dr. Dheeraj Assistant Professor, IIITM Gwalior (DataB-Trees

Structures
in Data
- BEE
Structures
and IMG Batch) 25 March 2026 26 / 26
 Geometric Data Structures

Dr. Dheeraj
Assistant Professor, IIITM Gwalior

Batch: BEE and IMG

8 April 2026

Batch: BEE and IMG 8 April 2026

Dr. Dheeraj Assistant Professor, IIITM Gwalior Geometric Data Structures 1 / 26
 Introduction

Geometric Data Structures store spatial data efficiently

Used for points, lines, regions
Applications: Graphics, AI, GIS

Batch: BEE and IMG 8 April 2026

Dr. Dheeraj Assistant Professor, IIITM Gwalior Geometric Data Structures 2 / 26
 Basic Concepts

Points in 2D: (x,y)

Distance formula
Slope and orientation

Batch: BEE and IMG 8 April 2026

Dr. Dheeraj Assistant Professor, IIITM Gwalior Geometric Data Structures 3 / 26
 2D Points Representation

P(2,2)

Batch: BEE and IMG 8 April 2026

Dr. Dheeraj Assistant Professor, IIITM Gwalior Geometric Data Structures 4 / 26
 Line Segment Intersection

Check if two line segments intersect

Based on orientation tests

Batch: BEE and IMG 8 April 2026

Dr. Dheeraj Assistant Professor, IIITM Gwalior Geometric Data Structures 5 / 26
 Problem 1

Check if two segments intersect: A(1,1), B(4,4), C(1,4), D(4,1)

Batch: BEE and IMG 8 April 2026

Dr. Dheeraj Assistant Professor, IIITM Gwalior Geometric Data Structures 6 / 26
 Solution 1

Compute orientations
Segments intersect

Batch: BEE and IMG 8 April 2026

Dr. Dheeraj Assistant Professor, IIITM Gwalior Geometric Data Structures 7 / 26
 Convex Hull

Smallest polygon enclosing all points

Algorithms: Graham Scan, Jarvis March

Batch: BEE and IMG 8 April 2026

Dr. Dheeraj Assistant Professor, IIITM Gwalior Geometric Data Structures 8 / 26
 Convex Hull Example

Batch: BEE and IMG 8 April 2026

Dr. Dheeraj Assistant Professor, IIITM Gwalior Geometric Data Structures 9 / 26
 Problem 2

Find convex hull for given points

Batch: BEE and IMG 8 April 2026

Dr. Dheeraj Assistant Professor, IIITM Gwalior Geometric Data Structures 10 / 26
 Solution 2

Apply Graham Scan

Batch: BEE and IMG 8 April 2026

Dr. Dheeraj Assistant Professor, IIITM Gwalior Geometric Data Structures 11 / 26
 Closest Pair of Points

Find minimum distance

Brute force vs Divide & Conquer

Batch: BEE and IMG 8 April 2026

Dr. Dheeraj Assistant Professor, IIITM Gwalior Geometric Data Structures 12 / 26
 Problem 3

Find closest pair among given points

Batch: BEE and IMG 8 April 2026

Dr. Dheeraj Assistant Professor, IIITM Gwalior Geometric Data Structures 13 / 26
 Solution 3

Use divide and conquer

Batch: BEE and IMG 8 April 2026

Dr. Dheeraj Assistant Professor, IIITM Gwalior Geometric Data Structures 14 / 26
 Range Searching

Query points inside region

Applications in GIS

Batch: BEE and IMG 8 April 2026

Dr. Dheeraj Assistant Professor, IIITM Gwalior Geometric Data Structures 15 / 26
 k-d Tree

Space partitioning structure

Efficient nearest neighbor search

Batch: BEE and IMG 8 April 2026

Dr. Dheeraj Assistant Professor, IIITM Gwalior Geometric Data Structures 16 / 26
 k-d Tree Partition

Batch: BEE and IMG 8 April 2026

Dr. Dheeraj Assistant Professor, IIITM Gwalior Geometric Data Structures 17 / 26
 Problem 4

Insert points into k-d tree

Batch: BEE and IMG 8 April 2026

Dr. Dheeraj Assistant Professor, IIITM Gwalior Geometric Data Structures 18 / 26
 Solution 4

Alternate splitting dimensions

Batch: BEE and IMG 8 April 2026

Dr. Dheeraj Assistant Professor, IIITM Gwalior Geometric Data Structures 19 / 26
 Quad Tree

Divide space into 4 regions

Used in image processing

Batch: BEE and IMG 8 April 2026

Dr. Dheeraj Assistant Professor, IIITM Gwalior Geometric Data Structures 20 / 26
 Sweep Line Algorithm

Process events in sorted order

Used for intersection detection

Batch: BEE and IMG 8 April 2026

Dr. Dheeraj Assistant Professor, IIITM Gwalior Geometric Data Structures 21 / 26
 Problem 5

Detect intersections using sweep line

Batch: BEE and IMG 8 April 2026

Dr. Dheeraj Assistant Professor, IIITM Gwalior Geometric Data Structures 22 / 26
 Solution 5

Sort events and process

Batch: BEE and IMG 8 April 2026

Dr. Dheeraj Assistant Professor, IIITM Gwalior Geometric Data Structures 23 / 26
 Real World Applications

Google Maps (GIS)

Robotics path planning
Machine learning (nearest neighbors)

Batch: BEE and IMG 8 April 2026

Dr. Dheeraj Assistant Professor, IIITM Gwalior Geometric Data Structures 24 / 26
 Practice Questions

1 Explain convex hull

2 Solve closest pair problem
3 Explain kd-tree
4 What is sweep line algorithm?

Batch: BEE and IMG 8 April 2026

Dr. Dheeraj Assistant Professor, IIITM Gwalior Geometric Data Structures 25 / 26
 Thank You

Questions?

Batch: BEE and IMG 8 April 2026

Dr. Dheeraj Assistant Professor, IIITM Gwalior Geometric Data Structures 26 / 26
KD-Tree Concept and Problem Solving

Dr. Dheeraj
Assistant Professor, IIITM Gwalior

8 April 2026
Batch: BEE and IMG
KD-Tree: Definition

▶ Binary tree for k-dimensional points

▶ Recursively partitions space
▶ Alternates splitting dimension at each level
Why KD-Tree?

▶ Brute force nearest neighbor: O(n)

▶ KD-Tree average: O(log n)
▶ Reduces search space using partitioning
Splitting Strategy

▶ Level 0: split by x-axis

▶ Level 1: split by y-axis
▶ Alternate recursively
KD-Tree Visualization

▶ Vertical split
▶ Horizontal split
▶ Creates regions
Example Points

▶ (2,3), (5,4), (9,6)

▶ (4,7), (8,1), (7,2)
Step 1: Root Selection

▶ Sort by x-coordinate
▶ Median = (7,2)
▶ Root node created
Step 2: Left/Right Split

▶ Left: (2,3), (5,4), (4,7)

▶ Right: (9,6), (8,1)
▶ Split by y-axis
KD-Tree Structure

(7,2)

(5,4) (9,6)

(2,3) (4,7)(8,1)
Nearest Neighbor Search

▶ Traverse tree
▶ Compare distances
▶ Prune subtrees
Range Search

▶ Query rectangular region

▶ Skip irrelevant partitions
Problem 1

Construct KD-tree for:

▶ (1,2), (3,6), (5,4), (7,8)
Solution 1

▶ Sort by x → median (5,4)

▶ Left: (1,2), (3,6)
▶ Right: (7,8)
Problem 2

Find nearest neighbor of (6,5)

▶ Points: (2,3), (5,4), (9,6)
Solution 2

▶ Distance to (5,4) = smallest

▶ Nearest = (5,4)
Problem 3

Range query: Find points where:

▶ x ∈ [2, 6], y ∈ [3, 7]
Solution 3

▶ Valid points: (2,3), (5,4), (4,7)

Problem 4

Which nodes can be pruned while searching?

Solution 4

▶ Nodes outside query region

▶ Subtrees with no overlap
Problem 5

Time complexity of KD-tree search?

Solution 5

▶ Average: O(log n)
▶ Worst: O(n)
Problem 6

Why KD-tree fails in high dimensions?

Solution 6

▶ Curse of dimensionality
▶ Ineffective partitioning
Practice Problem 7

Insert (6,3) into KD-tree

Solution 7

▶ Follow splitting rules

▶ Insert in correct subtree
Practice Problem 8

Delete node (5,4)

Solution 8

▶ Replace with subtree minimum

Practice Problem 9

Compare KD-tree vs brute force

Solution 9

▶ KD-tree faster for large data

▶ Brute force simple but slow
Summary

▶ KD-tree partitions space

▶ Efficient for spatial queries
▶ Widely used in real applications
Geometric Data Structures: Quad Tree, Segment
Tree, R-Tree, Voronoi, Delaunay

Dr. Dheeraj
Assistant Professor, IIITM Gwalior

8 April 2026
Batch: BEE and IMG
Quad Tree: Idea

▶ Divides 2D space recursively

▶ Each division creates 4
quadrants
Quad Tree Structure

▶ Each node has 4 children:

▶ NE, NW, SE, SW
▶ Recursive decomposition
Quad Tree Example

▶ City → Areas → Blocks → Streets

Quad Tree Problem

Given points in a map, how to efficiently find all points in a region?

Quad Tree Solution

▶ Divide map into quadrants

▶ Traverse only relevant regions
Segment Tree: Idea

▶ Stores intervals/segments
▶ Used for overlap detection I2
I1
▶ Supports efficient range
queries
Segment Tree Use

▶ Detect overlapping roads

▶ Range queries
Segment Tree Problem

Given road segments, find all intersections.

Segment Tree Solution

▶ Store segments in tree

▶ Query overlapping intervals
R-Tree: Idea

▶ Index spatial objects

▶ Uses bounding rectangles
R-Tree Structure

▶ Hierarchical MBRs
▶ Efficient spatial search
R-Tree Problem

Find nearest restaurant in a map.

R-Tree Solution

▶ Traverse bounding rectangles

▶ Prune irrelevant regions
Voronoi Diagram: Idea

▶ Divides space by nearest

point
Voronoi Example

▶ Hospital regions
▶ Delivery zones
Voronoi Problem

Assign each location to nearest hospital.

Voronoi Solution

▶ Partition space
▶ Each region = closest point
Delaunay Triangulation: Idea

▶ Triangles with empty

circumcircle
Delaunay Use

▶ Mesh generation
▶ Terrain modeling
Delaunay Problem

Create triangulation with no point inside circumcircle.

Delaunay Solution

▶ Adjust edges
▶ Ensure empty circumcircle property
Practice Questions

▶ Construct Quad Tree for given points

▶ Find overlapping intervals using Segment Tree
▶ Explain R-Tree pruning
▶ Draw Voronoi diagram for 3 points
 IT102 : Data Structures

Introduction to trees and graphs

115/04/30 IT102 1
 Trees

115/04/30 IT102 2
 What is a tree?
• Trees are structures used to represent hierarchical
relationship
• Each tree consists of nodes and edges
• Each node represents an object
• Each edge represents the relationship between two
nodes.

node
edge

115/04/30 IT102 3
 Some applications of Trees
Organization Chart Expression Tree

President
+
VP VP
Personnel Marketing * 5

3 2
Director Director
Customer Sales
Relation

115/04/30 IT102 4
 Terminology I
• For any two nodes u and v, if there is an edge
pointing from u to v, u is called the parent of v
while v is called the child of u. Such edge is
denoted as (u, v).
• In a tree, there is exactly one node without
parent, which is called the root. The nodes
without children are called leaves.
root

u
u: parent of v
v: child of u
v
115/04/30 IT102 leaves 5
 Terminology II
• In a tree, the nodes without children are
called leaves. Otherwise, they are called
internal nodes.

internal nodes

leaves
115/04/30 IT102 6
 Terminology III
• If two nodes have the same parent, they are
siblings.
• A node u is an ancestor of v if u is parent of v or
parent of parent of v or …
• A node v is a descendent of u if v is child of v or
child of child of v or …
u

v and w are siblings

u and v are ancestors of x v w
v and x are descendents of u
x
115/04/30 IT102 7
 Terminology IV
• A subtree is any node together with all its
descendants.

T
A subtree of T
v v

115/04/30 IT102 8
 Terminology V
• Level of a node n: number of nodes on the path from
root to node n
• Height of a tree: maximum level among all of its node

Level 1

Level 2
height=4
n Level 3

Level 4

115/04/30 IT102 9
 Binary Tree
• Binary Tree: Tree in which every node has at
most 2 children
• Left child of u: the child on the left of u
• Right child of u: the child on the right of u

x: left child of u
u v y: right child of u
w: right child of v
x y z: left child of w
w
z
115/04/30 IT102 10
 Full binary tree
• If T is empty, T is a full binary tree of height 0.
• If T is not empty and of height h >0, T is a full
binary tree if both subtrees of the root of T are
full binary trees of height h-1.

Full binary tree

of height 3

115/04/30 IT102 11
 Property of binary tree (I)
• A full binary tree of height h has 2h-1
nodes
No. of nodes = 20 + 21 + … + 2(h-1)
= 2h – 1
Level 1: 20 nodes

Level 2: 21 nodes

Level 3: 22 nodes
115/04/30 IT102 12
 Property of binary tree (II)
• Consider a binary tree T of height h. The
number of nodes of T  2h-1

Reason: you cannot have more nodes than

a full binary tree of height h.

115/04/30 IT102 13
 Property of binary tree (III)
• The minimum height of a binary tree with n
nodes is log(n+1)

By property (II), n  2h-1

Thus, 2h  n+1
That is, h  log2 (n+1)

115/04/30 IT102 14
 Binary Tree ADT
setElem

getElem
setLeft, setRight

binary
getLeft, getRight
tree
isEmpty, isFull,
isComplete

makeTree

115/04/30 IT102 15
Representation of a Binary Tree
• An array-based representation
• A reference-based representation

115/04/30 IT102 16
 An array-based representation
nodeNum item leftChild rightChild
–1: empty tree
root
0 d 1 2 0
1 b 3 4
2 f 5 -1
3 a -1 -1
d 4 c -1 -1
5 e -1 -1

b f 6 ? ? ? free
7 ? ? ? 6
8 ? ? ?
a c e 9 ? ? ?
... ..... ..... ....
115/04/30 IT102 17
 Reference Based
Representation
NULL: empty tree left element right

You can code this with a

class of three fields:
Object element;
BinaryNode left;
BinaryNode right; d d

b f
b f
a c
a c
115/04/30 IT102 18
 Tree Traversal
• Given a binary tree, we may like to do
some operations on all nodes in a binary
tree. For example, we may want to double
the value in every node in a binary tree.
• To do this, we need a traversal algorithm
which visits every node in the binary tree.

115/04/30 IT102 19
 Ways to traverse a tree
• There are three main ways to traverse a tree:
– Pre-order:
• (1) visit node, (2) recursively visit left subtree, (3) recursively
visit right subtree
– In-order:
• (1) recursively visit left subtree, (2) visit node, (3) recursively
right subtree
– Post-order:
• (1) recursively visit left subtree, (2) recursively visit right
subtree, (3) visit node
– Level-order:
• Traverse the nodes level by level
• In different situations, we use different traversal
algorithm.
115/04/30 IT102 20
 Examples for expression tree
• By pre-order, (prefix)
+*23/84
• By in-order, (infix) +
2*3+8/4
• By post-order, (postfix) * /
23*84/+ 2 3 8 4
• By level-order,
+*/2384
• Note 1: Infix is what we read!
• Note 2: Postfix expression can be computed
efficiently using stack
115/04/30 IT102 21
 Pre-order
Algorithm pre-order(BTree x)
If (x is not empty) {
print [Link](); // you can do other things!
pre-order([Link]());
pre-order([Link]());
}

115/04/30 IT102 22
 Pre-order example

Pre-order(a); Print a; Print b; Print d;

Pre-order(b); Pre-order(d); Pre-order(null);
Pre-order(c); Pre-order(null); Pre-order(null);

Print c;
Pre-order(null);
Pre-order(null);

a b d c b c

d
115/04/30 IT102 23
 Time complexity of Pre-order
Traversal
• For every node x, we will call
pre-order(x) one time, which performs
O(1) operations.
• Thus, the total time = O(n).

115/04/30 IT102 24
 In-order and post-order
Algorithm in-order(BTree x)
If (x is not empty) {
in-order([Link]());
print [Link](); // you can do other things!
in-order([Link]());
}

Algorithm post-order(BTree x)
If (x is not empty) {
post-order([Link]());
post-order([Link]());
print [Link](); // you can do other things!
}
115/04/30 IT102 25
 In-order example

In-order(a); In-order(b); In-order(d); In-order(null);

Print a; Print b; Print d;
In-order(c); In-order(null); In-order(null);

In-order(null);
Print c;
In-order(null);

d b a c b c

d
115/04/30 IT102 26
 Post-order example

Post-order(a); Post-order(b); Post-order(d); Post-order(null);

Post-order(c); Post-order(null); Post-order(null);
Print a; Print b; Print d;

Post-order(null);
Print c;
Post-order(null);

d b c a b c

d
115/04/30 IT102 27
Time complexity for in-order and
post-order
• Similar to pre-order traversal, the time
complexity is O(n).

115/04/30 IT102 28
 Level-order
• Level-order traversal requires a queue!

Algorithm level-order(BTree t)
Queue Q = new Queue();
BTree n;
[Link](t); // insert pointer t into Q
while (! [Link]()){
n = [Link](); //remove next node from the front of Q
if (![Link]()){
print [Link](); // you can do other things
[Link]([Link]()); // enqueue left subtree on rear of Q
[Link]([Link]()); // enqueue right subtree on rear of Q
};
};
115/04/30 IT102 29
 Time complexity of Level-order
traversal
• Each node will enqueue and dequeue one
time.
• For each node dequeued, it only does one
print operation!
• Thus, the time complexity is O(n).

115/04/30 IT102 30
 General tree implementation
struct TreeNode A
{
Object element
TreeNode *firstChild B C D E
TreeNode *nextsibling
}
F G
because we do not know how many children a
node has in advance.

• Traversing a general tree is similar to traversing

a binary tree
115/04/30 IT102 31
 Summary
• We have discussed
– the tree data-structure.
– Binary tree vs general tree
– Binary tree ADT
• Can be implemented using arrays or references
– Tree traversal
• Pre-order, in-order, post-order, and level-order

115/04/30 IT102 32
 Graphs

115/04/30 IT102 33
 What is a graph?
• Graphs represent the relationships among data
items
• A graph G consists of
– a set V of nodes (vertices)
– a set E of edges: each edge connects two nodes
• Each node represents an item
• Each edge represents the relationship between
two items
node
edge
115/04/30 IT102 34
 Examples of graphs
Molecular Structure Computer Network
H Server 1 Terminal 1

H C H
Terminal 2
H Server 2

Other examples: electrical and communication networks,

airline routes, flow chart, graphs for planning projects

115/04/30 IT102 35
 Formal Definition of graph
• The set of nodes is denoted as V
• For any nodes u and v, if u and v are
connected by an edge, such edge is denoted
as (u, v) v
(u, v)

u
• The set of edges is denoted as E
• A graph G is defined as a pair (V, E)
115/04/30 IT102 36
 Adjacent
• Two nodes u and v are said to be adjacent
if (u, v)  E

v
(u, v)
u
w
u and v are adjacent
v and w are not adjacent

115/04/30 IT102 37
 Path and simple path
• A path from v1 to vk is a sequence of
nodes v1, v2, …, vk that are connected by
edges (v1, v2), (v2, v3), …, (vk-1, vk)
• A path is called a simple path if every
node appears at most once. v2 v
v1 3

- v2, v3, v4, v2, v1 is a path

v4 v5
- v2, v3, v4, v5 is a path, also it
is a simple path
115/04/30 IT102 38
 Cycle and simple cycle
• A cycle is a path that begins and ends at
the same node
• A simple cycle is a cycle if every node
appears at most once, except for the first
and the last nodes
v2
v1 v3
- v2, v3, v4, v5 , v3, v2 is a cycle
- v2, v3, v4, v2 is a cycle, it is v4 v5
also a simple cycle
115/04/30 IT102 39
 Connected graph
• A graph G is connected if there exists path
between every pair of distinct nodes;
otherwise, it is disconnected
v2
v1 v3

v4 v5
This is a connected graph because there exists
path between every pair of nodes
115/04/30 IT102 40
 Example of disconnected graph

v1 v3 v7 v8
v2
v4 v5
v6 v9
This is a disconnected graph because there does not
exist path between some pair of nodes, says, v1 and
v7

115/04/30 IT102 41
 Connected component
• If a graph is disconnect, it can be partitioned into
a number of graphs such that each of them is
connected. Each such graph is called a
connected component.

v2 v7 v8
v1 v3

v4 v5
v6 v9
115/04/30 IT102 42
 Complete graph
• A graph is complete if each pair of distinct
nodes has an edge

Complete graph Complete graph

with 3 nodes with 4 nodes

115/04/30 IT102 43
 Subgraph
• A subgraph of a graph G =(V, E) is a graph
H = (U, F) such that U  V and
F  E.
v2 v2
v1 v3 v3

v4 v5 v4 v5

G H
115/04/30 IT102 44
 Weighted graph
• If each edge in G is assigned a weight, it
is called a weighted graph

Chicago 1000 New York

3500
2000

Houston

115/04/30 IT102 45
 Directed graph (digraph)
• All previous graphs are undirected graph
• If each edge in E has a direction, it is called a directed
edge
• A directed graph is a graph where every edges is a
directed edge
Chicago 1000 New York

Directed edge
2000
3500

Houston
115/04/30 IT102 46
 More on directed graph
x y

• If (x, y) is a directed edge, we say

– y is adjacent to x
– y is successor of x
– x is predecessor of y
• In a directed graph, directed path, directed
cycle can be defined similarly

115/04/30 IT102 47
 Multigraph
• A graph cannot have duplicate edges.
• Multigraph allows multiple edges and self
edge (or loop).

Self edge Multiple edge

115/04/30 IT102 48
 Property of graph
• A undirected graph that is connected and
has no cycle is a tree.
• A tree with n nodes have exactly n-1
edges.
• A connected undirected graph with n
nodes must have at least n-1 edges.

115/04/30 IT102 49
 Implementing Graph
• Adjacency matrix
– Represent a graph using a two-dimensional
array
• Adjacency list
– Represent a graph using n linked lists where n
is the number of vertices

115/04/30 IT102 50
Adjacency matrix for directed graph
Matrix[i][j] = 1 if (vi, vj)E 1 2 3 4 5
0 if (vi, vj)E
v1 v2 v3 v4 v5
1 v1 0 1 0 0 0
v2
v1 v3 2 v 0 0 0 1 0
2

3 v3 0 1 0 1 0
v4 v5 4 v4 0 0 0 0 0

G 5 v5 0 0 1 1 0

115/04/30 IT102 51
 Adjacency matrix for weighted
undirected graph
Matrix[i][j] = w(vi, vj) if (vi, vj)E or (vj, vi)E
∞ otherwise
1 2 3 4 5
v2 v1 v2 v3 v4 v5
v1 2 v3
5 1 v1 ∞ 5 ∞ ∞ ∞
4 3 7 2 v2 5 ∞ 2 4 ∞
v4
8 v5
3 v3 0 2 ∞ 3 7
G 4 v4 ∞ 4 3 ∞ 8
115/04/30 IT102
5 v5 ∞ ∞ 7 8 ∞
52
 Adjacency list for directed graph

1 v1  v2
v2 2 v2  v4
v1 v3
3 v3  v2  v4
4 v4
v4 v5
5 v5  v3  v4
G

115/04/30 IT102 53
 Adjacency list for weighted
undirected graph

v2
v1 2 v3 1 v1  v2(5)
5
4 3 2 v2  v1(5)  v3(2)  v4(4)
7
3 v3  v2(2)  v4(3)  v5(7)
v4
8 v5
4 v4  v2(4)  v3(3)  v5(8)
G 5 v5  v3(7)  v4(8)

115/04/30 IT102 54
 Pros and Cons
• Adjacency matrix
– Allows us to determine whether there is an
edge from node i to node j in O(1) time
• Adjacency list
– Allows us to find all nodes adjacent to a given
node j efficiently
– If the graph is sparse, adjacency list requires
less space

115/04/30 IT102 55
 Problems related to Graph
• Graph Traversal
• Topological Sort
• Spanning Tree
• Minimum Spanning Tree
• Shortest Path

115/04/30 IT102 56
 Graph Traversal Algorithm
• To traverse a tree, we use tree traversal
algorithms like pre-order, in-order, and post-
order to visit all the nodes in a tree
• Similarly, graph traversal algorithm tries to visit
all the nodes it can reach.
• If a graph is disconnected, a graph traversal that
begins at a node v will visit only a subset of
nodes, that is, the connected component
containing v.

115/04/30 IT102 57
 Two basic traversal algorithms
• Two basic graph traversal algorithms:
– Depth-first-search (DFS)
• After visit node v, DFS strategy proceeds along a
path from v as deeply into the graph as possible
before backing up
– Breadth-first-search (BFS)
• After visit node v, BFS strategy visits every node
adjacent to v before visiting any other nodes

115/04/30 IT102 58
 Depth-first search (DFS)
• DFS strategy looks similar to pre-order. From a given
node v, it first visits itself. Then, recursively visit its
unvisited neighbours one by one.
• DFS can be defined recursively as follows.

Algorithm dfs(v)
print v; // you can do other things!
mark v as visited;
for (each unvisited node u adjacent to v)
dfs(u);

115/04/30 IT102 59
 DFS example
• Start from v3
1
v3

2
v2 v2
v1 v3
x x x 3 4
v1 v4
v4
x x v5
5
G v5

115/04/30 IT102 60
 Non-recursive version of DFS
algorithm
Algorithm dfs(v)
[Link]();
[Link](v);
mark v as visited;
while (![Link]()) {
let x be the node on the top of the stack s;
if (no unvisited nodes are adjacent to x)
[Link](); // backtrack
else {
select an unvisited node u adjacent to x;
[Link](u);
mark u as visited;
}
}

115/04/30 IT102 61
 Non-recursive DFS example
visit stack
v3 v3
v2
v2 v3, v2
v1 v3
v1 v3, v2, v1
x x x
x
backtrack v3, v2
v4 v3, v2, v4 v4 x v5
v5 v3, v2, v4 , v5
backtrack v3, v2, v4
backtrack v3, v2 G
backtrack v3
backtrack empty
115/04/30 IT102 62
 Breadth-first search (BFS)
• BFS strategy looks similar to level-order. From a
given node v, it first visits itself. Then, it visits
every node adjacent to v before visiting any
other nodes.
– 1. Visit v
– 2. Visit all v’s neigbours
– 3. Visit all v’s neighbours’ neighbours
– …
• Similar to level-order, BFS is based on a queue.

115/04/30 IT102 63
 Algorithm for BFS
Algorithm bfs(v)
[Link]();
[Link](v);
mark v as visited;
while(![Link]()) {
w = [Link]();
for (each unvisited node u adjacent to w) {
[Link](u);
mark u as visited;
}
}
115/04/30 IT102 64
 BFS example
• Start from v5 Visit Queue
(front to
1 back)
v5 v5 v5

v2 v3 empty
v1
x x
2 3
v3 v4
v3 v3
x v4 v3, v4

v4x
v4
x
4
v2 v2 v4, v2
v5 v2
G 5 empty
v1 v1 v1
115/04/30 IT102
empty65
 Topological order
• Consider the prerequisite structure for courses:

b d
a

c e
• Each node x represents a course x
• (x, y) represents that course x is a prerequisite to course y
• Note that this graph should be a directed graph without cycles
(called a directed acyclic graph).
• A linear order to take all 5 courses while satisfying all prerequisites
is called a topological order.
• E.g.
– a, c, b, e, d
– c, a, b, e, d
115/04/30 IT102 66
 Topological sort
• Arranging all nodes in the graph in a topological
order

Algorithm topSort
n = |V|;
for i = 1 to n {
select a node v that has no successor;
[Link](1, v);
delete node v and its edges from the graph;
}
return aList;
115/04/30 IT102 67
 Example
b d b
a a

c e c
e
1. d has no 2. Both b and e have
successor! no successor!
Choose d! Choose e!
b b
a a
a
c
3. Both b and c have 4. Only b has no 5. Choose a!
no successor! successor! The topological
Choose c! Choose b! order is
a,b,c,e,d
115/04/30 IT102 68
 Topological sort algorithm 2
• This algorithm is based on DFS
Algorithm topSort2
[Link]();
for (all nodes v in the graph) {
if (v has no predecessors) {
[Link](v);
mark v as visited;
}
}
while (![Link]()) {
let x be the node on the top of the stack s;
if (no unvisited nodes are adjacent to x) { // i.e. x has no unvisited successor
[Link](1, x);
[Link](); // blacktrack
} else {
select an unvisited node u adjacent to x;
[Link](u);
mark u as visited;
}
}
return aList;
115/04/30 IT102 69
 Spanning Tree
• Given a connected undirected graph G, a
spanning tree of G is a subgraph of G that
contains all of G’s nodes and enough of its
edges to form a tree.
v2
v1 v3

v4 v5
Spanning
tree Spanning tree is not unique!

115/04/30 IT102 70
 DFS spanning tree
• Generate the spanning tree edge during the DFS
traversal.

Algorithm dfsSpanningTree(v)
mark v as visited;
for (each unvisited node u adjacent to v) {
mark the edge from u to v;
dfsSpanningTree(u);
}

• Similar to DFS, the spanning tree edges can be

generated based on BFS traversal.
115/04/30 IT102 71
Example of generating spanning
tree based on DFS
stack
v3 v3
v2
v1 v3
x
v2 v3, v2
v1 v3, v2, v1 x x
x
backtrack v3, v2
v4 v3, v2, v4 v4 x v5
v5 v3, v2, v4 , v5
backtrack v3, v2, v4
backtrack v3, v2 G
backtrack v3
115/04/30 backtrack empty IT102 72
 Minimum Spanning Tree
• Consider a connected undirected graph where
– Each node x represents a country x
– Each edge (x, y) has a number which measures the
cost of placing telephone line between country x and
country y
• Problem: connecting all countries while
minimizing the total cost
• Solution: find a spanning tree with minimum total
weight, that is, minimum spanning tree

115/04/30 IT102 73
 Formal definition of minimum
spanning tree
• Given a connected undirected graph G.
• Let T be a spanning tree of G.
• cost(T) = eTweight(e)
• The minimum spanning tree is a spanning tree T
which minimizes cost(T)
v2
v1 2 v3
5 Minimum
4 3 spanning
7
tree
v4
8 v5
115/04/30 IT102 74
 Prim’s algorithm (I)
v1 v2 v1 v2 v1 v2
5 2 v3 5 2 v3 5 2 v3
4 3 7 4 3 7 4 3 7
v4 8 v5 v4 8 v5 v4 8 v5
Start from v5, find the Find the minimum Find the minimum
minimum edge attach to edge attach to v3 and edge attach to v2, v3
v5 v5 and v5

v2 v1 v2
v1 2 v3
5 2 v3 5
4 3 7 4 3 7
v4 8 v5 v4 8 v5

Find the minimum edge

attach to v2, v3 , v4 and v5
115/04/30 IT102 75
 Prim’s algorithm (II)
Algorithm PrimAlgorithm(v)
• Mark node v as visited and include it in the
minimum spanning tree;
• while (there are unvisited nodes) {
– find the minimum edge (v, u) between a visited node v
and an unvisited node u;
– mark u as visited;
– add both v and (v, u) to the minimum spanning tree;
}

115/04/30 IT102 76
 Shortest path
• Consider a weighted directed graph
– Each node x represents a city x
– Each edge (x, y) has a number which represent the
cost of traveling from city x to city y
• Problem: find the minimum cost to travel from
city x to city y
• Solution: find the shortest path from x to y

115/04/30 IT102 77
 Formal definition of shortest
path
• Given a weighted directed graph G.
• Let P be a path of G from x to y.
• cost(P) = ePweight(e)
• The shortest path is a path P which minimizes
cost(P)
v2
v1 2 v3
5
4 3 Shortest Path
4
v4
8 v5
115/04/30 IT102 78
 Dijkstra’s algorithm
• Consider a graph G, each edge (u, v) has
a weight w(u, v) > 0.
• Suppose we want to find the shortest path
starting from v1 to any node vi
• Let VS be a subset of nodes in G
• Let cost[vi] be the weight of the shortest
path from v1 to vi that passes through
nodes in VS only.

115/04/30 IT102 79
 Example for Dijkstra’s algorithm
v1 v2 2 v3
5
4 3 4
v4
8 v5
v VS cost[v1] cost[v2] cost[v3] cost[v4] cost[v5]
1 [v1] 0 5 ∞ ∞ ∞

115/04/30 IT102 80
 Example for Dijkstra’s algorithm
v2
v1 2 v3
5
4 3 4
v4
8 v5
v VS cost[v1] cost[v2] cost[v3] cost[v4] cost[v5]
1 [v1] 0 5 ∞ ∞ ∞
2 v2 [v1, v2] 0 5 ∞ 9 ∞

115/04/30 IT102 81
 Example for Dijkstra’s algorithm
v2
v1 2 v3
5
4 3 4
v4
8 v5
v VS cost[v1] cost[v2] cost[v3] cost[v4] cost[v5]
1 [v1] 0 5 ∞ ∞ ∞
2 v2 [v1, v2] 0 5 ∞ 9 ∞
3 v4 [v1, v2, v4] 0 5 12 9 17

115/04/30 IT102 82
 Example for Dijkstra’s algorithm
v2
v1 2 v3
5
4 3 4
v4
8 v5
v VS cost[v1] cost[v2] cost[v3] cost[v4] cost[v5]
1 [v1] 0 5 ∞ ∞ ∞
2 v2 [v1, v2] 0 5 ∞ 9 ∞
3 v4 [v1, v2, v4] 0 5 12 9 17
4 v3 [v1, v2, v4, v3] 0 5 12 9 16
5 v5 [v1, v2, v4, v3, v5] 0 5 12 9 16
115/04/30 IT102 83
 Dijkstra’s algorithm
Algorithm shortestPath()
n = number of nodes in the graph;
for i = 1 to n
cost[vi] = w(v1, vi);
VS = { v1 };
for step = 2 to n {
find the smallest cost[vi] s.t. vi is not in VS;
include vi to VS;
for (all nodes vj not in VS) {
if (cost[vj] > cost[vi] + w(vi, vj))
cost[vj] = cost[vi] + w(vi, vj);
}
}
115/04/30 IT102 84
 Summary
• Graphs can be used to represent many real-life
problems.
• There are numerous important graph algorithms.
• We have studied some basic concepts and
algorithms.
– Graph Traversal
– Topological Sort
– Spanning Tree
– Minimum Spanning Tree
– Shortest Path
115/04/30 IT102 85
 Optimal and Average BSTs with Balanced Trees

Dr. Dheeraj
IIITM Gwalior

Dr. Dheeraj IIITM Gwalior Optimal and Average BSTs with Balanced Trees 1 / 21
Introduction

BST used in searching and indexing

Performance depends on tree structure
Types:
Average BST
Optimal BST
Balanced BST

Dr. Dheeraj IIITM Gwalior Optimal and Average BSTs with Balanced Trees 2 / 21
BST Example

10

5 15

2 7

Dr. Dheeraj IIITM Gwalior Optimal and Average BSTs with Balanced Trees 3 / 21
Problem Statement 1 (Real World)

You are designing a student database where IDs are inserted in sorted
order.
What happens to BST structure?
What is time complexity?

Dr. Dheeraj IIITM Gwalior Optimal and Average BSTs with Balanced Trees 4 / 21
Solution
1

Tree becomes skewed

Time complexity becomes O(n)
Dr. Dheeraj IIITM Gwalior Optimal and Average BSTs with Balanced Trees 5 / 21
Average BST

Random insertions
Height ≈ log n

Dr. Dheeraj IIITM Gwalior Optimal and Average BSTs with Balanced Trees 6 / 21
Problem Statement 2

Insert keys: 40, 20, 60, 10, 30, 50, 70

Construct BST
Find height

Dr. Dheeraj IIITM Gwalior Optimal and Average BSTs with Balanced Trees 7 / 21
Solution

40

20 60

10 30 50 70

Height = 3

Dr. Dheeraj IIITM Gwalior Optimal and Average BSTs with Balanced Trees 8 / 21
Optimal BST

Uses probabilities
Minimizes expected search cost

Dr. Dheeraj IIITM Gwalior Optimal and Average BSTs with Balanced Trees 9 / 21
Problem Statement 3 (OBST)

Keys: A, B, C
Probabilities: 0.2, 0.5, 0.3
Construct Optimal BST

Dr. Dheeraj IIITM Gwalior Optimal and Average BSTs with Balanced Trees 10 / 21
Solution

A C

B chosen as root
Minimum search cost

Dr. Dheeraj IIITM Gwalior Optimal and Average BSTs with Balanced Trees 11 / 21
Balanced BST

Maintains height balance

Ensures O(log n)

Dr. Dheeraj IIITM Gwalior Optimal and Average BSTs with Balanced Trees 12 / 21
Problem Statement 4 (AVL)

Insert: 10, 20, 30

Why imbalance occurs?
Fix using rotation

Dr. Dheeraj IIITM Gwalior Optimal and Average BSTs with Balanced Trees 13 / 21
Solution

10

20

30
Before Rotation:
20

10 30
After Rotation:

Dr. Dheeraj IIITM Gwalior Optimal and Average BSTs with Balanced Trees 14 / 21
Problem Statement 5 (Real World)

Search engine stores queries:

“AI” searched 50%
“ML” searched 30%
“DL” searched 20%
Which tree should be used?

Dr. Dheeraj IIITM Gwalior Optimal and Average BSTs with Balanced Trees 15 / 21
Solution

Use Optimal BST

Place most frequent element at root

Dr. Dheeraj IIITM Gwalior Optimal and Average BSTs with Balanced Trees 16 / 21
Comparison

Average BST → random

Optimal BST → probability-based
Balanced BST → height control

Dr. Dheeraj IIITM Gwalior Optimal and Average BSTs with Balanced Trees 17 / 21
Question

Why Balanced BST preferred in systems?

Dr. Dheeraj IIITM Gwalior Optimal and Average BSTs with Balanced Trees 18 / 21
Answer

Guaranteed O(log n)
Stable performance

Dr. Dheeraj IIITM Gwalior Optimal and Average BSTs with Balanced Trees 19 / 21
Summary

BST efficiency depends on structure

OBST minimizes cost
Balanced BST ensures performance

Dr. Dheeraj IIITM Gwalior Optimal and Average BSTs with Balanced Trees 20 / 21
Practice Questions

1 Construct BST for given sequence and compute height

2 Build Optimal BST using DP
3 Perform AVL rotations
4 Compare BST types with examples

Dr. Dheeraj IIITM Gwalior Optimal and Average BSTs with Balanced Trees 21 / 21