Abstract data types

Definition

An Abstract Data Type (ADT) is a logical description of how data is viewed and what operations can be
performed on it — without specifying how these operations are implemented.

Think of it as a blueprint that defines:

 What operations are possible,

 What they do,
 But not how they do it.

Key Idea

ADTs separate the interface (what to do) from the implementation (how to do it).

Aspect Description
Logical (Abstract) View Focuses on what the data structure does.
Physical (Implementation) View Focuses on how it does it (using arrays, linked lists, etc.).

Example (Simple Analogy)

 TV Remote (ADT):
o Interface: Buttons like Power, Volume+, Volume−, Channel+.
o Implementation: Could be infrared or Bluetooth — user doesn’t care.
o → You only need to know what each button does, not how it works internally.
 Bank Account (ADT):
o Data: Account balance.
o Operations: Deposit, Withdraw, Check balance.
o Implementation: Doesn’t matter whether it’s stored in a database, blockchain, etc.
 Programming Example:
 ADT Stack {
 push(item)
 pop()
 peek()
 isEmpty()
 }

The above defines what operations a Stack supports — not how they’re written in code.

2. Characteristics of ADTs
1. Encapsulation
o Hides implementation details from the user.
o User interacts through defined operations only.

Example:
When you use a List in Python (append(), remove()), you don’t see how it’s internally stored
(array or linked list).

2. Data + Operations Together

 o Both data and allowed operations are considered part of the ADT.
o Prevents misuse and maintains integrity.

Example:
A Stack only allows push() and pop() from the top; you can’t remove items from the middle.

3. Abstraction
o Focus on what operations do, not how they do it.

Example:

o In an ATM machine, you know “Withdraw” takes money out, not the exact steps inside the
machine.

4. Implementation Independence
o Different data structures can implement the same ADT.

Example:

o A Stack can be implemented using:

 An array (fixed size)
 A linked list (dynamic size)
o But both must behave the same way logically.

3. Common Abstract Data Types

Let’s look at the most frequently used ADTs, their operations, and real-world analogies.

A. List ADT

Definition:
A collection of elements arranged in a sequence (order matters).

Operations:

 insert(position, item)
 delete(position)
 get(position)
 length()

Examples:

 Real-world: To-do list (ordered tasks)

 Programming:
 myList = [10, 20, 30]
 [Link](40)
 Implementations: Array, Linked List

B. Stack ADT

Definition:
A collection where the last inserted item is the first to be removed.
(LIFO – Last In, First Out)

Operations:
  push(item) → Add to top
 pop() → Remove from top
 peek() → View top item
 isEmpty() → Check if stack is empty

Examples:

 Real-world:
o Stack of plates — take from the top first.
o Undo/Redo feature in software.
 Programming Example:
 stack = []
 [Link]('A')
 [Link]('B')
 [Link]() # removes 'B'

C. Queue ADT

Definition:
A collection where the first inserted item is the first removed.
(FIFO – First In, First Out)

Operations:

 enqueue(item) → Add to back

 dequeue() → Remove from front
 isEmpty()

Examples:

 Real-world:
o Queue at a ticket counter.
o Print jobs in a printer queue.
 Programming Example:
 from collections import deque
 q = deque()
 [Link]('A')
 [Link]('B')
 [Link]() # removes 'A'

D. Set ADT

Definition:
A collection of unique items (no duplicates, order doesn’t matter).

Operations:

 add(item)
 remove(item)
 union(setB)
 intersection(setB)
 isMember(item)

Examples:
  Real-world:
o Group of students enrolled in a course (each student appears once).
o Tags on social media posts (unique categories).
 Programming Example:
 A = {1, 2, 3}
 B = {3, 4, 5}
 [Link](B) # {1,2,3,4,5}

E. Tree ADT

Definition:
A hierarchical structure consisting of nodes, where each node has:

 A value, and
 Links to child nodes.

Operations:

 insert(node)
 delete(node)
 traverse()
 find(value)

Examples:

 Real-world:
o Company hierarchy (CEO → Managers → Employees).
o Family tree.
 Programming Example (Binary Tree):
 class Node:
 def __init__(self, val):
 [Link] = None
 [Link] = None
 [Link] = val

4. Relationship Between ADTs and Data Structures

Concept Description Example
ADT Logical model defining operations Stack defines push/pop
Data Structure Concrete implementation of ADT Stack implemented using array or linked list

Analogy:

 ADT = Interface (Blueprint)

 Data Structure = Implementation (Building)

Example Connection

 ADT: Stack → defines push/pop behavior

 Data Structure: Array-based Stack, Linked-list Stack
→ Both satisfy the same ADT behavior but differ in memory and performance.

5. Why ADTs Matter

 1. Encourages Modularity
o You can change the internal implementation without affecting the rest of the program.
2. Promotes Code Reusability
o The same ADT interface can be reused in different programs.
3. Improves Maintainability
o Easier to debug and update since the logic is separate from implementation.
4. Supports Abstraction in OOP
o ADTs align with classes and objects — defining behavior while hiding details.

6. Practical Example (Stack ADT Implementation)

ADT Definition (Logical)

ADT Stack {
push(item)
pop()
peek()
isEmpty()
}

Implementation (Concrete using List)

class Stack:
def __init__(self):
[Link] = []
def push(self, item):
[Link](item)
def pop(self):
return [Link]()
def peek(self):
return [Link][-1]
def isEmpty(self):
return len([Link]) == 0

Here, the Stack ADT is implemented using a Python list.

If later we implement it using a linked list, the interface stays the same.

Complexity analysis
What is Complexity Analysis?

Complexity Analysis helps us measure the efficiency of an algorithm — how much time and space
(memory) it needs to run.

It allows us to:

 Predict performance before running the program.

 Compare algorithms and choose the most optimal one.
 Understand how an algorithm behaves as input size (n) grows.

Why It Matters

 In real-world systems (like Google Search or Banking Apps), efficiency matters more than just
correctness.
 A slow algorithm can make a system unusable even if it gives the correct result.
Example Scenarios

1. Sorting 10 numbers vs. 10 million numbers

o Small input: almost any algorithm is fine.
o Large input: algorithm choice (QuickSort vs Bubble Sort) makes a huge difference.
2. Finding a student in a class list
o Linear Search: check one by one → Slow for big lists.
o Binary Search: divide and conquer → Much faster.

2. Types of Algorithm Efficiency

1. Time Complexity → How much time an algorithm takes as input size grows.
2. Space Complexity → How much memory an algorithm uses during execution.

Example
def print_items(n):
for i in range(n):
print(i)

 Time Complexity: O(n) → depends on number of items.

 Space Complexity: O(1) → no extra memory used.

3. Time Complexity Explained

Time complexity measures how the runtime of an algorithm grows with the size of input (n).

Common Growth Rates

Notation Name Example Algorithm Performance (approx)

O(1) Constant Time Accessing an array element 🚀 Fastest
O(log n) Logarithmic Time Binary Search ⚡ Very efficient
O(n) Linear Time Linear Search Moderate
O(n log n) Linearithmic Merge Sort, QuickSort Efficient for sorting
O(n²) Quadratic Bubble Sort, Insertion Sort Slow for large n
O(2ⁿ) Exponential Recursive Fibonacci Very slow
O(n!) Factorial Traveling Salesman Problem ❌ Impractical for large n

Visual Understanding

As input grows, time increases differently for each complexity:

O(1) ── constant
O(log n) ── grows slowly
O(n) ── grows linearly
O(n²) ── grows fast
O(2ⁿ) ── explodes exponentially

Example 1 – Constant Time (O(1))

def get_first_item(lst):
return lst[0]
✅ Takes the same time no matter the list size.

Example 2 – Linear Time (O(n))

def find_sum(lst):
total = 0
for i in lst:
total += i
return total

⏱ Time grows proportionally to the number of elements.

Example 3 – Quadratic Time (O(n²))

for i in range(n):
for j in range(n):
print(i, j)

🌀 Nested loops → each loop runs n times → total n × n = n².

Common Mistake

Students often count lines of code instead of growth pattern.

Complexity focuses on how runtime scales, not exact time in seconds.

4. Space Complexity
Space complexity measures the amount of extra memory required by an algorithm apart from the input
data.

Example 1 – Constant Space (O(1))

def add_numbers(a, b):
return a + b

 Only two variables → constant memory.

Example 2 – Linear Space (O(n))

def store_list(n):
arr = []
for i in range(n):
[Link](i)
return arr

 Creates a list of n elements → grows linearly with input size.

Why Space Complexity Matters

 Mobile or embedded systems have limited memory.

 Some algorithms trade space for time (e.g., caching results).

5. Asymptotic Analysis
Asymptotic analysis studies the behavior of an algorithm as input size → ∞ (very large).
It ignores constant factors and focuses on growth rate.

Three Main Notations

Notation Meaning Focus Example

Big O (O) Upper Bound Worst Case O(n²)
Big Omega (Ω) Lower Bound Best Case Ω(n)
Big Theta (Θ) Tight Bound Average Case Θ(n log n)

Example: Linear Search

def linear_search(arr, key):
for i in range(len(arr)):
if arr[i] == key:
return i
return -1
Case Description Complexity
Best Case Key is at first position Ω(1)
Worst Case Key not found / last position O(n)
Average Case Key somewhere in the middle Θ(n/2) ≈ Θ(n)

Example: Binary Search

def binary_search(arr, key):
low, high = 0, len(arr) - 1
while low <= high:
mid = (low + high) // 2
if arr[mid] == key:
return mid
elif arr[mid] < key:
low = mid + 1
else:
high = mid - 1
return -1
Case Description Complexity
Best Case Found at first mid Ω(1)
Worst / Average Case Keep dividing array O(log n)

6. How to Calculate Complexity

Steps

1. Identify loops and recursion.

2. Determine how many times the main operation executes.
3. Remove constants and lower-order terms.
4. Express in Big O notation.

Example
for i in range(n):
for j in range(n):
print(i, j)

 Outer loop runs n times

  Inner loop runs n times
→ Total = n × n = O(n²)

Mixed Example
for i in range(n):
print(i)
for j in range(n*n):
print(j)

Total = O(n) + O(n²) = O(n²) (highest term dominates)

Recursive Example
def factorial(n):
if n == 0:
return 1
return n * factorial(n - 1)

Each call makes 1 recursive call → total n calls → O(n)

Common Mistakes

❌ Counting statements line by line.

✅ Focus on loops and recursion growth patterns.

7. Comparing Common Algorithm Complexities

Complexity Name Example Algorithm Performance for n=10⁴
O(1) Constant Access array element 1 operation
O(log n) Logarithmic Binary Search ~13
O(n) Linear Linear Search 10,000
O(n log n) Linearithmic Merge Sort ~132,000
O(n²) Quadratic Bubble Sort 100,000,000
O(2ⁿ) Exponential Recursive Fibonacci ~∞ (unusable)

8. Real-World Relevance
Scenario Algorithm Choice Reason
Searching small data Linear Search Simpler, small input
Searching large sorted data Binary Search Faster (O(log n))
Sorting emails Merge Sort / QuickSort Efficient O(n log n)
Pathfinding in maps Dijkstra’s Algorithm Balances time and space
Data compression Huffman Coding Optimizes efficiency

Big-O notation
What Is Big-O Notation?
Simple Explanation

Big-O notation describes how the running time or memory usage of an algorithm grows as the input size
(n) increases.

It tells us the worst-case performance of an algorithm — how much time it could take at most.

Why We Use It

 To compare algorithms regardless of hardware or language.

 To predict scalability — how performance changes for large inputs.
 To ignore constants and minor terms that don’t affect growth.

Example

If doubling your input size doubles the time → O(n).

If doubling your input size quadruples the time → O(n²).

Real-Life Analogy

 Walking through a crowd = O(n) → time increases with number of people.

 Checking everyone twice = O(2n) → still O(n) (constants don’t matter).
 Asking each person about every other person = O(n²) → grows very fast!

2. Formal Definition
Let T(n) represent the running time of an algorithm for input size n.

We say:

T(n) = O(f(n))
if there exist positive constants c and n₀ such that
T(n) ≤ c × f(n) for all n ≥ n₀.

✅ Meaning:
After a certain input size n₀, the growth of T(n) will never exceed f(n) multiplied by some constant.

Example:

If T(n) = 5n + 3 → O(n)
(because for large n, the term “5n” dominates, and constants 5 and 3 don’t change the growth pattern)

3. Common Big-O Complexities (Ordered from Best to Worst)

Big-O Notation Name Description Example Algorithm
O(1) Constant Time Same time, no matter input size Accessing array element
O(log n) Logarithmic Time grows slowly Binary Search
O(n) Linear Time grows proportionally with input Linear Search
O(n log n) Linearithmic Slightly worse than linear Merge Sort, QuickSort
Big-O Notation Name Description Example Algorithm
O(n²) Quadratic Time grows fast (nested loops) Bubble Sort
O(n³) Cubic Triple nested loops Matrix Multiplication
O(2ⁿ) Exponential Extremely slow Recursive Fibonacci
O(n!) Factorial Impossible for large n Traveling Salesman Problem

Visual Intuition (Growth Comparison)

Fast → O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!)
Slow ↑

If input size doubles:

Complexity Effect of Doubling Input

O(1) No change
O(log n) Slight increase
O(n) Doubles
O(n²) Quadruples
O(2ⁿ) Grows exponentially (very bad!)

4. Practical Examples of Big-O

Example 1: O(1) – Constant Time
def get_first_item(lst):
return lst[0]

✅ Time does not depend on list size.

Example 2: O(n) – Linear Time

def print_items(lst):
for item in lst:
print(item)

⏱ Time increases proportionally with the number of elements.

Example 3: O(n²) – Quadratic Time

def print_pairs(lst):
for i in lst:
for j in lst:
print(i, j)

🌀 For every element, you loop through all elements again → n × n.

Example 4: O(log n) – Logarithmic Time

def binary_search(arr, key):
low, high = 0, len(arr) - 1
while low <= high:
mid = (low + high) // 2
if arr[mid] == key:
return mid
 elif arr[mid] < key:
low = mid + 1
else:
high = mid - 1

📉 Each iteration cuts the problem size in half — very efficient.

Example 5: O(n log n) – Linearithmic Time

Sorting algorithms like Merge Sort or QuickSort split the array (log n) and sort each part (n).

Total = O(n log n)

💡 Efficient and commonly used for large data sorting.

5. How to Find Big-O

Step-by-Step Approach

1. Identify loops
o One loop → O(n)
o Nested loops → Multiply: O(n²)
2. Ignore constants
o 2n + 10 → O(n)
3. Add separate parts
o O(n) + O(n²) → keep the dominant one → O(n²)
4. Consider recursive calls
o e.g., Binary Search halves each time → O(log n)

Example
for i in range(n): # O(n)
for j in range(n): # O(n)
print(i, j)
for k in range(n): # O(n)
print(k)

Total = O(n² + n) → O(n²) (dominant term only)

6. Common Mistakes Students Make

❌ Mistake ✅ Correct Understanding
Counting every line Only growth rate matters
Keeping constants Drop constants (O(2n) → O(n))
Ignoring nested loops Multiply complexities (O(n²))
Mixing Big-O with runtime Big-O ≠ seconds, it’s scaling behavior
Forgetting worst-case nature Big-O shows upper bound (worst case)

7. Real-World Examples
Situation Algorithm Complexity Meaning
Finding a person in a phonebook Binary Search O(log n) Quick lookup
 Situation Algorithm Complexity Meaning
Checking all students’ marks Linear Search O(n) Slower for large classes
Sorting an email inbox Merge Sort O(n log n) Efficient
Password cracking (brute force) Exponential O(2ⁿ) Extremely slow
Generating all possible routes Factorial O(n!) Practically impossible

8. Big-O Summary Table

Complexity Name Example Efficiency
O(1) Constant Access array element ⏱ Excellent
O(log n) Logarithmic Binary Search ⏱ Excellent
O(n) Linear Linear Search ⏱ Moderate
O(n log n) Linearithmic Merge Sort ⏱ Good
O(n²) Quadratic Bubble Sort 🔴 Poor
O(2ⁿ) Exponential Recursive Fibonacci ❌ Very bad
O(n!) Factorial Traveling Salesman ❌ Worst

Stacks (linked list and array implementations)

Introduction to Stack
Definition

A Stack is a linear data structure that follows the LIFO (Last In, First Out) principle.

👉 The last element inserted into the stack is the first one to be removed.

Key Operations

Operation Description

push(x) Add an element x to the top of the stack

pop() Remove the top element

peek() / top() View (but don’t remove) the top element

isEmpty() Check if the stack is empty

isFull() (array only) Check if stack reached its limit

Real-World Examples

1. Stack of plates – last plate added is the first to be removed.

2. Undo/Redo feature – last action undone first.
3. Browser history – last page visited is the first to go back from.
 4. Function call stack – tracks which function is currently running.

Visual Representation
Top → [E]
[D]
[C]
[B]
Bottom [A]

When you push E, it goes to the top; pop() removes E first.

2. Stack Operations Explained

1️⃣ Push (Insert Element)

 Adds a new item on the top of the stack.

Example:

Initial Stack: [A, B, C]

push(D)
→ [A, B, C, D] ← D is at top

2️⃣ Pop (Remove Top Element)

 Removes and returns the top element.

Example:

Initial Stack: [A, B, C, D]

pop()
→ Returns D, Stack = [A, B, C]

3️⃣ Peek / Top

 Returns the top element without removing it.

Example:

Stack: [A, B, C]
peek() → C
Stack remains [A, B, C]

4️⃣ isEmpty

 Returns True if there are no elements, otherwise False.

3. Stack Implementation Methods

There are two main ways to implement a stack:

1. Using Arrays
2. Using Linked Lists
A. Stack Implementation Using Array
Concept

 Uses a fixed-size array.

 Has a top pointer that indicates the index of the last inserted element.

Structure

Variable Description

stack[] Array that stores elements

top Index of the topmost element

maxSize Maximum capacity of the stack

Operations

Push Operation

 Check if stack is full (top == maxSize - 1)

 If not full, increment top and insert element.

Pop Operation

 Check if stack is empty (top == -1)

 If not empty, return stack[top] and decrement top.

Peek

 Return stack[top] without changing top.

Python Example (Array Implementation)

class StackArray:
def __init__(self, size):
[Link] = [None] * size
[Link] = -1
[Link] = size

def push(self, item):

if [Link] == [Link] - 1:
print("Stack Overflow")
else:
[Link] += 1
[Link][[Link]] = item

def pop(self):
if [Link] == -1:
print("Stack Underflow")
return None
item = [Link][[Link]]
[Link] -= 1
return item
 def peek(self):
if [Link] == -1:
return None
return [Link][[Link]]

def isEmpty(self):
return [Link] == -1

Example Run
s = StackArray(3)
[Link]('A')
[Link]('B')
print([Link]()) # B
[Link]() # removes B
[Link]('C')

📦 Stack contents change as:

[] → ['A'] → ['A','B'] → pop() → ['A'] → ['A','C']

Advantages

✅ Simple to implement
✅ Fast access using index

Disadvantages

❌ Fixed size (cannot grow dynamically)

❌ Overflow if max size reached

B. Stack Implementation Using Linked List

Concept

 Each element is stored in a node.

 Each node has:
o data
o pointer to next node
 The top points to the latest node inserted.

Structure of Node
class Node:
data
next

Stack Visualization
Top → [30 | next] → [20 | next] → [10 | None]

Python Example (Linked List Implementation)

class Node:
def __init__(self, data):
[Link] = data
[Link] = None
class StackLinkedList:
def __init__(self):
[Link] = None

def push(self, item):

new_node = Node(item)
new_node.next = [Link]
[Link] = new_node

def pop(self):
if [Link] is None:
print("Stack Underflow")
return None
popped = [Link]
[Link] = [Link]
return popped

def peek(self):
if [Link] is None:
return None
return [Link]

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

Example Run
s = StackLinkedList()
[Link](10)
[Link](20)
[Link](30)
print([Link]()) # 30
[Link]() # removes 30
print([Link]()) # 20

📦 Stack structure evolves:

Push 10 → Top = 10
Push 20 → Top = 20 → 10
Push 30 → Top = 30 → 20 → 10
Pop → Top = 20 → 10

Advantages

✅ Dynamic size (grows and shrinks at runtime)

✅ No overflow unless memory is full

Disadvantages

❌ Slightly more memory (extra pointer per node)

❌ Slower access due to pointer traversal

4. Comparison: Array vs Linked List Implementation

Feature Array-Based Stack Linked List-Based Stack

Memory Allocation Fixed (static) Dynamic (runtime)

 Feature Array-Based Stack Linked List-Based Stack

Overflow Condition Possible (if array full) Not unless memory full

Underflow Condition Yes (if empty) Yes (if empty)

Implementation Complexity Simple Slightly complex

Access Speed Faster (index access) Slower (pointer traversal)

Extra Memory None Pointer storage required

Flexibility Fixed size Unlimited size (until memory full)

5. Stack Applications
Stacks are used everywhere in computer science:

Application Description

Function calls Used in recursion to store return addresses

Undo/Redo Stores previous actions in editors

Expression Evaluation Used in infix → postfix conversions

Syntax Checking Parentheses balance checking

Browser History Back and forward navigation

Backtracking Algorithms Like solving mazes or puzzles

Example: Expression Evaluation

Expression: (3 + 5) * (2 - 1)

→ Use a stack to keep track of operators and operands for evaluation.

6. Complexity Analysis
Operation Array Stack Linked List Stack

Push O(1) O(1)

Pop O(1) O(1)

Peek O(1) O(1)

Space O(n) O(n)

✅ All major operations are constant time → O(1).

7. Common Student Mistakes
❌ Mistake ✅ Correction

Forgetting to check overflow/underflow Always check before push/pop

Mixing stack order (FIFO vs LIFO) Remember: LIFO (Last In, First Out)

Not updating top pointer correctly Increment/decrement carefully

Assuming array stack auto-expands It doesn’t; must define fixed size

Forgetting None check in linked list Always check if top is None before accessing

Recursion and analyzing recursive algorithms

Introduction to Recursion
Definition

Recursion is a programming technique where a function calls itself directly or indirectly to solve a
problem.

In simple words: a recursive function solves a smaller version of the same problem until it reaches a base
case.

Every Recursive Function Has Two Parts

1. Base Case → the condition that stops the recursion.

2. Recursive Case → where the function calls itself on a smaller input.

Example 1: Factorial Function

Mathematically:
n! = n × (n − 1) × (n − 2) × … × 1
or recursively,
n! = n × (n − 1)! , with 0! = 1

Python Example:

def factorial(n):
if n == 0: # Base case
return 1
else:
return n * factorial(n - 1) # Recursive case

Flow:

factorial(3)
→ 3 * factorial(2)
→ 3 * (2 * factorial(1))
→ 3 * (2 * (1 * factorial(0)))
→ 3 * 2 * 1 * 1 = 6

Example 2: Fibonacci Series

Fibonacci:
F(n) = F(n−1) + F(n−2)
with F(0)=0, F(1)=1

Code:

def fib(n):
if n <= 1:
return n
return fib(n-1) + fib(n-2)

Real-World Examples

1. Nested folders → Opening each subfolder recursively.

2. Family tree → Each person’s children form smaller sub-trees.
3. Web crawling → Visiting links inside links recursively.

2. Types of Recursion
Type Description Example
Direct Recursion Function calls itself directly factorial(n)
Indirect Recursion Function A calls B, and B calls A A() → B() → A()
Tail Recursion Recursive call is the last statement in the function factorial in tail form
Non-Tail Recursion Function performs more work after recursive call Fibonacci
Mutual Recursion Two or more functions calling each other in cycle even(), odd() pair

Example: Tail vs Non-Tail Recursion

Non-Tail Recursion

def factorial(n):
if n == 0:
return 1
return n * factorial(n - 1) # More work (multiplication) after call

Tail Recursion

def factorial_tail(n, result=1):

if n == 0:
return result
return factorial_tail(n - 1, n * result)

Tail recursion is memory efficient, because it can be optimized by the compiler (converted to iteration).

3. How Recursion Works Internally (Call Stack)

Every time a function calls itself:

 The current state (variables, position, return address) is pushed onto the call stack.
 When a base case is reached, each function call returns in reverse order (LIFO).

Example: factorial(3)

Call stack process:

Step Function Call Stack (Top → Bottom)
1 factorial(3) factorial(3)
2 factorial(2) factorial(2), factorial(3)
3 factorial(1) factorial(1), factorial(2), factorial(3)
4 factorial(0) → return 1 factorial(0), factorial(1), factorial(2), factorial(3)
5 Start returning values Stack pops out one by one

🔁 The recursion unwinds in reverse order of calls.

4. Advantages and Disadvantages

✅ Advantages

 Simpler and shorter code.

 Natural fit for problems that are inherently recursive (like trees, graphs, divide-and-conquer).
 Easier to reason about mathematically.

❌ Disadvantages

 Extra memory usage (function call stack).

 Slower than iteration due to function call overhead.
 May lead to Stack Overflow if base case missing or too deep recursion.

5. Converting Recursion to Iteration

Many recursive algorithms can be written iteratively using loops or stacks.

Example: Factorial (Iterative Version)

def factorial_iterative(n):
result = 1
for i in range(1, n+1):
result *= i
return result

6. Analyzing Recursive Algorithms

To analyze a recursive algorithm, we use a recurrence relation that expresses the time complexity in terms
of smaller subproblems.

Step-by-Step Analysis Process

1. Express recurrence relation

(define time complexity in terms of smaller problems)
2. Solve recurrence
(expand or apply known formulas)
3. Simplify to Big-O

Example 1: Factorial
def factorial(n):
if n == 0:
 return 1
return n * factorial(n-1)

Recurrence Relation:
T(n) = T(n−1) + O(1)
(Single recursive call + constant work)

Solution:
T(n) = O(n)

✅ Time Complexity: O(n)

✅ Space Complexity: O(n) (due to recursion stack)

Example 2: Fibonacci
def fib(n):
if n <= 1:
return n
return fib(n-1) + fib(n-2)

Recurrence Relation:
T(n) = T(n−1) + T(n−2) + O(1)

Solution:
T(n) ≈ O(2ⁿ)

✅ Time Complexity: Exponential O(2ⁿ)

✅ Space Complexity: O(n)

Example 3: Binary Search

def binary_search(arr, low, high, x):
if low > high:
return -1
mid = (low + high) // 2
if arr[mid] == x:
return mid
elif arr[mid] > x:
return binary_search(arr, low, mid-1, x)
else:
return binary_search(arr, mid+1, high, x)

Recurrence Relation:
T(n) = T(n/2) + O(1)

Using Master Theorem:

T(n) = O(log n)

✅ Time Complexity: O(log n)

✅ Space Complexity: O(log n)

Example 4: Merge Sort

def merge_sort(arr):
if len(arr) > 1:
mid = len(arr)//2
L = arr[:mid]
R = arr[mid:]
 merge_sort(L)
merge_sort(R)
# merge step takes O(n)

Recurrence Relation:
T(n) = 2T(n/2) + O(n)

By Master Theorem:
T(n) = O(n log n)

✅ Time Complexity: O(n log n)

✅ Space Complexity: O(n)

7. Common Recurrence Patterns

Recurrence Algorithm Example Solution (Big-O)
T(n) = T(n−1) + O(1) Factorial O(n)
T(n) = T(n−1) + O(n) Insertion Sort O(n²)
T(n) = 2T(n/2) + O(n) Merge Sort O(n log n)
T(n) = T(n/2) + O(1) Binary Search O(log n)
T(n) = 2T(n−1) + O(1) Fibonacci O(2ⁿ)

8. Common Mistakes in Recursion

❌ Mistake ✅ Correction
Missing base case Always define stopping condition
Incorrect base case logic Ensure smallest case returns correct value
Infinite recursion Reduce input toward base case
Forgetting to return recursive value Always return recursive call result
Overlapping subproblems (e.g., Fibonacci) Use memoization or dynamic programming

9. Optimization Techniques
1. Tail Recursion Optimization – keeps constant stack size.
2. Memoization – store results of subproblems (Dynamic Programming).
3. Iterative Conversion – rewrite using loops if recursion is too deep.

Divide and conquer algorithms

1. Introduction
Definition

Divide and Conquer is a problem-solving strategy where a problem is:

1. Divided into smaller subproblems of the same type,

2. Solved recursively, and
3. Combined to form the final solution.
Basic Idea

Break a big problem into smaller pieces → solve each piece → combine results.

This method uses recursion to solve subproblems.

Real-World Analogy

 Sorting a deck of cards: Split the deck into halves, sort each half, then merge them.
 Teamwork: Divide a big project among team members, solve parts individually, then integrate.
 Binary Search: Divide the list into halves repeatedly until you find the target.

2. Steps in Divide and Conquer

Step Description Example (Merge Sort)
Divide Break the problem into smaller subproblems Split the array into halves
Conquer Solve subproblems recursively Sort each half recursively
Combine Merge the solutions of subproblems Merge two sorted halves

General Algorithm Structure

def divide_and_conquer(problem):
if problem is small enough:
return base_case_solution
else:
subproblems = divide(problem)
sub_results = [divide_and_conquer(p) for p in subproblems]
return combine(sub_results)

3. Mathematical Representation
If a problem of size n is divided into a subproblems, each of size n/b, and the combine step takes O(f(n)),
then the recurrence relation is:

T(n) = aT(n/b) + f(n)

We solve this using the Master Theorem (covered later).

4. Common Divide and Conquer Algorithms

Time
Algorithm Problem Type Recurrence Relation
Complexity
Binary Search Searching T(n) = T(n/2) + O(1) O(log n)
Merge Sort Sorting T(n) = 2T(n/2) + O(n) O(n log n)
T(n) = T(k) + T(n−k−1) +
Quick Sort Sorting O(n log n) (avg)
O(n)
Strassen’s Matrix
Matrix Multiplication T(n) = 7T(n/2) + O(n²) O(n^2.81)
Multiplication
Closest Pair of Points Geometry T(n) = 2T(n/2) + O(n log n) O(n log n)
Large integer
Karatsuba Multiplication T(n) = 3T(n/2) + O(n) O(n^1.585)
multiplication
5. Example Algorithms
️ 1. Binary Search

Concept:
Search an element in a sorted array by repeatedly dividing the search space in half.

Code Example:

def binary_search(arr, low, high, x):

if low > high:
return -1
mid = (low + high) // 2
if arr[mid] == x:
return mid
elif arr[mid] > x:
return binary_search(arr, low, mid - 1, x)
else:
return binary_search(arr, mid + 1, high, x)

Time Complexity:
T(n) = T(n/2) + O(1) → O(log n)

Real Example:
Looking for a word in a dictionary by opening the middle page and narrowing the range.

️ 2. Merge Sort

Concept:
Divide array into halves → sort each half → merge them.

Code Example:

def merge_sort(arr):
if len(arr) > 1:
mid = len(arr) // 2
L = arr[:mid]
R = arr[mid:]

merge_sort(L)
merge_sort(R)

i = j = k = 0
while i < len(L) and j < len(R):
if L[i] < R[j]:
arr[k] = L[i]
i += 1
else:
arr[k] = R[j]
j += 1
k += 1

while i < len(L):

arr[k] = L[i]
i += 1
k += 1

while j < len(R):

arr[k] = R[j]
j += 1
k += 1
Recurrence Relation:
T(n) = 2T(n/2) + O(n)
Time Complexity: O(n log n)
Space Complexity: O(n)

Real Example:
Sorting a large list of names by splitting and merging sorted sublists.

️ 3. Quick Sort

Concept:
Choose a pivot, partition array into smaller/larger elements, and sort recursively.

Code Example:

def quick_sort(arr):
if len(arr) <= 1:
return arr
pivot = arr[len(arr)//2]
left = [x for x in arr if x < pivot]
middle = [x for x in arr if x == pivot]
right = [x for x in arr if x > pivot]
return quick_sort(left) + middle + quick_sort(right)

Recurrence Relation:
T(n) = T(k) + T(n−k−1) + O(n)

Time Complexity:

 Best / Average Case: O(n log n)

 Worst Case (sorted array): O(n²)

Space Complexity: O(log n)

Real Example:
Organizing students by height: pick a “pivot” height, divide into taller/shorter groups, repeat.

️ 4. Strassen’s Matrix Multiplication

Concept:
Improves matrix multiplication using fewer recursive multiplications.

Traditional: O(n³)
Strassen: O(n^2.81)

Recurrence:
T(n) = 7T(n/2) + O(n²)

Used in scientific computing and machine learning matrix operations.

6. Advantages and Disadvantages

✅ Advantages

 Efficient for large inputs (reduces time complexity).

  Simplifies complex problems using recursion.
 Enables parallel processing (independent subproblems).

❌ Disadvantages

 Overhead of recursion (stack memory).

 May not be optimal for small datasets.
 Requires combining sub-results correctly (can be tricky).

7. Master Theorem (for Analysis)

To analyze a divide-and-conquer recurrence:
T(n) = aT(n/b) + f(n)

Case Condition Time Complexity

Case 1 If f(n) = O(n^(log_b a - ε)) T(n) = Θ(n^(log_b a))
Case 2 If f(n) = Θ(n^(log_b a)) T(n) = Θ(n^(log_b a) log n)
Case 3 If f(n) = Ω(n^(log_b a + ε)) T(n) = Θ(f(n))

Example Applications

Algorithm a b f(n) Case Result

Merge Sort 2 2 n Case 2 O(n log n)
Binary Search 1 2 1 Case 1 O(log n)
Strassen’s 7 2 n² Case 1 O(n^2.81)

8. Divide and Conquer vs Dynamic Programming

Aspect Divide & Conquer Dynamic Programming (DP)
Subproblem Overlap Independent subproblems Overlapping subproblems
Storage No memoization Stores intermediate results
Examples Merge Sort, Quick Sort Fibonacci (DP), Knapsack
Approach Top-down recursion Bottom-up tabulation or memoization

9. Common Mistakes
❌ Mistake ✅ Correction
Forgetting to combine results Always implement the combine step properly
Ignoring base case Add a clear base condition to stop recursion
Incorrect recurrence relation Carefully derive recurrence from algorithm steps
Assuming divide always improves performance Some problems are better solved iteratively

Sorting algorithms (selection, insertion, merge, quick,

bubble, heap, shell, radix, bucket)
Introduction to Sorting
Definition

Sorting is the process of arranging data in a specific order — typically ascending or descending.

Purpose

 Improves search efficiency (e.g., Binary Search).

 Helps in data organization and report generation.
 Used in database indexing, scheduling, and data analysis.

Real-World Example

 Sorting students by marks.

 Sorting files by date.
 Sorting numbers in a spreadsheet.

2. Classification of Sorting Algorithms

Category Description Examples
Internal Sorting Entire data fits into main memory Bubble, Insertion, Merge
External Sorting Data too large (stored in disks) External Merge Sort
Stable Sort Keeps equal elements in same order Merge, Bubble, Insertion
Unstable Sort May change order of equal elements Quick, Selection, Heap
Comparison-based Compares elements to decide order Bubble, Quick, Merge
Non-comparison-based Uses digits/buckets for sorting Radix, Bucket

️ 3. Major Sorting Algorithms

We’ll go through each sorting algorithm one by one.

A. Bubble Sort
Idea

Repeatedly compare adjacent elements, swapping if they are in the wrong order.

Example (Ascending order):

[5, 3, 4, 1]
→ [3, 5, 4, 1]
→ [3, 4, 5, 1]
→ [3, 4, 1, 5]
→ ...

Python Example
def bubble_sort(arr):
n = len(arr)
for i in range(n-1):
for j in range(n-1-i):
 if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]

Time Complexity

Case Complexity
Best O(n) (if already sorted)
Average O(n²)
Worst O(n²)
Space O(1)
Stability ✅ Stable

⏱ Analogy: Like bubbles rising to the top — largest elements “bubble up” each pass.

B. Selection Sort
Idea

Select the smallest element and swap it with the first unsorted element.

Example:

[5, 3, 4, 1]
→ Select 1 → swap with 5 → [1, 3, 4, 5]

Python Example
def selection_sort(arr):
n = len(arr)
for i in range(n):
min_idx = i
for j in range(i+1, n):
if arr[j] < arr[min_idx]:
min_idx = j
arr[i], arr[min_idx] = arr[min_idx], arr[i]

Complexity

Case Complexity
Best O(n²)
Average O(n²)
Worst O(n²)
Space O(1)
Stability ❌ Unstable

⏱ Analogy: Like picking the smallest card in each round from a deck.

C. Insertion Sort
Idea

Builds a sorted portion one element at a time by inserting new elements in the correct position.
Example:

[5, 2, 4, 6]
→ [2, 5, 4, 6]
→ [2, 4, 5, 6]

Python Example
def insertion_sort(arr):
for i in range(1, len(arr)):
key = arr[i]
j = i - 1
while j >= 0 and arr[j] > key:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key

Complexity

Case Complexity
Best O(n)
Average O(n²)
Worst O(n²)
Space O(1)
Stability ✅ Stable

⏱ Analogy: Like sorting playing cards in your hand.

D. Merge Sort (Divide & Conquer)

Divide the array into halves, recursively sort, then merge.

Python Example
def merge_sort(arr):
if len(arr) > 1:
mid = len(arr) // 2
L = arr[:mid]
R = arr[mid:]
merge_sort(L)
merge_sort(R)
i = j = k = 0
while i < len(L) and j < len(R):
if L[i] < R[j]:
arr[k] = L[i]
i += 1
else:
arr[k] = R[j]
j += 1
k += 1
while i < len(L):
arr[k] = L[i]
i += 1
k += 1
while j < len(R):
arr[k] = R[j]
j += 1
k += 1
Complexity

Case Complexity
Best O(n log n)
Average O(n log n)
Worst O(n log n)
Space O(n)
Stability ✅ Stable

⏱ Analogy: Sorting by dividing a big list into halves and merging sorted parts.

E. Quick Sort (Divide & Conquer)

Pick a pivot, partition array into smaller and larger elements, and sort recursively.

Python Example
def quick_sort(arr):
if len(arr) <= 1:
return arr
pivot = arr[len(arr)//2]
left = [x for x in arr if x < pivot]
middle = [x for x in arr if x == pivot]
right = [x for x in arr if x > pivot]
return quick_sort(left) + middle + quick_sort(right)

Complexity

Case Complexity
Best O(n log n)
Average O(n log n)
Worst O(n²) (if pivot bad)
Space O(log n)
Stability ❌ Unstable

⏱ Analogy: Organizing numbers around a central “pivot” value.

F. Heap Sort
Idea

Convert array into a heap, then repeatedly extract the maximum element.

Python Example
def heapify(arr, n, i):
largest = i
l, r = 2*i + 1, 2*i + 2
if l < n and arr[l] > arr[largest]:
largest = l
if r < n and arr[r] > arr[largest]:
largest = r
if largest != i:
 arr[i], arr[largest] = arr[largest], arr[i]
heapify(arr, n, largest)

def heap_sort(arr):
n = len(arr)
for i in range(n//2 - 1, -1, -1):
heapify(arr, n, i)
for i in range(n-1, 0, -1):
arr[i], arr[0] = arr[0], arr[i]
heapify(arr, i, 0)

Complexity

Case Complexity
Best O(n log n)
Average O(n log n)
Worst O(n log n)
Space O(1)
Stability ❌ Unstable

⏱ Analogy: Like repeatedly removing the tallest person from a lineup.

G. Shell Sort
Idea

Improves insertion sort by comparing elements far apart, gradually reducing the gap.

Python Example
def shell_sort(arr):
n = len(arr)
gap = n // 2
while gap > 0:
for i in range(gap, n):
temp = arr[i]
j = i
while j >= gap and arr[j - gap] > temp:
arr[j] = arr[j - gap]
j -= gap
arr[j] = temp
gap //= 2

Complexity

Case Complexity
Best O(n log n)
Average O(n^(3/2))
Worst O(n²)
Space O(1)
Stability ❌ Unstable

⏱ Analogy: Like sorting by comparing distant elements, then refining.

H. Radix Sort (Non-Comparison)

Sort numbers by individual digits, from least to most significant (LSD).

Example: Sorting [170, 45, 75, 90, 802, 24, 2, 66]

 Sort by ones place

 Sort by tens
 Sort by hundreds

Python Example
def counting_sort(arr, exp):
n = len(arr)
output = [0] * n
count = [0] * 10
for i in range(n):
index = arr[i] // exp
count[index % 10] += 1
for i in range(1, 10):
count[i] += count[i - 1]
i = n - 1
while i >= 0:
index = arr[i] // exp
output[count[index % 10] - 1] = arr[i]
count[index % 10] -= 1
i -= 1
for i in range(n):
arr[i] = output[i]

def radix_sort(arr):
max_val = max(arr)
exp = 1
while max_val // exp > 0:
counting_sort(arr, exp)
exp *= 10

Complexity

Case Complexity
Best O(nk)
Average O(nk)
Worst O(nk)
Space O(n + k)
Stability ✅ Stable

⏱ Analogy: Sorting numbers by digits like a postal worker sorting by zip codes.

I. Bucket Sort
Distribute elements into buckets, sort each bucket, then combine.

Example:

Input: [0.78, 0.17, 0.39, 0.26, 0.72]

→ Buckets: [0.17, 0.26], [0.39], [0.72, 0.78]
→ Merge sorted buckets

Python Example
def bucket_sort(arr):
buckets = [[] for _ in range(len(arr))]
for num in arr:
index = int(num * len(arr))
buckets[index].append(num)
for bucket in buckets:
[Link]()
return [num for bucket in buckets for num in bucket]

Complexity

Case Complexity
Best O(n + k)
Average O(n + k)
Worst O(n²)
Space O(n + k)
Stability ✅ Stable (depends on bucket sort used)

⏱ Analogy: Sorting coins into labeled buckets before counting.

4. Summary Table — Comparison of Sorting Algorithms

Algorithm Best Average Worst Space Stable Type
Bubble O(n) O(n²) O(n²) O(1) ✅ Comparison
Selection O(n²) O(n²) O(n²) O(1) ❌ Comparison
Insertion O(n) O(n²) O(n²) O(1) ✅ Comparison
Merge O(n log n) O(n log n) O(n log n) O(n) ✅ Comparison
Quick O(n log n) O(n log n) O(n²) O(log n) ❌ Comparison
Heap O(n log n) O(n log n) O(n log n) O(1) ❌ Comparison
Shell O(n log n) O(n^(3/2)) O(n²) O(1) ❌ Comparison
Radix O(nk) O(nk) O(nk) O(n + k) ✅ Non-Comparison
Bucket O(n + k) O(n + k) O(n²) O(n + k) ✅ Non-Comparison

5. Choosing the Right Sorting Algorithm

Situation Recommended Algorithm
Small dataset, nearly sorted Insertion Sort
Large dataset, stable sort needed Merge Sort
Fast average case, random data Quick Sort
Memory-limited environment Heap Sort
Numeric data with limited range Radix or Bucket Sort
Educational / conceptual learning Bubble or Selection Sort

Expression parsing using stacks

What is Expression Parsing?
Expression parsing means reading and evaluating mathematical expressions that involve operators (+,
-, *, /, ^) and operands (numbers or variables).

Computers cannot directly evaluate infix expressions like humans do — they need a structured way to
process them.

That’s where stacks come in!

Example:

Human-readable expression:

A + B * C

Computers can’t directly handle operator precedence here, so we use stacks to reorder or evaluate
expressions correctly.

2. Why Use Stacks?

A stack follows LIFO (Last-In-First-Out) order — perfect for handling nested and hierarchical
operations, like:

 Parentheses ()
 Operator precedence (* before +)
 Reversing order of operations

Stacks help:

1. Convert expressions (Infix → Postfix / Prefix)

2. Evaluate Postfix or Prefix expressions

3. Expression Notations

Type Form Example (A=2, B=3, C=4)

Infix Operator between operands A + B * C → 2 + 3 * 4
Prefix (Polish) Operator before operands + A * B C → + 2 * 3 4
Postfix (Reverse Polish) Operator after operands A B C * + →2 3 4 * +

Why Convert Infix to Postfix/Prefix?

Because infix notation requires precedence and parentheses handling — stacks simplify this by making
order explicit.

Postfix and Prefix are unambiguous — no need for parentheses.

4. Converting Infix → Postfix Using Stack

Algorithm (Step-by-Step)

1. Initialize an empty stack for operators.

2. Read the expression left to right.
3. If the token is:
 o Operand (A–Z or number) → Add to output (postfix result)
o Left parenthesis '(' → Push to stack
o Right parenthesis ')' → Pop from stack to output until '(' is found
o *Operator (+, -, , /, ^) →
 Pop from stack to output while the top of the stack has higher or equal precedence
 Push the current operator
4. After reading the entire expression → Pop all remaining operators to output.

Operator Precedence Table

Operator Precedence Associativity

^ Highest Right to Left
*, / Medium Left to Right
+, - Lowest Left to Right

Example 1:

Convert:

A + B * C
Step Symbol Stack Output
1 A A
2 + + A
3 B + AB
4 * +* AB
5 C +* ABC
6 End → Pop all ABC*+

✅ Postfix: A B C * +

Example 2:

Convert:

(A + B) * (C - D)
Step Symbol Stack Output
1 ( (
2 A ( A
3 + (+ A
4 B (+ AB
5 ) — AB+
6 * * AB+
7 ( *( AB+
8 C *( AB+C
9 - *(- AB+C
10 D *(- AB+CD
11 ) * AB+CD-
Step Symbol Stack Output
12 End AB+CD-*

✅ Postfix: A B + C D - *

Python Example:
def infix_to_postfix(expression):
precedence = {'+':1, '-':1, '*':2, '/':2, '^':3}
stack = []
output = ''

for char in expression:

if [Link]():
output += char
elif char == '(':
[Link](char)
elif char == ')':
while stack and stack[-1] != '(':
output += [Link]()
[Link]()
else:
while stack and stack[-1] != '(' and precedence[char] <=
[Link](stack[-1], 0):
output += [Link]()
[Link](char)
while stack:
output += [Link]()
return output

print(infix_to_postfix("(A+B)*(C-D)")) # Output: AB+CD-*

5. Evaluating Postfix Expressions Using Stack

Algorithm

1. Initialize an empty stack.

2. Scan postfix expression left to right.
3. For each symbol:
o Operand → Push onto stack.
o Operator → Pop top two operands, apply the operator, and push result back.
4. Final value in stack = result.

Example:

Evaluate:

Postfix: 2 3 4 * +
Step Symbol Stack Action
1 2 2 Push
2 3 23 Push
3 4 234 Push
4 * 2 12 Pop 3 & 4 → 3*4=12 → Push
5 + 14 Pop 2 & 12 → 2+12=14 → Push

✅ Result = 14
Python Example
def evaluate_postfix(expr):
stack = []
for ch in [Link]():
if [Link]():
[Link](int(ch))
else:
b = [Link]()
a = [Link]()
if ch == '+': [Link](a + b)
elif ch == '-': [Link](a - b)
elif ch == '*': [Link](a * b)
elif ch == '/': [Link](a / b)
return stack[0]

print(evaluate_postfix("2 3 4 * +")) # Output: 14

6. Prefix Conversion & Evaluation

The process is similar to postfix but works right-to-left.

Step Operation
1 Scan expression right to left
2 Push operands
3 When operator found, pop two operands, evaluate, push result back
4 Final result is in the stack

Example:

Prefix: + 2 * 3 4

Evaluation:

1. * 3 4 = 12
2. + 2 12 = 14

✅ Result = 14

7. Common Mistakes in Expression Parsing

❌ Ignoring operator precedence (e.g., + vs *)
❌ Forgetting parentheses handling
❌ Reversing operands during pop in evaluation
❌ Not handling associativity properly (^ is right-associative!)

8. Real-World Applications
✅ Compilers & Interpreters — Convert infix expressions into postfix for machine execution
✅ Calculators — Evaluate expressions in postfix form internally
✅ Expression Evaluators in Programming Languages — e.g., math libraries, spreadsheets
Queues and variants (dequeue, priority queues)
What is a Queue?
Definition

A Queue is a linear data structure that follows the FIFO (First-In, First-Out) principle —
➡⏱ the first element added is the first one removed.

Real-World Analogies

 A ticket counter line — first person in line gets served first.

 Printer queue — first document sent gets printed first.
 Task scheduling — oldest request gets processed before newer ones.

Basic Queue Operations

Operation Description
Enqueue(x) Add element x at the rear (end) of the queue
Dequeue() Remove element from the front of the queue
Front / Peek() View the front element without removing it
IsEmpty() Check if the queue has no elements
IsFull() (For fixed-size queues) check if it’s full

Queue Representation
Front → [10][20][30][40] ← Rear
Dequeue → 10
Enqueue(50) → [20][30][40][50]

2. Queue Implementation
A. Array-Based Implementation
class Queue:
def __init__(self, size):
[Link] = [None] * size
[Link] = size
[Link] = [Link] = -1

def enqueue(self, item):

if [Link] == [Link] - 1:
print("Queue is Full")
else:
if [Link] == -1:
[Link] = 0
[Link] += 1
[Link][[Link]] = item

def dequeue(self):
if [Link] == -1 or [Link] > [Link]:
print("Queue is Empty")
else:
print("Dequeued:", [Link][[Link]])
[Link] += 1
B. Linked List Implementation
class Node:
def __init__(self, data):
[Link] = data
[Link] = None

class Queue:
def __init__(self):
[Link] = [Link] = None

def enqueue(self, item):

new_node = Node(item)
if [Link] is None:
[Link] = [Link] = new_node
return
[Link] = new_node
[Link] = new_node

def dequeue(self):
if [Link] is None:
print("Queue is Empty")
return
temp = [Link]
[Link] = [Link]
if [Link] is None:
[Link] = None
print("Dequeued:", [Link])

3. Types of Queues
Type Description Example Use
Simple Queue Standard FIFO queue Ticket line
Connects rear to front (circular
Circular Queue Memory-efficient buffer
array)
Double-Ended Queue
Insert/delete from both ends Undo/Redo, Browser history
(Deque)
CPU Scheduling, Dijkstra’s
Priority Queue Elements have priorities
Algorithm

4. Circular Queue
Problem with Simple Queue

When front moves forward, empty spaces form at the start → wasted space.

Circular Queue fixes this by wrapping around:

Rear connects back to Front → making a circle.

Formulae

 Enqueue: rear = (rear + 1) % size

 Dequeue: front = (front + 1) % size

Example
[10, 20, 30, 40], size = 4
Dequeue 10 → Front moves
Enqueue 50 → Rear wraps → [50, 20, 30, 40]

🔄 5. Double-Ended Queue (Deque)

Definition

A Deque (Double-Ended Queue) allows insertion and deletion from both ends.

Types of Deque

Type Description
Input-Restricted Deque Insertion only at rear, deletion both ends
Output-Restricted Deque Deletion only at front, insertion both ends

Operations

Operation Description
insertFront(x) Add element at front
insertRear(x) Add element at rear
deleteFront() Remove element from front
deleteRear() Remove element from rear

Example Flow
InsertRear(10) → [10]
InsertRear(20) → [10, 20]
InsertFront(5) → [5, 10, 20]
DeleteRear() → [5, 10]

Python Example
from collections import deque

dq = deque()
[Link](10) # InsertRear
[Link](5) # InsertFront
[Link]() # DeleteRear
[Link]() # DeleteFront

Real-World Uses

 Undo/Redo systems (add/remove from both ends)

 Browser history navigation
 Palindrome checking
 Sliding window problems (used in algorithms)

🚨 6. Priority Queue
Definition
A Priority Queue is a special type of queue where each element has a priority,
and elements with higher priority are served first, regardless of insertion order.

Example
Jobs with priorities:
Job A (priority 3)
Job B (priority 1)
Job C (priority 2)

Served in order: A → C → B

Types of Priority Queues

Type Description
Ascending Priority Queue Lower values have higher priority
Descending Priority Queue Higher values have higher priority

Python Implementation (Using Heapq)

Python’s heapq implements a min-heap, where smallest value = highest priority.

import heapq

pq = []
[Link](pq, (2, 'Write Code'))
[Link](pq, (1, 'Fix Bug'))
[Link](pq, (3, 'Review'))

while pq:
print([Link](pq))

Output:

(1, 'Fix Bug')

(2, 'Write Code')
(3, 'Review')

Applications of Priority Queues

 CPU Scheduling (OS)

 Shortest Path Algorithms (Dijkstra’s, A)*
 Event-driven simulations
 Data compression (Huffman coding)

️ 7. Comparison Table
Queue Type Insert From Delete From Order Special Feature
Simple Queue Rear Front FIFO Basic form
Circular Queue Rear Front FIFO Efficient memory usage
Deque Both ends Both ends Flexible Used in complex apps
Priority Queue Anywhere (based on priority) Based on priority Priority-based Used in scheduling

8. Time Complexities
Operation Simple Queue Deque Priority Queue (Heap)
Enqueue O(1) O(1) O(log n)
Dequeue O(1) O(1) O(log n)
Peek O(1) O(1) O(1)
Search O(n) O(n) O(n)

9. Common Mistakes
❌ Forgetting to handle queue overflow/underflow
❌ Confusing front and rear pointers
❌ Mixing up priority-based and FIFO-based removal
❌ Not resetting indices in circular queues

10. Real-World Applications Summary

Queue Type Real-World Use Case
Simple Queue Printer buffer, call center queue
Circular Queue CPU task management, traffic control
Deque Undo/Redo, palindrome checking, sliding window problems
Priority Queue CPU scheduling, Dijkstra’s algorithm, data compression

Linked lists (including sorted linked lists)

What is a Linked List?
Definition

A Linked List is a linear data structure where elements (called nodes) are connected using pointers.
Unlike arrays, linked lists don’t store elements in contiguous memory.

Each node contains:

1. Data – the actual value

2. Pointer (next) – address/reference to the next node

Visual Representation
[Data|Next] → [Data|Next] → [Data|Next] → NULL

Example:

[10|*] → [20|*] → [30|NULL]

Key Idea

 The last node always points to NULL (indicating the end of the list).
 The first node is called the Head.
2. Why Linked Lists?
Feature Array Linked List
Memory Allocation Fixed (contiguous) Dynamic (non-contiguous)
Insertion/Deletion Expensive (shifting needed) Efficient (just change pointers)
Random Access O(1) O(n)
Memory Use May waste space Efficient use (grow/shrink easily)

✅ Best used when:

 The size of the list is unknown or changes frequently

 Frequent insertion/deletion operations are required

3. Types of Linked Lists

1. Singly Linked List
2. Doubly Linked List
3. Circular Linked List
4. Circular Doubly Linked List
5. Sorted Linked List

4. Singly Linked List

Each node points only to the next node.

Structure
Head → [10|*] → [20|*] → [30|NULL]

Node Definition (Python Example)

class Node:
def __init__(self, data):
[Link] = data
[Link] = None

Linked List Operations

class LinkedList:
def __init__(self):
[Link] = None

def insert_front(self, data):

new_node = Node(data)
new_node.next = [Link]
[Link] = new_node

def insert_end(self, data):

new_node = Node(data)
if [Link] is None:
[Link] = new_node
return
temp = [Link]
while [Link]:
temp = [Link]
[Link] = new_node
 def delete(self, key):
temp = [Link]
if temp and [Link] == key:
[Link] = [Link]
return
prev = None
while temp and [Link] != key:
prev = temp
temp = [Link]
if temp is None:
return
[Link] = [Link]

def display(self):
temp = [Link]
while temp:
print([Link], end=" → ")
temp = [Link]
print("NULL")

Example Run
ll = LinkedList()
ll.insert_end(10)
ll.insert_end(20)
ll.insert_front(5)
[Link]()

Output:

5 → 10 → 20 → NULL

5. Doubly Linked List (DLL)

Each node has two pointers:

 prev → points to the previous node

 next → points to the next node

Structure
NULL ← [10|*|*] ↔ [20|*|*] ↔ [30|*|NULL]

Advantages

✅ Bidirectional traversal
✅ Easier deletion/insertion before or after any node

Disadvantages

❌ Uses extra memory for prev pointer

❌ More complex pointer handling

6. Circular Linked List

In a circular linked list, the last node points back to the head instead of NULL.
Structure
[10] → [20] → [30] ↘
↑___________|

Uses

 Round-robin scheduling
 Continuous data buffering
 Music/video playlists

7. Sorted Linked List

Definition

A sorted linked list is a linked list where elements are kept in sorted order automatically after every
insertion.

➡⏱ The list remains ascending or descending at all times.

Example (Ascending Order)

Insert in order:

Insert 20 → [20]
Insert 10 → [10 → 20]
Insert 30 → [10 → 20 → 30]
Insert 25 → [10 → 20 → 25 → 30]

Implementation Example
class SortedLinkedList:
def __init__(self):
[Link] = None

def insert(self, data):

new_node = Node(data)
# If list is empty or first element is greater
if [Link] is None or data < [Link]:
new_node.next = [Link]
[Link] = new_node
return

current = [Link]
while [Link] and [Link] < data:
current = [Link]

new_node.next = [Link]
[Link] = new_node

def display(self):
temp = [Link]
while temp:
print([Link], end=" → ")
temp = [Link]
print("NULL")

Output Example:
Insert(20), Insert(10), Insert(30), Insert(25)
→ 10 → 20 → 25 → 30 → NULL

Advantages

 Always sorted → no need to sort after insertion

 Efficient for merging sorted lists

Disadvantages

 Insertion takes O(n) (must find correct position)

 Not ideal for frequent random access

8. Time Complexity Table

Operation Singly Linked List Doubly Linked List Sorted Linked List
Traversal O(n) O(n) O(n)
Insertion (front) O(1) O(1) O(n)
Insertion (end) O(n) O(1)* (if tail pointer used) O(n)
Deletion O(n) O(n) O(n)
Search O(n) O(n) O(n)

9. Common Mistakes
❌ Forgetting to set next = None for the last node
❌ Losing the rest of the list while inserting/deleting (not updating pointers correctly)
❌ Confusing prev and next in doubly linked lists
❌ Assuming random access like arrays — no indexing!

10. Real-World Applications

Type Applications
Singly Linked List Dynamic memory allocation, stacks, queues
Doubly Linked List Undo/Redo functionality, browser history
Circular Linked List CPU scheduling (round robin), playlists
Sorted Linked List Priority queues, event-driven systems

Searching (unsorted and binary search)

What is Searching?
Definition

Searching is the process of finding the location of a specific element (key) in a collection of data (like an
array or list).

In programming, searching determines whether an element exists and, if yes, where it is located.
Example

Suppose we have a list of student roll numbers:

[10, 25, 33, 47, 59]

If we search for 33 → found at index 2.

If we search for 100 → not found.

Types of Searching Techniques

Category Algorithm Examples

Sequential Searching Linear Search
Divide and Conquer Searching Binary Search
Advanced Searching (beyond BS level) Hashing, Interpolation Search, etc.

2. Linear Search (Unsorted Search)

Concept

 Simplest searching algorithm

 Works on both sorted and unsorted lists
 Checks each element one by one until the target is found or the list ends

Logic Flow
For each element in the list:
If element == target → FOUND
If end reached → NOT FOUND

Python Example
def linear_search(arr, key):
for i in range(len(arr)):
if arr[i] == key:
return i # Return index
return -1 # Not found

data = [14, 3, 7, 19, 23]

key = 19
result = linear_search(data, key)
print("Found at index:", result if result != -1 else "Not found")

Output:

Found at index: 3

Visualization

Index 0 12 3 4
Array 14 3 7 19 23
Key = 19 → Check sequentially until found at index 3

Time Complexity
 Case Explanation Time
Best Case Target at first position O(1)
Worst Case Target at last position or not present O(n)
Average Case Found halfway through O(n/2) ≈ O(n)

Space Complexity: O(1)

Real-World Example

 Searching for a name in a contact list that’s not alphabetically sorted.

 Checking for a specific order ID in a random order of transaction logs.

✅ Advantages

 Simple and easy to implement

 Works for both sorted and unsorted data
 No extra space needed

❌ Disadvantages

 Slow for large datasets (checks every element)

 Inefficient compared to binary search on sorted data

⚡ 3. Binary Search (For Sorted Data)

Concept

Binary Search is a fast search algorithm that works only on sorted data (ascending or descending order).

It repeatedly divides the search space in half, eliminating one half each time.

Core Idea

1. Compare the target element with the middle element.

2. If target = middle → found.
3. If target < middle → search left half.
4. If target > middle → search right half.

Example

Array (sorted):

[5, 10, 15, 20, 25, 30, 35]

Key = 25
Step Range (low–high) Middle Compare Action
1 0–6 mid=3 (20) 25 > 20 Search right half
2 4–6 mid=5 (30) 25 < 30 Search left half
3 4–4 mid=4 (25) 25 == 25 ✅ Found

Python Example
def binary_search(arr, key):
low, high = 0, len(arr) - 1

while low <= high:

mid = (low + high) // 2
if arr[mid] == key:
return mid
elif arr[mid] < key:
low = mid + 1
else:
high = mid - 1
return -1

data = [5, 10, 15, 20, 25, 30, 35]

key = 25
result = binary_search(data, key)
print("Found at index:", result if result != -1 else "Not found")

Output:

Found at index: 4

Visualization
[5, 10, 15, 20, 25, 30, 35]
↑
mid=3 (20)
25 > 20 → search right → [25, 30, 35]
next mid=30 → 25 < 30 → left → [25] ✅ found

Time Complexity

Case Explanation Time

Best Case Found at mid in first step O(1)
Worst Case Keep halving until 1 element left O(log₂ n)
Average Case Typically half the steps O(log₂ n)

Space Complexity

 Iterative version: O(1)

 Recursive version: O(log n) (due to recursion stack)

Real-World Examples

 Dictionary lookup: finding a word in a sorted dictionary.

 Database indexing: searching records via sorted keys.
 Binary Search Trees (BSTs): use same principle for fast searching.

⚙️ 4. Binary Search (Recursive Version)

def binary_search_recursive(arr, low, high, key):
if low > high:
return -1
mid = (low + high) // 2
if arr[mid] == key:
return mid
elif arr[mid] < key:
return binary_search_recursive(arr, mid + 1, high, key)
 else:
return binary_search_recursive(arr, low, mid - 1, key)

️ 5. Comparison: Linear vs Binary Search

Feature Linear Search Binary Search
Data Requirement Works on unsorted or sorted Works only on sorted data
Approach Sequential check Divide and conquer
Time Complexity O(n) O(log₂ n)
Space Complexity O(1) O(1) iterative, O(log n) recursive
Best Case O(1) O(1)
Worst Case O(n) O(log₂ n)
Ease of Implementation Simple Slightly complex
Performance on Large Data Slow Very fast

Example Performance (n = 1,000,000)

Algorithm Max Comparisons Needed

Linear Search 1,000,000
Binary Search ~20 (log₂ 1,000,000 ≈ 20)

⚠️ 6. Common Mistakes
❌ Using binary search on unsorted arrays → incorrect results
❌ Forgetting to update low and high correctly → infinite loops
❌ Integer overflow when calculating mid = (low + high) / 2 in large data (fix: mid = low + (high -
low)//2)
❌ Assuming binary search works for all types of data (it doesn’t — only sorted comparable data)

💡 7. Real-World Use Cases

Scenario Algorithm Used
Searching contact in unordered phone list Linear Search
Searching name in sorted dictionary Binary Search
Looking up student record by roll number in sorted database Binary Search
Searching through unsorted log files Linear Search

Hashing and indexing (open addressing and chaining)

What is Hashing?
Definition

Hashing is a technique used to store and retrieve data quickly in a structure called a hash table.
It uses a hash function to convert a data value (key) into an index (address) in the hash table.

Simple Idea

➡⏱ Key → Hash Function → Index → Value stored/retrieved

Index = hash(key)

Example

Let’s store roll numbers in a hash table of size 10:

Hash function: h(key) = key % 10

Keys: 23, 42, 34, 52

Indexes: 3, 2, 4, 2

→ Collision occurs at index 2 (42 and 52).

Real-World Analogy

Imagine a library:

 Each book (key) has a unique code (hash).

 The hash code decides where the book is placed on the shelf (index).
 You can instantly find the book by computing its code — without searching every book.

2. Hash Function
Definition

A hash function maps a large set of possible keys into a smaller set of table indices.

Properties of a Good Hash Function

1. Should distribute keys uniformly across the table.

2. Should be fast to compute.
3. Should minimize collisions.

Common Hash Functions

Type Formula Example

Division Method h(key) = key % table_size 42 % 10 = 2

Mid-Square Method h(key) = middle digits of (key²) 123² = 15129 → 12

123456 → 12 + 34 + 56 = 102 →
Folding Method Divide key into parts and add them 2

Multiplication h(key) = floor(m*(k*A % 1)), 0<A<

Used for uniform spread
Method 1
3. Collision
Definition

A collision occurs when two keys hash to the same index.

Example:

Keys: 42, 52
h(key) = key % 10 → both map to index 2

Since only one element can occupy an index, we must handle the collision.

4. Collision Resolution Techniques

There are two main ways to handle collisions:

1. Open Addressing (store colliding items elsewhere in the table)

2. Chaining (create a linked list at each index)

5. Open Addressing
Definition

All elements are stored in the hash table itself.

When a collision occurs, the algorithm searches for the next available slot according to a rule.

Types of Open Addressing

A. Linear Probing

If a position is occupied, move sequentially to the next empty slot.

Formula:

h_i(key) = (h(key) + i) % table_size

where i = 0, 1, 2, 3, ...

Example:

Table size = 10
Keys = 23, 33, 43
h(key) = key % 10

23 → 3
33 → 3 (collision) → try 4
43 → 3 (collision) → try 4 (taken) → try 5
Result: [3]=23, [4]=33, [5]=43

Issue: Clustering — many consecutive filled slots slow future searches.

B. Quadratic Probing

If a collision occurs, jump by squares instead of 1 step.

Formula:

h_i(key) = (h(key) + i²) % table_size

Example:

h(23)=3
h(33)=3 → collision → 3+1²=4
h(43)=3 → collision → 3+2²=7

✅ Reduces clustering
❌ Still may not find a free slot if table is nearly full.

C. Double Hashing

Uses two hash functions to calculate new positions.

Formula:

h_i(key) = (h1(key) + i * h2(key)) % table_size

Example:

h1(key) = key % 10
h2(key) = 7 - (key % 7)

If h1(key) collides, h2 determines the step size.

✅ Best at reducing clustering

❌ More computation

Time Complexity (Open Addressing)

Operation Average Case Worst Case

Search O(1) O(n)

Insert O(1) O(n)

Delete O(1) O(n)

Python Example (Linear Probing)

class HashTable:
def __init__(self, size):
[Link] = size
[Link] = [None] * size

def hash(self, key):

return key % [Link]

def insert(self, key):

index = [Link](key)
while [Link][index] is not None:
index = (index + 1) % [Link]
[Link][index] = key
 def display(self):
for i, val in enumerate([Link]):
print(i, ":", val)

6. Chaining (Closed Addressing)

Definition

In chaining, each hash table slot contains a linked list (or dynamic list).
When a collision occurs, the new key is appended to the linked list at that index.

Example
h(key) = key % 5

Keys: 10, 20, 25, 30, 12

Indexes:
10 → 0
20 → 0 (collision)
25 → 0 (collision)
30 → 0 (collision)
12 → 2

Table:
[0]: 10 → 20 → 25 → 30
[1]: None
[2]: 12

Advantages

✅ Simple and efficient collision handling

✅ Table never fills up (only linked lists grow)
✅ Deletion is easy

Disadvantages

❌ Extra memory for pointers

❌ Search time increases if chains grow long

Python Example (Chaining)

class HashTableChaining:
def __init__(self, size):
[Link] = size
[Link] = [[] for _ in range(size)]

def hash(self, key):

return key % [Link]

def insert(self, key):

index = [Link](key)
[Link][index].append(key)

def display(self):
for i in range([Link]):
print(f"{i}: {[Link][i]}")

7. Indexing
Definition

Indexing is a data structure technique that helps access data quickly — especially in databases and large
datasets.

An index acts like a lookup table that maps a key to the actual data location.

Example

Imagine a book’s index:

 You want to find “Binary Search.”

 The index says → “Page 78”
→ Go directly there instead of reading every page!

In Databases

In SQL databases, an index works like a hash table or B-tree, allowing:

 Faster search queries (e.g., SELECT * FROM students WHERE id = 101)

 Direct access instead of scanning all records.

️ 8. Comparison Table

Method Structure Collision Handling Memory Use Performance

Open Addressing Array only Store elsewhere in table Compact Slightly slower if full

Chaining Array of linked lists Store in separate linked lists More memory Consistent

Indexing Lookup table None (maps directly) Moderate Very fast

📊 9. Time Complexities

Operation Average Case (Hashing) Worst Case (Hashing) Indexing

Insert O(1) O(n) O(log n)

Search O(1) O(n) O(log n)

Delete O(1) O(n) O(log n)

💡 10. Real-World Applications

Use Case Technique Used

Password storage Hashing (with salts)

Database indexing Hash indexing, B-tree indexing

Compiler symbol tables Hashing with chaining

 Use Case Technique Used

Caches (like Redis, CPU cache) Hash tables

IP routing tables Hash-based lookup

⚠️ 11. Common Mistakes

❌ Using a poor hash function → uneven distribution, more collisions
❌ Forgetting to handle full table in open addressing
❌ Assuming hash tables maintain order (they don’t!)
❌ Using binary search instead of hashing for unordered data

Trees and traversals

What is a Tree?
Definition

A Tree is a non-linear data structure that represents data in a hierarchical form — like a family tree or
an organization chart.

Each element of a tree is called a node, and nodes are connected by edges.

Real-Life Examples

 Family Tree → parent, children relationships

 File System → folders and subfolders
 Company Hierarchy → CEO → Managers → Employees
 Decision Trees → used in AI for predictions

Basic Terminology

Term Description Example

Node A single element (data + links) e.g., 5
Root Topmost node of a tree e.g., A
Parent Node that has child nodes A is parent of B
Child Node descending from parent B is child of A
Siblings Nodes having the same parent B and C
Leaf Node with no children E, F, etc.
Edge Connection between nodes A → B
Height Longest path from root to leaf
Depth Distance of a node from root
Visual Example
A
/ \
B C
/ \
D E

 Root → A
 Parent of D and E → B
 Leaf nodes → D, E, C
 Height = 2

2. Properties of Trees
1. If a tree has n nodes, it has (n – 1) edges.
2. There is exactly one path between any two nodes.
3. The root node has no parent.
4. Leaf nodes have no children.

3. Binary Tree
A Binary Tree is a tree in which each node can have at most two children — usually referred to as:

 Left child
 Right child

Example
10
/ \
20 30
/ \
40 50

Types of Binary Trees

Type Description
Full Binary Tree Every node has 0 or 2 children
Complete Binary Tree All levels filled except possibly last
Perfect Binary Tree All internal nodes have 2 children and all leaves at same level
Degenerate Tree Every parent has only one child (acts like linked list)

4. Binary Tree Representation

(A) Array Representation

For node at index i:

 Left child → 2*i + 1

 Right child → 2*i + 2
 Parent → (i-1)//2
Example (Level Order):

Tree:
10
\ /
20 30
Array: [10, 20, 30]

(B) Linked Representation

Each node is a structure/class with:

 data
 left (pointer/reference)
 right (pointer/reference)

class Node:
def __init__(self, value):
[Link] = value
[Link] = None
[Link] = None

5. Tree Traversals
Definition

Traversal means visiting all the nodes of a tree in a specific order.

There are two main types:

1. Depth First Traversal (DFT)

o Inorder
o Preorder
o Postorder
2. Breadth First Traversal (BFT)
o Level Order

6. Depth First Traversals

Let’s use this tree:

A
/ \
B C
/ \
D E

(A) Inorder Traversal (Left → Root → Right)

Order: D, B, E, A, C

Pseudocode:

def inorder(node):
if node:
inorder([Link])
print([Link])
inorder([Link])
Example Use:
Used in Binary Search Trees (BST) to get elements in sorted order.

(B) Preorder Traversal (Root → Left → Right)

Order: A, B, D, E, C

Pseudocode:

def preorder(node):
if node:
print([Link])
preorder([Link])
preorder([Link])

Example Use:
Used to copy a tree or generate prefix expressions (used in expression trees).

(C) Postorder Traversal (Left → Right → Root)

Order: D, E, B, C, A

Pseudocode:

def postorder(node):
if node:
postorder([Link])
postorder([Link])
print([Link])

Example Use:
Used to delete a tree safely or generate postfix expressions.

📘 Summary Table – DFS Traversals

Traversal Type Visit Order Example Output (for tree above)

Inorder Left → Root → Right DBEAC
Preorder Root → Left → Right ABDEC
Postorder Left → Right → Root DEBCA

7. Breadth First Traversal (Level Order)

Definition

Visit nodes level by level, from left to right.

Example
Tree:
A
/ \
B C
/ \
D E
Output: A, B, C, D, E
Implementation (Using Queue)
from collections import deque

def level_order(root):
if not root:
return
queue = deque([root])
while queue:
node = [Link]()
print([Link])
if [Link]:
[Link]([Link])
if [Link]:
[Link]([Link])

8. Binary Search Tree (BST)

Definition

A BST is a binary tree where:

 Left child’s key < Parent’s key

 Right child’s key > Parent’s key

Example
50
/\
30 70
/ \ / \
20 40 60 80

 Inorder Traversal → 20 30 40 50 60 70 80 (Sorted)

Operations and Time Complexities

Operation Average Case Worst Case (Skewed Tree)

Search O(log n) O(n)
Insert O(log n) O(n)
Delete O(log n) O(n)

Example (Search in BST)

def search(root, key):
if root is None or [Link] == key:
return root
if key < [Link]:
return search([Link], key)
return search([Link], key)

9. Expression Trees
Definition

Used to represent arithmetic expressions in a tree form.

Each leaf node → operand
Each internal node → operator

Example:
Expression: (A + B) * (C - D)

*
/ \
+ -
/ \ / \
A B C D

 Preorder → * + A B - C D → Prefix
 Inorder → (A + B) * (C - D) → Infix
 Postorder → A B + C D - * → Postfix

10. Common Mistakes

❌ Mixing up the order of traversals (always remember Left/Right/Root sequence)
❌ Forgetting base case in recursion (causes infinite recursion)
❌ Assuming BST is balanced — not always true!
❌ Using arrays for large trees → memory waste

️ 11. Real-World Applications of Trees

Application Tree Used
File systems General trees
Databases (indexes) B-trees, B+ trees
Compilers Syntax/parse trees
AI search Decision trees
Networking Routing trees
Arithmetic expressions Expression trees
Priority management Heaps (a type of binary tree)

Expression trees
What is an Expression Tree?
Definition

An Expression Tree is a binary tree used to represent arithmetic expressions.

 Leaf nodes → operands (constants or variables like A, B, 3, x)

 Internal nodes → operators (+, -, *, /, ^)

It defines the order of evaluation of operations.

Example Expression

Expression:
(A + B) * (C - D)

Expression Tree:

*
/ \
+ -
/ \ / \
A B C D

Real-World Analogy

Think of a calculator:

 Each operator performs a task (like “add” or “multiply”)

 Each operand provides input values
The calculator internally follows the tree hierarchy to decide which operation to perform first.

2. Key Characteristics
Property Explanation
Binary Tree Every operator has at most 2 operands
Operands as Leaves Constants or variables are leaves
Operators as Internal Nodes Represent actions (e.g., +, *)
Recursion Evaluation naturally follows recursive logic
Structure Determines Order Parent nodes define operation order

3. Expression Tree Traversals and Notations

An expression can be represented in three forms:

 Infix (human-readable)
 Prefix (Polish)
 Postfix (Reverse Polish)

Each corresponds to a different tree traversal.

Example Tree
*
/ \
+ -
/ \ / \
A B C D
Traversal Type Traversal Order Result Expression Type
Inorder Left → Root → Right (A + B) * (C - D) Infix
Preorder Root → Left → Right * + A B - C D Prefix
Postorder Left → Right → Root A B + C D - * Postfix

4. Construction of Expression Trees

There are two main ways to construct expression trees:
A. From Postfix Expression

Postfix: A B + C D - *

Algorithm (using Stack):

1. Read the expression from left to right.

2. If the symbol is an operand, push it to the stack.
3. If the symbol is an operator, pop two operands from the stack, make them children, and push the
new tree node back.
4. The final element in the stack is the root of the expression tree.

Example:
Postfix: A B + C D - *

Step Symbol Stack (Top → Bottom)

1 A A
2 B B, A
3 + (+) → left=B, right=A
4 C C, (+)
5 D D, C, (+)
6 - (-) → left=D, right=C
7 * (*) → left=(+), right=(-)

✅ Final Tree:

*
/ \
+ -
/ \ / \
A B C D

B. From Prefix Expression

Prefix: * + A B - C D

Algorithm:

1. Read expression right to left.

2. If operand → push to stack.
3. If operator → pop two operands, create node, push result back.
4. The final node = root.

️ 5. Evaluating an Expression Tree

Each operator node performs an operation on its left and right child recursively.

Algorithm (Recursive)
def evaluate(root):
if root is None:
return 0
 # If leaf node → return its value
if [Link] is None and [Link] is None:
return int([Link])

# Evaluate left and right subtrees

left_val = evaluate([Link])
right_val = evaluate([Link])

# Apply operator
if [Link] == '+':
return left_val + right_val
elif [Link] == '-':
return left_val - right_val
elif [Link] == '*':
return left_val * right_val
elif [Link] == '/':
return left_val / right_val

Example

Expression Tree:

*
/ \
+ -
/ \ / \
3 2 4 1

Evaluation:

= (3 + 2) * (4 - 1)
= 5 * 3
= 15

️ 6. Implementation Example (Python)

class Node:
def __init__(self, value):
[Link] = value
[Link] = None
[Link] = None

# Function to build expression tree from postfix

def buildTree(postfix):
stack = []
for char in postfix:
if [Link](): # Operand
[Link](Node(char))
else: # Operator
right = [Link]()
left = [Link]()
node = Node(char)
[Link] = left
[Link] = right
[Link](node)
return stack[-1]

# Traversal functions
def inorder(node):
if node:
inorder([Link])
print([Link], end=" ")
inorder([Link])
def preorder(node):
if node:
print([Link], end=" ")
preorder([Link])
preorder([Link])

def postorder(node):
if node:
postorder([Link])
postorder([Link])
print([Link], end=" ")

# Example
expr = "AB+CD-*"
root = buildTree(expr)
print("Inorder: "); inorder(root)
print("\nPreorder: "); preorder(root)
print("\nPostorder: "); postorder(root)

️ 7. Time and Space Complexity

Operation Time Complexity Space Complexity
Build Tree O(n) O(n)
Traversal O(n) O(h) (h = height)
Evaluation O(n) O(h)

⚖️ 8. Expression Tree vs Other Representations

Method Description Example Evaluation Method
Infix Human-readable (A + B) * C Operator precedence rules
Prefix Operator before operands * + A B C Evaluate right to left
Postfix Operator after operands A B + C * Evaluate left to right
Expression Tree Hierarchical (Tree form) Recursively evaluate nodes

9. Real-World Applications
Application Explanation
Compilers Parsing arithmetic and logical expressions
Calculators Evaluate nested arithmetic
Query Processing SQL expression evaluation
Expression Evaluation in AI Used in symbolic math and logic systems
Code Generation Expression trees help compilers generate assembly code

⚠️ 10. Common Mistakes

❌ Forgetting operator precedence — tree structure automatically handles it
❌ Mixing prefix/postfix/infix incorrectly
❌ Popping wrong number of operands in postfix → must pop two operands for each operator
❌ Treating multi-digit numbers or variables as single characters without proper parsing
Binary search trees
What is a Binary Search Tree?
Definition

A Binary Search Tree (BST) is a special kind of binary tree where each node follows this property:

Left child < Root < Right child

That means:

 Every node in the left subtree has a smaller value than the root.
 Every node in the right subtree has a larger value than the root.

Example
50
/
\
30 70
/ \ / \
20 40 60 80

✅ Properties:

 Left of 50 → all smaller (30, 20, 40)

 Right of 50 → all greater (70, 60, 80)

Real-World Analogy

Think of a dictionary:

 Words are stored in alphabetical order.

 To find one, you don’t check every word — you “divide and search” by comparing midway entries.
 That’s exactly how BST search works!

2. BST Properties
Property Description

Binary Structure Each node has at most two children

Ordering Rule Left < Root < Right

Unique Keys Usually, each node stores a unique key

Recursive Nature Each subtree is itself a BST

Inorder Traversal Produces elements in sorted order

Inorder Traversal Example

For the above BST:

Inorder (Left → Root → Right) → 20, 30, 40, 50, 60, 70, 80

✅ Sorted output confirms valid BST.

⚙️ 3. Basic Operations on BST

Let’s go through the most important BST operations:
Search, Insertion, Deletion, Traversal

A. Search

Algorithm (Recursive)
def search(root, key):
if root is None or [Link] == key:
return root

if key < [Link]:

return search([Link], key)
else:
return search([Link], key)
Example

Search for 60:

50
/ \
30 70
/ \
60 80

Steps:

1. 60 > 50 → move right

2. 60 < 70 → move left
3. Found ✅

Time Complexity

Case Complexity

Best / Average O(log n)

Worst (Skewed Tree) O(n)

⚠⏱ Skewed tree = when all elements are in ascending or descending order (like a linked list).

B. Insertion

Algorithm

1. Start at root.
2. If tree is empty → new node becomes root.
3. If key < [Link] → insert in left subtree.
4. If key > [Link] → insert in right subtree.
Example

Insert 65 into:

50
/ \
30 70
/ \
60 80

Steps:

 65 > 50 → right
 65 < 70 → left
 65 > 60 → insert right of 60

✅ New Tree:

50
/ \
30 70
/ \
60 80
\
65
Code
class Node:
def __init__(self, data):
[Link] = data
[Link] = None
[Link] = None

def insert(root, key):

if root is None:
return Node(key)
if key < [Link]:
[Link] = insert([Link], key)
elif key > [Link]:
[Link] = insert([Link], key)
return root

C. Deletion

Deletion is slightly more complex — there are three cases.

Case 1: Node is a leaf

Simply remove it.

Example:
Delete 20

30
/
20 → just remove it
Case 2: Node has one child

Replace the node with its child.

Example:
Delete 30 from:

30
/
20

→ Replace 30 with 20.

Case 3: Node has two children

 Find inorder successor (smallest node in right subtree).

 Replace node’s value with that successor.
 Delete the successor.

Example:
Delete 50 from:

50
/ \
30 70
/ \
60 80

Inorder successor of 50 = 60

✅ Replace 50 with 60
✅ Delete 60 (from right subtree)

Result:

60
/ \
30 70
\
80
Code Example
def minValueNode(node):
current = node
while [Link]:
current = [Link]
return current

def deleteNode(root, key):

if root is None:
return root

if key < [Link]:

[Link] = deleteNode([Link], key)
elif key > [Link]:
[Link] = deleteNode([Link], key)
else:
# Node found
if [Link] is None:
return [Link]
elif [Link] is None:
return [Link]

temp = minValueNode([Link])
[Link] = [Link]
[Link] = deleteNode([Link], [Link])
 return root

4. Tree Traversals in BST

BST uses the same traversals as binary trees, but their meaning differs:

Traversal Type Order Result Meaning

Inorder Left → Root → Right Sorted order

Preorder Root → Left → Right For copying tree

Postorder Left → Right → Root For deleting tree

Example

BST:

50
\/
30 70
/ \ / \
20 40 60 80
Traversal Order

Inorder 20 30 40 50 60 70 80

Preorder 50 30 20 40 70 60 80

Postorder 20 40 30 60 80 70 50

5. Validating a BST
Sometimes you must check if a binary tree is a BST.

Rule

 The maximum value in the left subtree < root

 The minimum value in the right subtree > root

Recursive Approach
def isBST(root, min_val=float('-inf'), max_val=float('inf')):
if root is None:
return True
if [Link] <= min_val or [Link] >= max_val:
return False
return (isBST([Link], min_val, [Link]) and
isBST([Link], [Link], max_val))

6. Time and Space Complexities

Operation Average Case Worst Case (Skewed Tree)

Search O(log n) O(n)

Insertion O(log n) O(n)

Deletion O(log n) O(n)

Space O(n) O(n)

Why Skewed Tree = O(n)?

If data is inserted in sorted order, tree becomes one-sided:

50
\
60
\
70
\
80

→ Degenerates into a linked list.

To avoid this, use Balanced BSTs (like AVL or Red-Black Trees).

7. Real-World Applications of BST

Application Explanation

Databases For indexing and quick lookup

Search engines Keyword storage and retrieval

File systems Directory sorting

Auto-suggestion systems Maintain ordered words

Compilers Syntax analysis of variables

Memory management Allocating sorted blocks efficiently

⚠️ 8. Common Mistakes
❌ Confusing BST with Binary Tree (BST has ordering rule!)
❌ Forgetting to return nodes during recursion in insert/delete
❌ Not handling duplicate keys properly
❌ Building skewed trees with sorted input
❌ Forgetting base case for recursive calls

Heaps
What is a Heap?
Definition

A Heap is a complete binary tree that satisfies the heap property:

 Max-Heap → Every parent node has a value greater than or equal to its children.
 Min-Heap → Every parent node has a value less than or equal to its children.

Example

Max-Heap
50
/\
30 40
/ \ / \
10 20 35 25

✅ Parent ≥ Children
(50 > 30, 40; 30 > 10, 20; etc.)

Min-Heap
10
/\
20 15
/ \ / \
30 40 25 35

✅ Parent ≤ Children

Heap Characteristics

Property Explanation

Complete Binary Tree All levels filled except possibly the last (filled left to right).

Shape Property Always a complete tree — never “skewed.”

Heap Property For Max-Heap or Min-Heap, parent-child relationship follows the rule.

Not a BST! The ordering is local (only between parent and child), not global like in BST.

💾 2. Array Representation of a Heap

Heaps are usually stored in arrays, not as pointers or nodes.

For a node at index i:

 Left child → 2i + 1
 Right child → 2i + 2
 Parent → (i - 1) // 2

Example
Heap Tree:

50
/\
30 40
/ \ / \
10 20 35 25

Array Representation:

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

✅ Easy to access children/parents via index math.

3. Types of Heaps
Type Heap Property Use Case

Max-Heap Parent ≥ Children Priority queues (largest element first)

Min-Heap Parent ≤ Children Shortest path, scheduling, Huffman coding

4. Basic Operations on Heaps

Heaps mainly support:

 Insertion
 Deletion (Extract Root)
 Heapify
 Build Heap
 Peek (Get Max/Min)

A. Insertion into Heap

Steps

1. Insert new element at the end (next available leaf).

2. Heapify Up (Bubble Up) — compare with parent; swap until heap property is restored.

Example (Max-Heap)

Insert 45 into [50, 30, 40, 10, 20]

1⏱⃣ Add 45 → [50, 30, 40, 10, 20, 45]

2⏱⃣ Compare 45 with parent (40) → 45 > 40 → swap
✅ Final Heap → [50, 30, 45, 10, 20, 40]

Code (Python – Max-Heap Insert)

def heapify_up(heap, index):
parent = (index - 1) // 2
if index > 0 and heap[index] > heap[parent]:
heap[index], heap[parent] = heap[parent], heap[index]
heapify_up(heap, parent)
def insert(heap, value):
[Link](value)
heapify_up(heap, len(heap) - 1)

B. Deletion (Extract Root)

Steps

1. Remove the root (max or min).

2. Replace it with the last element.
3. Heapify Down (compare with children and swap as needed).

Example (Max-Heap)

Heap: [50, 30, 45, 10, 20, 40]

Delete 50

1⏱⃣ Replace 50 with last → [40, 30, 45, 10, 20]

2⏱⃣ Heapify Down → swap 40 ↔ 45
✅ Final → [45, 30, 40, 10, 20]

Code (Python – Max-Heap Delete)

def heapify_down(heap, index, size):
largest = index
left = 2 * index + 1
right = 2 * index + 2

if left < size and heap[left] > heap[largest]:

largest = left
if right < size and heap[right] > heap[largest]:
largest = right

if largest != index:
heap[index], heap[largest] = heap[largest], heap[index]
heapify_down(heap, largest, size)

def extract_max(heap):
size = len(heap)
if size == 0:
return None
root = heap[0]
heap[0] = heap[-1]
[Link]()
heapify_down(heap, 0, len(heap))
return root

C. Heapify Operation

Converts an unordered array into a heap.

Algorithm

 Start from the last non-leaf node → n/2 - 1

 Heapify each node downward
Example

Input: [10, 20, 15, 30, 40]

After heapify (Max-Heap): [40, 30, 15, 10, 20]

D. Build Heap

Call heapify on all non-leaf nodes (bottom-up).

✅ Time Complexity: O(n)

(Even though each heapify is O(log n), total cost averages out to O(n))

E. Peek (Get Root)

Return the element at index 0 — O(1) time.

📊 5. Heap Sort (Application of Heap)

Heap Sort uses a heap to sort an array efficiently.

Steps

1. Build a Max-Heap from array.

2. Repeatedly swap root with last element, reduce heap size, and heapify.

Example

Array: [4, 10, 3, 5, 1]

1⏱⃣ Build Max-Heap → [10, 5, 3, 4, 1]

2⏱⃣ Swap (10 ↔ 1) → [1, 5, 3, 4, 10]
3⏱⃣ Heapify remaining → [5, 4, 3, 1, 10]
4⏱⃣ Continue until sorted → [1, 3, 4, 5, 10]

✅ Sorted Output

Time & Space Complexity

Operation Time Complexity Space

Build Heap O(n) O(1)

Insert O(log n) O(1)

Delete (Extract Root) O(log n) O(1)

Peek O(1) O(1)

Heap Sort O(n log n) O(1)

🏗️ 6. Applications of Heaps
 Application Description

Priority Queues Highest (or lowest) priority element is served first

Heap Sort Efficient sorting algorithm

Graph Algorithms Used in Dijkstra’s & Prim’s algorithms

Job Scheduling Managing CPU processes based on priority

Median Finding Two heaps (max and min) used to find median in streams

Event-driven simulations Scheduling based on event time

️ 7. Real-World Examples
Scenario Heap Type Used Explanation

OS Process Scheduling Max-Heap Higher priority process runs first

GPS Route Optimization Min-Heap Smallest distance node processed first

Streaming Median Both Max-Heap for lower half, Min-Heap for upper half

Huffman Encoding Min-Heap Smallest frequency combined first

⚠️ 8. Common Mistakes
❌ Confusing heap property with BST ordering
❌ Forgetting to heapify after insert/delete
❌ Using O(n log n) for Build Heap (it’s O(n))
❌ Mixing up parent/child index formulas
❌ Trying to perform traversal-based sorting (heap only guarantees root order)

M-way trees
What is an M-Way Tree?
Simple Definition

An M-way tree is a tree data structure in which each node can have up to M children.
It’s a generalization of a binary tree (which is a 2-way tree).

Formal Definition

An M-way tree is a tree where:

 Each node contains at most (M – 1) keys (data items).

  Each node can have up to M children (subtrees).
 The keys within each node are ordered.

Visual Example (M = 4)

Each node can have up to 3 keys and 4 children:

[20 | 40 | 60]
/ | | \
<20 20–40 40–60 >60

✅ Here:

 Keys are sorted within the node.

 Each pointer (child) covers a range of values.

2. Why M-Way Trees?

Binary trees can become tall and inefficient for large datasets.
M-way trees reduce height by allowing more children per node, leading to faster searching and
insertion.

Analogy

Think of it like a library catalog:

 Instead of separating books into 2 categories (A–M, N–Z),

you separate them into 4 (A–E, F–J, K–O, P–Z).
✅ Faster search since fewer levels are needed.

3. Structure of an M-Way Tree Node

Each node typically contains:

 Keys (data values) — up to M – 1

 Pointers/Links to child nodes — up to M

Node Example (M = 4)

Key1 Key2 Key3

20 40 60

And 4 child pointers:

P0 | P1 | P2 | P3

Meaning:

 P0 → values < 20
 P1 → values between 20–40
 P2 → values between 40–60
 P3 → values > 60
4. Properties of M-Way Trees
Property Description
Degree (M) Max number of children a node can have
Keys per node Up to M – 1 keys
Minimum keys Varies by implementation (e.g., balanced trees may have rules)
Search property Keys in each node are sorted; subtrees follow range rules
Height Decreases as M increases (faster access)

5. Searching in M-Way Trees

Process

1. Start at the root node.

2. Compare key with all keys in the node.
3. If match → Found.
4. If smaller → move to left child; if larger → right child of the relevant key.
5. Repeat until found or node = null.

Example

Search for 55 in M=4 tree:

[20 | 40 | 60]
/ | | \
A B C D

1⏱⃣ 55 > 40 but < 60 → move to child C

2⏱⃣ Continue in subtree C

✅ Efficient search — fewer levels than BST.

Code-Like Pseudocode
def search(node, key):
if node is None:
return False
i = 0
while i < len([Link]) and key > [Link][i]:
i += 1
if i < len([Link]) and key == [Link][i]:
return True
return search([Link][i], key)

6. Insertion in M-Way Tree

Steps

1. Start at root, find the appropriate child pointer to follow.

2. Go down until reaching a leaf node.
3. Insert the key in sorted order within that node.
4. If the node exceeds (M – 1) keys → node splitting may be needed (used in B-trees).
Example (M=4)

Insert 50 into:

[20 | 40 | 60]

Result:

[20 | 40 | 50 | 60] ❌ (too many keys)

If max keys = 3, we split:

[40 | 60]
/ | \
[20] [50] [>60]

✅ This concept leads directly to B-trees and B+ trees.

7. Deletion in M-Way Tree

Deletion can be complex and depends on whether balancing rules apply.
Basic idea:

1. Find the key.

2. If leaf → remove directly.
3. If internal → replace with predecessor/successor from subtrees.
4. Adjust pointers to maintain order.

Balanced trees (like B-trees) handle deletion carefully to maintain structure.

8. Example of M-Way Tree Traversal

Like binary trees, M-way trees can be traversed using generalized inorder traversal:

for i = 0 to n-1:
traverse(child[i])
print(key[i])
traverse(child[n])

Example

Node: [10 | 20 | 30]

Inorder Traversal Order:

child0 → 10 → child1 → 20 → child2 → 30 → child3

📊 9. Time Complexity
Operation Average Time Explanation
Search O(logₘ n) Fewer levels than binary tree
Insert O(logₘ n) Depends on height
Delete O(logₘ n) Similar to insertion
Space O(n) Stores all elements
✅ As M increases, height decreases, improving performance.

Height Formula

If each node has M children:

Height ≈ logₘ(n)

(Binary Tree height ≈ log₂(n))

So a 4-way tree is shorter than a binary tree by roughly half.

🏗️ 10. Variants of M-Way Trees

Tree Type Description Used In
Binary Tree (M=2) Each node has 2 children Basic data structures
B-Tree Balanced M-way tree Databases, file systems
B+ Tree All data in leaves Database indexing
Trie (Prefix Tree) M determined by alphabet size Text search, autocomplete
M-ary Search Tree General M-way search structure Advanced searching

🌍 11. Real-World Applications

Application Use Case
Databases Indexing large datasets using B/B+ Trees
File Systems Directory hierarchies (NTFS, ext4)
Search Engines Storing word prefixes (Tries)
Memory Management Multi-level page tables
Routing Tables IP range lookup using tree structures

⚠️ 12. Common Mistakes

❌ Assuming M-way trees are always balanced (they’re not by default).
❌ Forgetting that node keys are sorted.
❌ Mixing M-way trees with binary search trees.
❌ Ignoring child pointer range logic.
❌ Forgetting max (M–1) keys per node rule.

✅ 13. Summary (Exam Revision)

Concept Key Points
Definition Tree with up to M children per node
Keys per node Up to M – 1
Ordering rule Keys in node are sorted
Search time O(logₘ n)
 Concept Key Points
Height logₘ(n)
Advantages Fewer levels → faster operations
Applications Database indexing, file systems
Examples B-trees, B+ trees, Tries

Balanced trees
What is a Balanced Tree?
Definition

A balanced tree is a tree data structure in which the height difference between subtrees is kept small to
ensure that operations like search, insertion, and deletion remain efficient (O(log n)).

In simpler terms:

A balanced tree keeps its branches evenly distributed so no side of the tree grows too tall.

Example

❌ Unbalanced Binary Search Tree (Skewed Tree)

1
\
2
\
3
\
4

Height = 4, behaves like a linked list → inefficient (O(n)) search.

✅ Balanced Tree
3
/ \
2 4
/
1

Height = 2 → faster operations (O(log n)).

2. Why Balance Matters

Property Balanced Tree Unbalanced Tree

Height O(log n) O(n)

Search Speed Fast Slow

Insert/Delete Predictable May degrade

Memory Access Efficient Skewed

 Property Balanced Tree Unbalanced Tree

Use Case Databases, indexing Rarely used in practice

✅ Balanced trees guarantee performance stability — crucial for real-world systems like file systems and
databases.

3. Balance Factor (Concept)

In many balanced trees (like AVL trees), balance is measured by the balance factor:

Balance Factor=Height of Left Subtree−Height of Right Subtree\text{Balance Factor} = \text{Height of Left

Subtree} - \text{Height of Right Subtree}Balance Factor=Height of Left Subtree−Height of Right Subtree

 If Balance Factor ∈ {–1, 0, +1} → Node is balanced.

 If outside this range → Tree needs rebalancing (rotation).

Example
10
/ \
5 15
/
2
Node Left Height Right Height Balance Factor Balanced?

10 2 1 +1 ✅

5 1 0 +1 ✅

15 0 0 0 ✅

4. How to Maintain Balance

When a tree becomes unbalanced (after insertion or deletion), rotations are used to restore balance.

Types of Rotations

Type When Used Fix

Left Rotation Right-heavy tree Rotate left

Right Rotation Left-heavy tree Rotate right

Left-Right Rotation Left-right heavy Double rotation

Right-Left Rotation Right-left heavy Double rotation

Right Rotation Example

Before:
 30
/
20
/
10

After:

20
/ \
10 30

✅ Balanced restored.

5. Searching in Balanced Trees

Searching works the same as in binary search trees (BSTs) but with guaranteed efficiency:

1. Start at root.
2. Compare key.
3. Go left or right depending on value.
4. Because the tree is balanced, height = O(log n), so search time = O(log n).

6. Insertion in Balanced Trees

1. Insert as in BST.
2. Update balance factors.
3. If any node becomes unbalanced, perform rotation to fix it.

✅ Ensures height stays ~log₂(n).

7. Deletion in Balanced Trees

1. Delete node like in BST.
2. Check balance factors up the path.
3. Apply rotation(s) if any node becomes unbalanced.

8. Common Types of Balanced Trees

Type Full Name Key Property Use Case

Adelson–Velsky & Landis Strictly balanced using

AVL Tree Fast searching
Tree balance factor

Red-Black Loosely balanced using Used in libraries (e.g., C++ map,

—
Tree coloring rules Java TreeMap)

Multi-way (M-way)
B-Tree — Databases, file systems
balanced tree

B-tree variant with all

B+ Tree — Database indexing
data in leaves
 Type Full Name Key Property Use Case

Each node has 2 or 3

2-3 Tree — Foundation of Red-Black Trees
children

Self-adjusting based on
Splay Tree — Caches, adaptive search
recent access

AVL vs Red- AVL stricter; Red-Black faster

—
Black insert/delete

9. Example: AVL Tree (Simplified)

Step 1: Insert 10, 20, 30
10
\
20
\
30

Unbalanced → Right-heavy.

Step 2: Apply Left Rotation

20
/ \
10 30

✅ Now Balanced.

📊 10. Time Complexity

Operation Balanced Tree (e.g., AVL) Unbalanced BST

Search O(log n) O(n)

Insert O(log n) O(n)

Delete O(log n) O(n)

Traversal O(n) O(n)

✅ Balanced trees maintain logarithmic height → efficient even in worst case.

11. Memory Usage

Balanced trees require:

 Extra space for balance factor or color info.

 Slightly more complex rotations.
But this overhead is small compared to the performance gain.
12. Height of a Balanced Tree
If there are n nodes and branching factor m:

Height≈log⁡m(n)\text{Height} ≈ \log_m(n)Height≈logm(n)

For binary balanced trees (m = 2):

Height≈log⁡2(n)\text{Height} ≈ \log_2(n)Height≈log2(n)

✅ Much smaller than unbalanced height = n.

13. Applications of Balanced Trees

Application Usage

Databases (B/B+ Trees) Indexing, fast record lookup

Compilers Syntax parsing trees

File Systems Directory structure (NTFS, ext4)

Operating Systems Scheduling and memory management

Language Libraries Red-Black trees for maps, sets

Networking Routing tables, caching

⚠️ 14. Common Mistakes

❌ Assuming BSTs are automatically balanced — they’re not.
❌ Forgetting to apply rotations after insert/delete.
❌ Confusing AVL (strict) and Red-Black (loose) balancing.
❌ Ignoring height difference criteria.

(AVL, Red Black)

Introduction
Balanced Binary Search Trees (BSTs) are special kinds of trees that keep their height small (≈ log₂n),
ensuring efficient search, insertion, and deletion operations.

Two popular types are:

Tree Type Balancing Method Strictness Common Use

AVL Tree Height difference (balance factor) Very strict Fast lookups

Red-Black Tree Color rules (red/black) Less strict Libraries, databases

🌲 2. AVL Trees

👨💻 Invented by:

Adelson-Velsky and Landis (1962) — first self-balancing binary search tree.

Definition
An AVL Tree is a binary search tree (BST) where the difference in height between the left and right
subtrees of any node (called the balance factor) is at most 1.

Balance Factor (BF)=Height(Left Subtree)−Height(Right Subtree)\text{Balance Factor (BF)} =

\text{Height(Left Subtree)} - \text{Height(Right
Subtree)}Balance Factor (BF)=Height(Left Subtree)−Height(Right Subtree)

 If BF ∈ {–1, 0, +1} → node is balanced

 If |BF| > 1 → unbalanced → needs rotation

Properties of AVL Trees

 Strictly balanced (height difference ≤ 1)
 Height ≈ log₂(n)
 Faster searching than Red-Black Trees
 Extra storage: each node stores a balance factor
 Rotations used to restore balance

🔁 Rotations in AVL Trees

To fix imbalance after insertion or deletion, AVL Trees perform rotations.

Case Type of Rotation Example Structure Fix

Left-Left (LL) Right Rotation Insertion in left subtree of left child Right Rotate

Right-Right (RR) Left Rotation Insertion in right subtree of right child Left Rotate

Left-Right (LR) Double Rotation (Left then Right) Left subtree’s right child Left + Right

Right-Left (RL) Double Rotation (Right then Left) Right subtree’s left child Right + Left

️ Example: LL Rotation

Insert 30, 20, 10

→ Tree becomes left-heavy (LL imbalance)

Before Rotation:

30
/
20
/
10
After Right Rotation:

20
/ \
10 30

✅ Balanced again (BF = 0 at all nodes)

️ Example: LR Rotation

Insert 30, 10, 20

→ Left-Right imbalance

Before:

30
/
10
\
20

Step 1: Left Rotation on (10)

Step 2: Right Rotation on (30)

After:

20
/ \
10 30

✅ Balanced

️ Time Complexities
Operation Time (Balanced)

Search O(log n)

Insertion O(log n)

Deletion O(log n)

✅ Always logarithmic due to strict balancing.

💡 Applications
 Databases requiring frequent lookups
 Memory indexing systems
 Compiler symbol tables

⚠️ Common Mistakes
 Forgetting to update height/balance factor after rotations
 Misidentifying rotation cases (LL vs LR, RR vs RL)
  Thinking AVL = BST (AVL is a type of BST)

🌳 3. Red-Black Trees

👨💻 Invented by:

Rudolf Bayer (1972), later improved by Guibas and Sedgewick.

⚙️ Definition
A Red-Black Tree is a binary search tree that maintains balance using color properties (each node is
either red or black) rather than strict height balance.

️ Red-Black Tree Properties

Every Red-Black Tree satisfies the following rules:

1. Each node is either red or black.

2. Root is always black.
3. Red nodes cannot have red children (no two reds in a row).
4. Every path from root to leaf has the same number of black nodes.
5. All leaves (NIL nodes) are black.

✅ These rules keep the tree approximately balanced.

📏 Height Property
If the tree has n nodes, the height is always ≤ 2 * log₂(n + 1)
➡⏱ Ensures O(log n) performance (not as strictly balanced as AVL).

🔁 Balancing Operations
When an insertion or deletion breaks the Red-Black rules, it’s fixed using:

 Recoloring (change red ↔ black)

 Rotations (Left or Right)
 Both together

️ Example: Insertion (Simple Case)

Insert: 10, 20, 30

1⏱⃣ Insert 10 → black (root)

2⏱⃣ Insert 20 → red
3⏱⃣ Insert 30 → red child of red → violates rule (two reds in a row)

Fix: Left Rotation + Recoloring

After balancing:

20(B)
 / \
10(R) 30(R)

✅ Rules satisfied again.

⚙️ Rotations Used

 Left Rotation
 Right Rotation
 Left-Right
 Right-Left

Same concept as AVL, but triggered by color violations instead of height imbalance.

️ Time Complexities
Operation Time

Search O(log n)

Insertion O(log n)

Deletion O(log n)

✅ Efficient in worst case due to balanced height.

️ AVL vs. Red-Black Tree Comparison

Feature AVL Tree Red-Black Tree

Balance Type Strict (height diff ≤ 1) Loose (color rules)

Balancing Method Rotations based on height Rotations + recoloring

Search Speed Faster (tighter height) Slightly slower

Insert/Delete Speed Slower (more rotations) Faster (fewer rotations)

Storage Needs balance factor Needs color bit

Use Case Databases, memory tables Libraries, OS, maps, sets

Height (approx) log₂(n) ≤ 2·log₂(n+1)

Examples in Use — Java TreeMap, C++ map/set, Linux scheduler

💡 Analogy for Memory

Concept AVL Red-Black

Like Strict teacher (perfect balance) Chill teacher (just enough balance)
Concept AVL Red-Black

Goal Perfectly equal height Keep overall structure balanced

Tradeoff More rotations Fewer rotations, easier maintenance

📚 Applications
 Red-Black Trees
o C++ STL (map, set)
o Java Collections (TreeMap, TreeSet)
o Linux kernel scheduler
o Symbol tables, compilers
 AVL Trees
o Memory-intensive databases
o Real-time lookups where search speed is critical

Graphs
What is a Graph?
Definition

A graph is a collection of vertices (nodes) and edges (connections between nodes).

G=(V,E)G = (V, E)G=(V,E)

 VVV = Set of vertices/nodes

 EEE = Set of edges (connections between nodes)

Example

Vertices: V={A,B,C,D}V = \{A, B, C, D\}V={A,B,C,D}

Edges: E={(A,B),(B,C),(C,D),(D,A)}E = \{(A,B), (B,C), (C,D), (D,A)\}E={(A,B),(B,C),(C,D),(D,A)}

Visual:

A --- B
| |
D --- C

🌿 2. Types of Graphs
Type Description Example Use Case
Directed Graph (Digraph) Edges have direction (A→B) Social media follower graph
Undirected Graph Edges have no direction Friendship network
Weighted Graph Edges have weights/costs Road maps, shortest path
Unweighted Graph Edges have no weights Basic connectivity
Cyclic Graph Contains a cycle Circuit networks
 Type Description Example Use Case
Acyclic Graph No cycles Task scheduling (DAG)
Connected Graph There is a path between every pair of vertices Road network
Disconnected Graph Not all vertices are reachable Isolated sub-networks

3. Graph Representations
A. Adjacency Matrix

 2D array of size V×VV \times VV×V

 Matrix[i][j] = 1 if edge exists (0 otherwise)
 Good for dense graphs

Example (Undirected Graph A-B-C)

Vertices: {A, B, C}

A B C
A0 1 0
B1 0 1
C0 1 0

B. Adjacency List

 Each vertex stores a list of connected vertices

 Efficient for sparse graphs

Example

A -> B
B -> A, C
C -> B

C. Edge List

 Simple list of edges:

[(A,B), (B,C), (C,A)]
 Easy to understand but less efficient for lookups.

4. Graph Terminology
Term Definition
Vertex (Node) Fundamental unit (point)
Edge Connection between two vertices
Degree Number of edges connected to a vertex
In-degree Number of incoming edges (directed graph)
Out-degree Number of outgoing edges (directed graph)
Path Sequence of vertices connected by edges
Cycle Path where first = last vertex
Connected Component Subgraph where any vertex is reachable from any other
 Term Definition
Weighted Edge Edge with a numeric value (cost, distance)

⚡ 5. Graph Traversal Algorithms

Graph traversal = visiting all vertices systematically

A. Breadth-First Search (BFS)

 Visits level by level

 Uses queue
 Finds shortest path in unweighted graphs

Algorithm Steps

1. Start at source vertex

2. Visit all neighbors, mark visited
3. Enqueue neighbors
4. Repeat until all vertices visited

Example (Graph A-B-C-D)

BFS starting at A: A → B → D → C

B. Depth-First Search (DFS)

 Visits as deep as possible before backtracking

 Uses stack (or recursion)
 Good for detecting cycles, topological sorting

Algorithm Steps

1. Start at source vertex

2. Visit a neighbor recursively
3. Backtrack when no unvisited neighbors remain

Example
DFS starting at A: A → B → C → D (depending on neighbor order)

️ 6. Weighted Graph Algorithms

Algorithm Purpose Complexity
Dijkstra Shortest path (non-negative weights) O(V²) or O(E + V log V) with min-heap
Bellman-Ford Shortest path (can handle negative weights) O(V·E)
Floyd-Warshall All pairs shortest path O(V³)
Prim’s Minimum Spanning Tree (MST) O(E log V)
Kruskal’s MST using edges sorted by weight O(E log E)

🌿 7. Special Graphs
 Directed Acyclic Graph (DAG)
 o No cycles
o Used in task scheduling, course prerequisites
o Topological sorting applies
 Complete Graph
o Every vertex connected to every other vertex
o Number of edges = n(n-1)/2 (undirected)
 Sparse Graph
o Few edges relative to vertices
o Use adjacency list
 Dense Graph
o Many edges
o Use adjacency matrix

💾 8. Real-World Applications of Graphs

Application Example
Social Networks Facebook, Twitter followers
Navigation Google Maps, shortest route
Network Routing Internet packet routing, OSPF
Task Scheduling Course prerequisite graph, project management
Recommendation Systems Users → products
Circuit Design Components as vertices, wires as edges

📊 9. Complexity Analysis
Operation Adjacency Matrix Adjacency List
Add Edge O(1) O(1)
Remove Edge O(1) O(degree(v))
Check Edge O(1) O(degree(v))
BFS/DFS O(V²) O(V + E)

✅ Adjacency list is generally more efficient for sparse graphs

⚠️ 10. Common Mistakes

❌ Treating directed edges as undirected
❌ Not marking visited nodes → infinite loops in DFS/BFS
❌ Ignoring negative weights in Dijkstra
❌ Confusing adjacency matrix and list complexities
❌ Forgetting that weighted graphs need algorithms like Dijkstra/Bellman-Ford

Breadth-first and depth-first traversal

What is Graph Traversal?
Graph traversal = systematically visiting all vertices in a graph.
  Purpose: Search, pathfinding, cycle detection, connectivity check.
 Two main strategies:
1. Breadth-First Search (BFS)
2. Depth-First Search (DFS)

2. Breadth-First Search (BFS)

Definition

BFS explores a graph level by level, visiting all vertices at distance k from the start node before visiting
vertices at distance k+1.

 Uses a queue data structure.

 Good for shortest path in unweighted graphs.

BFS Algorithm (Step-by-Step)

1. Initialize a queue and visited list/set.

2. Enqueue the starting vertex and mark it as visited.
3. While queue is not empty:
o Dequeue vertex v.
o Process v (e.g., print it).
o For each neighbor u of v:
 If u is not visited, mark as visited and enqueue u.

Pseudocode
def BFS(graph, start):
visited = set()
queue = [start]
[Link](start)

while queue:
v = [Link](0)
print(v, end=" ")
for neighbor in graph[v]:
if neighbor not in visited:
[Link](neighbor)
[Link](neighbor)

Example

Graph:

A
/ \
B C
/ \ \
D E F

BFS starting at A:
A → B → C → D → E → F

✅ Visits all vertices level by level

Complexity
  Time: O(V + E) → Each vertex and edge visited once
 Space: O(V) → Queue + visited list

Applications

 Shortest path in unweighted graphs

 Social network friend recommendations
 Level-order traversal in trees
 Web crawler (finding all reachable pages)

🌿 3. Depth-First Search (DFS)

Definition

DFS explores as deep as possible along a branch before backtracking.

 Uses stack (or recursion)

 Good for cycle detection, topological sorting, connected components

DFS Algorithm (Recursive Step-by-Step)

1. Start at the source vertex.

2. Mark it visited.
3. Process vertex (e.g., print).
4. For each unvisited neighbor, recursively call DFS.

Pseudocode
def DFS(graph, v, visited=set()):
[Link](v)
print(v, end=" ")
for neighbor in graph[v]:
if neighbor not in visited:
DFS(graph, neighbor, visited)

Example

Graph:

A
/ \
B C
/ \ \
D E F

DFS starting at A (using recursion):

A → B → D → E → C → F

Order may vary depending on neighbor processing order.

DFS Using Stack (Iterative)

def DFS_iterative(graph, start):
visited = set()
stack = [start]

while stack:
 v = [Link]()
if v not in visited:
[Link](v)
print(v, end=" ")
for neighbor in reversed(graph[v]):
if neighbor not in visited:
[Link](neighbor)

Complexity

 Time: O(V + E) → Each vertex and edge visited once

 Space: O(V) → Stack + visited set (recursive or iterative)

Applications

 Pathfinding in mazes
 Detect cycles in graphs
 Topological sorting (DAGs)
 Strongly connected components (Kosaraju’s/ Tarjan’s algorithm)

⚡ 4. BFS vs DFS Comparison

Feature BFS DFS
Data Structure Queue Stack / Recursion
Traversal Order Level by level Depth first
Shortest Path Yes (unweighted) No
Cycle Detection Possible Yes
Memory Usage More for wide graphs Less for deep graphs
Use Cases Shortest path, network broadcast Topological sort, maze solving, cycle detection

Visualization

Graph:

A
/ \
B C
/ \ \
D E F
BFS DFS
ABCDEFABDECF

BFS = explores neighbors first, DFS = explores one path to the end first

⚠️ 5. Common Mistakes
 Forgetting to mark vertices as visited → infinite loop
 Confusing BFS & DFS traversal order
 Using DFS for shortest path in unweighted graph (BFS should be used instead)
 Incorrect stack/queue implementation in iterative versions
Topological order
What is Topological Order?
Definition

A topological order of a Directed Acyclic Graph (DAG) is a linear ordering of vertices such that:

For every directed edge u→vu → vu→v, vertex u comes before vertex v in the ordering.

 Only DAGs can have a topological ordering.

 Not unique — multiple valid orders may exist.

Real-World Example

 Course Scheduling:
o Courses A → B → C
o A must be taken before B, B before C
o Topological order: A → B → C
 Build Systems / Compilation Order:
o Modules with dependencies must be compiled in order.

2. Conditions
1. Graph must be Directed
2. Graph must be Acyclic (no cycles)

If a cycle exists, topological sort is impossible.

3. Algorithms for Topological Sort

A. DFS-Based Approach

1. Initialize all vertices as unvisited

2. For each unvisited vertex, perform DFS
3. After visiting all neighbors, push the vertex onto a stack
4. Once DFS is complete for all vertices, pop vertices from stack → topological order

DFS Pseudocode
def topoDFS(graph):
visited = set()
stack = []

def dfs(v):
[Link](v)
for neighbor in graph[v]:
if neighbor not in visited:
dfs(neighbor)
[Link](v) # Add after exploring neighbors

for vertex in graph:

if vertex not in visited:
dfs(vertex)
 return stack[::-1] # Reverse stack to get topological order

Example

Graph:

5 → 0 ← 4
|
↓
2
|
↓
3 → 1

One possible topological order:

4 → 5 → 2 → 3 → 1 → 0

Vertices appear before their dependents.

B. Kahn’s Algorithm (BFS-Based)

1. Compute in-degree of all vertices

2. Enqueue all vertices with in-degree = 0
3. While queue is not empty:
o Dequeue vertex v, add to topological order
o For each neighbor u of v:
 Decrease in-degree of u by 1
 If in-degree of u becomes 0 → enqueue u
4. If all vertices are processed → topological sort complete
5. If not → graph has a cycle

Kahn’s Algorithm Pseudocode

from collections import deque

def topoKahn(graph):
in_degree = {v: 0 for v in graph}
for v in graph:
for neighbor in graph[v]:
in_degree[neighbor] += 1

queue = deque([v for v in graph if in_degree[v] == 0])

topo_order = []

while queue:
v = [Link]()
topo_order.append(v)
for neighbor in graph[v]:
in_degree[neighbor] -= 1
if in_degree[neighbor] == 0:
[Link](neighbor)

if len(topo_order) == len(graph):
return topo_order
else:
return "Graph has a cycle!"

4. Complexity
Algorithm Time Complexity Space Complexity
DFS-based O(V + E) O(V)
Kahn’s BFS O(V + E) O(V)

✅ Efficient for large DAGs.

5. Applications of Topological Sorting

Application Example
Task Scheduling Job sequences in project management
Course Prerequisites Ordering courses by dependency
Build Systems Compiling source files with dependencies
Instruction Scheduling CPU instruction ordering
Dependency Resolution Package managers (npm, pip)

6. Common Mistakes
 Applying topological sort on graphs with cycles
 Confusing DFS post-order with topological order
 Not updating in-degrees correctly in Kahn’s algorithm
 Assuming unique order — multiple valid topological orders exist

Shortest path
What is Shortest Path?
Definition:
The shortest path between two vertices in a graph is the path with minimum total weight or minimum
number of edges (if unweighted) connecting them.

 Weighted graph: Each edge has a cost, distance, or weight.

 Unweighted graph: Every edge has equal weight (often considered 1).

Applications:

 GPS navigation (road networks)

 Network routing (packet transmission)
 Game AI pathfinding
 Transportation scheduling

🌿 2. Algorithms for Shortest Path

A. BFS (Unweighted Graph)

 For unweighted graphs, shortest path = fewest edges.

 Use BFS because it explores level by level.

Steps:
 1. Start from the source vertex
2. Mark vertices as visited and track distance from source
3. Enqueue neighbors
4. First time reaching a vertex → shortest path

Example:

Graph:
A - B - D
| |
C - E

BFS from A:

 Distance to B = 1
 Distance to C = 1
 Distance to D = 2
 Distance to E = 2

Complexity:

 Time = O(V + E)
 Space = O(V)

B. Dijkstra’s Algorithm (Weighted Graph, Non-Negative Weights)

Definition:
Finds shortest paths from a single source to all vertices in a weighted graph with non-negative weights.

Steps:

1. Initialize distance to all vertices as ∞, distance to source = 0

2. Use a priority queue to pick vertex with minimum distance
3. For each neighbor, relax the edge:
4. if dist[u] + weight(u,v) < dist[v]:
5. dist[v] = dist[u] + weight(u,v)
6. Repeat until all vertices are processed

Example:

Graph (weights in parentheses):

A - B(4)
A - C(2)
B - C(5)
B - D(10)
C - D(3)

Dijkstra from A:

Vertex Distance
A 0
B 4
C 2
D 5 (via C → D)
Time Complexity:

 O(V²) with array

 O(E + V log V) with min-heap (priority queue)

C. Bellman-Ford Algorithm (Weighted Graph, Negative Weights Allowed)

Definition:
Finds single-source shortest path, works even if some edges have negative weights, but no negative
cycles.

Steps:

1. Initialize distances: source = 0, others = ∞

2. Relax all edges V-1 times
3. Check for negative cycles: if any edge can still be relaxed → negative cycle exists

Time Complexity: O(V × E)

Use Case: Graphs with negative edge weights, e.g., financial networks

D. Floyd-Warshall Algorithm (All-Pairs Shortest Path)

 Computes shortest paths between all pairs of vertices

 Dynamic programming approach

Steps:

1. Initialize distance matrix:

2. dist[i][j] = weight(i,j) if edge exists, else ∞
3. dist[i][i] = 0
4. For each vertex k:
5. for all i, j:
6. if dist[i][k] + dist[k][j] < dist[i][j]:
7. dist[i][j] = dist[i][k] + dist[k][j]

Time Complexity: O(V³)

Use Case: Dense graphs, all-pairs distances

🔁 3. Comparison of Shortest Path Algorithms

Algorithm Graph Type Negative Weights? Single/All Source Complexity
BFS Unweighted N/A Single Source O(V + E)
Dijkstra Weighted No Single Source O(E + V log V)
Bellman-Ford Weighted Yes Single Source O(V × E)
Floyd-Warshall Weighted Yes All Pairs O(V³)

💡 4. Example Use Cases

Algorithm Example
BFS Finding shortest route in unweighted road network
 Algorithm Example
Dijkstra GPS navigation with distance/time as edge weight
Bellman-Ford Currency arbitrage detection (negative cycles)
Floyd-Warshall Computing travel times between all cities

⚠️ 5. Common Mistakes
 Using Dijkstra with negative weights → incorrect results
 Forgetting to relax all edges in Bellman-Ford
 Not initializing distance[source] = 0
 BFS only works for unweighted graphs

Adjacency matrix and list

Why Graph Representation Matters
A graph can be represented in multiple ways for computational efficiency:

 Efficient edge lookups

 Efficient traversals (BFS/DFS)
 Memory usage optimization
 Algorithm selection depends on representation

🌿 2. Adjacency Matrix
Definition

An Adjacency Matrix is a 2D array (V × V) where:

matrix[i][j]={1if edge from vertex i to vertex j exists0otherwisematrix[i][j] = \begin{cases} 1 & \text{if

edge from vertex i to vertex j exists} \\ 0 & \text{otherwise} \end{cases}matrix[i][j]={10
if edge from vertex i to vertex j existsotherwise

 For weighted graphs, store weight instead of 1.

 Works for directed and undirected graphs.

Example

Graph:

A → B
B → C
C → A

Vertices: {A, B, C}

Adjacency Matrix:

ABC
A0 1 0
 ABC
B0 0 1
C1 0 0

 Row = source vertex

 Column = destination vertex
 1 indicates an edge exists

Properties / Complexity

Operation Complexity
Check if edge exists (i → j) O(1)
Add edge O(1)
Remove edge O(1)
Iterate neighbors O(V)
Space O(V²) → Can be large for sparse graphs

✅ Efficient for dense graphs but memory-heavy for large sparse graphs.

Advantages

 Simple and direct

 Quick edge lookup (O(1))
 Easy to implement

Disadvantages

 Wastes memory for sparse graphs

 Iterating neighbors = O(V), not optimal

🌿 3. Adjacency List
Definition

An Adjacency List is an array or list of lists, where each vertex stores a list of its neighbors.

 More memory-efficient for sparse graphs

 Can store weights for weighted graphs

Example

Graph:

A → B, C
B → C
C → A

Adjacency List:

A -> [B, C]
B -> [C]
C -> [A]
  Each vertex has a list of connected vertices
 For weighted graphs, store tuples: (neighbor, weight)

A -> [(B, 2), (C, 5)]

Properties / Complexity

Operation Complexity
Check if edge exists (i → j) O(degree(i))
Add edge O(1)
Remove edge O(degree(i))
Iterate neighbors O(degree(i))
Space O(V + E) → Efficient for sparse graphs

✅ Ideal for large sparse graphs.

Advantages

 Memory-efficient for sparse graphs

 Iterating neighbors is efficient (proportional to degree)

Disadvantages

 Checking if an edge exists → O(degree)

 Slightly more complex to implement than adjacency matrix

4. Comparison: Matrix vs List

Feature Adjacency Matrix Adjacency List
Space O(V²) O(V + E)
Edge Lookup O(1) O(degree(v))
Iterate Neighbors O(V) O(degree(v))
Best for Dense graphs Sparse graphs
Ease of Use Easy Slightly complex
Weighted Graph Easy (store weights) Easy (store tuple with weight)

Example Use Case

 Dense Graph: Social network where everyone is connected → adjacency matrix

 Sparse Graph: Road network or tree → adjacency list

Dynamic programming
What is Dynamic Programming?
Definition:
Dynamic Programming is a method for solving complex problems by breaking them into simpler
subproblems and storing the results of subproblems to avoid redundant computations.
  Works when the problem has:
1. Overlapping Subproblems → Same subproblem occurs multiple times
2. Optimal Substructure → Optimal solution can be built from optimal solutions of
subproblems

Real-World Analogy

 Making change for coins:

o To make 5$, you can use 1$ + 4$ or 2$ + 3$
o Solve smaller amounts first, reuse results to build bigger solutions

🌿 2. Key Concepts
1. Memoization (Top-Down)
o Recursive approach
o Store results in a table (array/dictionary) to avoid recalculation
2. Tabulation (Bottom-Up)
o Iterative approach
o Solve small subproblems first, then build up solution for larger problem
3. State
o Variables defining subproblem (e.g., n in Fibonacci, i,j in grid)
4. Transition/Recurrence Relation
o Formula to compute subproblem from smaller subproblems

⚡ 3. Common DP Problems
A. Fibonacci Numbers

Problem: Compute n-th Fibonacci number.

 Recursive (inefficient): O(2ⁿ)

 DP (Top-Down / Memoization): O(n)

Top-Down Example (Python)

def fib(n, memo={}):

if n <= 1:
return n
if n not in memo:
memo[n] = fib(n-1, memo) + fib(n-2, memo)
return memo[n]

Bottom-Up Example (Tabulation)

def fib(n):
dp = [0]*(n+1)
dp[1] = 1
for i in range(2, n+1):
dp[i] = dp[i-1] + dp[i-2]
return dp[n]

B. Knapsack Problem (0/1 Knapsack)

Problem:
  Items with weights and values
 Maximize value in knapsack with capacity W

DP Approach:

 dp[i][w] = maximum value using first i items with capacity w

Recurrence:

dp[i][w]=max⁡(dp[i−1][w],dp[i−1][w−weight[i]]+value[i])

Complexity: O(n*W)

Example:

 Items: [(weight=2, value=3), (weight=3, value=4)]

 Capacity = 5
 Max value = 7 (both items included)

C. Longest Common Subsequence (LCS)

Problem: Find longest subsequence common to two sequences.

 Strings: X = "ABCBDAB", Y = "BDCAB"

 LCS = "BCAB"

DP Table:

dp[i][j]={0i=0 or j=0dp[i−1][j−1]+1X[i−1]=Y[j−1]max⁡(dp[i−1][j],dp[i][j−1])X[i−1]≠Y[j−1]dp[i][j] =
\begin{cases} 0 & i=0 \text{ or } j=0 \\ dp[i-1][j-1] + 1 & X[i-1] = Y[j-1] \\ \max(dp[i-1][j], dp[i][j-1]) &
X[i-1] \neq Y[j-1] \end{cases}dp[i][j]=⎩⎨⎧0dp[i−1][j−1]+1max(dp[i−1][j],dp[i][j−1])
i=0 or j−1]

 Time Complexity: O(m * n)

 Space Complexity: O(m * n)

D. Matrix Chain Multiplication

Problem: Find minimum multiplication cost for matrix sequence.

 DP State: dp[i][j] = minimum cost to multiply matrices i…j

 Recurrence:

 Solves optimization problems in O(n³)

🔍 4. Steps to Solve a DP Problem

1. Identify Subproblems
o Break main problem into smaller overlapping problems
 2. Define State
o Decide variables that represent subproblem
3. Formulate Recurrence
o Express subproblem in terms of smaller subproblems
4. Decide Top-Down or Bottom-Up
o Recursive memoization or iterative tabulation
5. Implement Base Cases
6. Compute Final Solution
7. (Optional) Reconstruct Solution
o Trace back the DP table if solution sequence is needed

⚡ 5. Complexity Analysis
Approach Time Complexity Space Complexity
Top-Down (Memoization) Number of subproblems Number of subproblems (table)
Bottom-Up (Tabulation) Same as top-down Table size (can be optimized)

✅ DP trades memory for speed.

💡 6. Common DP Mistakes
 Forgetting base cases
 Not identifying overlapping subproblems
 Using recursion without memoization → exponential time
 Confusing subset sum / knapsack / LCS recurrence formulas
 Not optimizing space when possible (1D array instead of 2D)

Greedy algorithms
What Are Greedy Algorithms?
Simple Explanation

A greedy algorithm builds up a solution step by step, always choosing the best immediate (local) option
at each stage — without reconsidering previous choices.

It assumes that by choosing the local optimum, the overall (global) optimum will be reached.

Formal Definition

A greedy algorithm is one that selects the locally optimal choice at each step with the hope that these local
choices lead to a globally optimal solution.

Real-Life Analogy

 Imagine you are trying to get change for ₹10 using the least number of coins.
You pick the largest coin possible each time (₹5 → ₹2 → ₹2 → ₹1).
This greedy choice works perfectly when the currency system allows it.

2. Key Characteristics
 Feature Description
Greedy Choice Property Local choice leads to global solution
Optimal Substructure Solution to the problem can be built using optimal solutions to subproblems
No Backtracking Once a choice is made, it’s never changed
Efficiency Often runs faster than dynamic programming

When It Works

 Problem must have:

o Greedy Choice Property
o Optimal Substructure

✅ If either condition fails → greedy may not give the correct answer.

⚙️ 3. Steps in Designing a Greedy Algorithm

1. Define the Problem Clearly
o What needs to be minimized or maximized?
2. List All Choices Available
3. Define a Greedy Strategy
o What is the “best” choice at each step?
4. Prove That It Works (if required)
5. Implement Efficiently

️ 4. Common Greedy Algorithms with Examples

A. Activity Selection Problem

Goal:
Select the maximum number of activities that don’t overlap.

Example:

Activity Start Finish

A1 1 3
A2 2 5
A3 4 6
A4 6 8

Algorithm Steps:

1. Sort activities by finish time

2. Pick the first activity
3. For each next activity:
o If start time ≥ finish time of last selected → include it

Code Example (Python):

def activity_selection(activities):
[Link](key=lambda x: x[1]) # sort by finish time
selected = [activities[0]]
 last_finish = activities[0][1]
for i in range(1, len(activities)):
if activities[i][0] >= last_finish:
[Link](activities[i])
last_finish = activities[i][1]
return selected

Complexity:

 Sorting: O(n log n)

 Selection: O(n)

✅ Used in: Job scheduling, interval problems.

B. Fractional Knapsack Problem

Goal:
Maximize value of items in a knapsack that can hold fractional parts.

Given:

Item Weight Value Value/Weight

1 10 60 6
2 20 100 5
3 30 120 4

Algorithm Steps:

1. Sort items by value/weight ratio (descending)

2. Pick as much of the item as possible
3. If knapsack full → stop

Code Example:

def fractional_knapsack(items, capacity):

[Link](key=lambda x: x[1]/x[0], reverse=True)
total_value = 0
for w, v in items:
if capacity >= w:
total_value += v
capacity -= w
else:
total_value += v * (capacity / w)
break
return total_value

Complexity: O(n log n)

✅ Used in: Resource allocation, investment problems.

C. Huffman Coding (Data Compression)

Goal:
Compress data using variable-length binary codes.
Characters with higher frequency get shorter codes.

Steps:
 1. Create a min-heap of characters by frequency
2. Pick two smallest, merge into one node
3. Repeat until one tree remains

Example:

Char Freq
A 5
B 9
C 12
D 13
E 16
F 45

Huffman Tree → produces binary codes like:

F: 0, C: 100, D: 101, A: 1100, B: 1101, E: 111

✅ Used in: File compression (.zip, .mp3)

D. Kruskal’s Algorithm (Minimum Spanning Tree)

Goal:
Find MST (Minimum Spanning Tree) with minimum edge cost.

Steps:

1. Sort all edges by weight

2. Pick smallest edge that doesn’t form a cycle
3. Repeat until n−1 edges chosen

Complexity: O(E log E)

✅ Used in: Network design, circuit layout

E. Prim’s Algorithm (MST Alternative)

Goal:
Build MST by expanding from a single vertex.

Steps:

1. Start from any vertex

2. At each step, add smallest edge connecting a new vertex
3. Repeat until all vertices included

Complexity: O(V²) (or O(E log V) with heap)

✅ Used in: Road, electricity network design.

F. Dijkstra’s Shortest Path Algorithm

Goal:
Find shortest paths from source to all vertices in a weighted graph (non-negative weights).

Steps:

1. Set distance[source] = 0, others = ∞

2. Choose vertex with smallest distance not yet processed
3. Update distances to its neighbors
4. Repeat until all vertices processed

Complexity: O(V²) or O(E log V) (with priority queue)

✅ Used in: GPS, routing, maps, network packet delivery.

⚡ 5. Greedy vs Dynamic Programming

Feature Greedy Dynamic Programming
Approach Local best at each step Considers all possibilities
Backtracking No Yes
Optimal Substructure Required Required
Overlapping Subproblems Not required Required
Examples Dijkstra, Prim, Kruskal Knapsack, LCS, Fibonacci
Efficiency Faster Slower but more accurate

️ 6. Common Mistakes
 Assuming greedy always gives optimal result
 Forgetting to check for greedy choice property
 Not sorting input correctly before applying greedy logic
 Confusing Fractional Knapsack (greedy) with 0/1 Knapsack (DP)
 Ignoring tie-breaking conditions

Backtracking
What is Backtracking?
Definition:
Backtracking is a systematic method of exploring all possible solutions by:

1. Building a solution incrementally

2. Abandoning a partial solution (backtrack) if it cannot lead to a valid complete solution

It is often described as "trial and error with pruning."

Key Idea

 Explore all choices at each step

 If a choice leads to a dead-end, undo it (backtrack)
 Continue exploring other options
Analogy:

 Navigating a maze:
o Move forward until you hit a wall → backtrack → try another path

2. Characteristics of Backtracking
Feature Description
Recursive / Tree-based Often implemented with recursion
Exhaustive Search Tries all possibilities (prunes invalid paths)
Solution Space Tree of all possible partial solutions
Constraint Checking Prune paths that violate constraints
Optimality Can find all solutions or first valid solution

3. Steps to Solve a Problem Using Backtracking

1. Choose a state representation (variables or positions)
2. Define constraints to check validity
3. Build the solution incrementally
4. Backtrack if a partial solution violates constraints
5. Return complete solutions

4. Common Backtracking Problems

A. N-Queens Problem

Problem: Place N queens on an N×N chessboard such that no two queens attack each other.

Algorithm (Step-by-Step):

1. Place queen in a row, column by column

2. If safe → move to next row
3. If no safe position → backtrack to previous row
4. Repeat until all queens are placed

Code Snippet (Python)

def solve_n_queens(board, row, solutions):

N = len(board)
if row == N:
[Link]([''.join(r) for r in board])
return
for col in range(N):
if is_safe(board, row, col):
board[row][col] = 'Q'
solve_n_queens(board, row+1, solutions)
board[row][col] = '.' # Backtrack

Example (4x4 board):

 Solution 1:

. Q . .
. . . Q
Q . . .
. . Q .

 Solution 2:

. . Q .
Q . . .
. . . Q
. Q . .

B. Sudoku Solver

Problem: Fill a 9×9 Sudoku grid satisfying row, column, and 3×3 box constraints.

Algorithm:

1. Find first empty cell

2. Try numbers 1–9
3. If number valid → recurse to next empty cell
4. If stuck → backtrack

✅ Widely used in puzzles and constraint problems.

C. Subset Sum / Combinatorial Problems

Problem: Given set of integers, find subsets that sum to a target.

Algorithm:

 Include current element → recurse

 Exclude current element → recurse
 Backtrack when sum exceeds target

Example:
Set = [2, 3, 5], target = 5

 Subsets = [2,3], [5]

D. Maze Solving

Problem: Find path from start to end in a maze (grid with walls).

Algorithm:

1. Move in four directions (up, down, left, right)

2. Check bounds and obstacles
3. Mark path, recurse
4. If dead end → unmark and backtrack

✅ Used in robot navigation, games, and puzzle solving.

5. Backtracking vs Other Techniques

 Feature Backtracking Greedy Dynamic Programming
Solve subproblems + store
Approach Explore all possibilities Local optimum
results
Optimal for overlapping
Optimality Finds all or first solution Not guaranteed
subproblems
Constraint Checks constraints Assumes local choice is
Constraints indirectly handled
Handling dynamically safe
Activity selection,
Use Case N-Queens, Sudoku, Maze Knapsack, LCS, Fibonacci
Huffman

⚡ 6. Complexity
 Time complexity depends on the number of possible solutions:
o Worst-case = O(branch^depth)
o Example: N-Queens → O(N!)
 Space complexity = O(depth of recursion)

Note: Pruning constraints early reduces search space dramatically.

✅ 7. Tips for Backtracking Problems

 Always undo your last move before returning (backtrack)
 Prune early when constraints are violated
 Use recursion stack carefully
 Consider iterative approaches with stack if recursion depth is high
 Practice classic problems: N-Queens, Sudoku, subset sum, maze, word search

Amortized analysis
What is Amortized Analysis?
Definition:
Amortized analysis calculates the average time per operation over a sequence of operations, ensuring that
the occasional expensive operation does not make the average cost too high.

Unlike average-case analysis (which assumes random inputs), amortized analysis guarantees the average
cost over worst-case sequences.

Intuition / Real-Life Analogy

 Example: A printer’s ink cartridge lasts for 1000 pages.

o Printing a single page: very cheap
o Replacing cartridge: expensive
o Amortized cost per page = total cost / total pages
o Smooths out the occasional expensive operation

2. Why Amortized Analysis?

 Some operations are usually cheap, but occasionally very expensive.
 Traditional worst-case analysis may overestimate cost per operation.
  Amortized analysis gives a more realistic average cost for all operations in a sequence.

3. Methods of Amortized Analysis

A. Aggregate Method

 Compute total cost of n operations, divide by n to get amortized cost.

Example: Dynamic Array (Array Doubling)

 Operation: Append to array

 Cost pattern:
o Most appends = O(1)
o Occasionally, array doubles → O(n)

Calculation (Aggregate Method):

Operation Cost
Append 1 1
Append 2 1
Append 3 3 (array doubles)
Append 4 1
Append 5 5 (array doubles)

 Total cost for n operations ≤ 2n → Amortized cost = O(1) per append

B. Accounting (Banker’s) Method

 Assign a credit to cheap operations to pay for expensive ones.

 Each operation may cost more than actual, store credit for future operations.

Example: Dynamic Array

 Assign 2 units of cost per append:

o 1 unit = actual cost
o 1 unit = stored as credit
 When doubling occurs, stored credit pays for the copy → all operations O(1) amortized

C. Potential Method

 Define a potential function φ representing stored work or credit

 Amortized cost = actual cost + change in potential

Formula:

ci^=ci+(ϕi−ϕi−1)\hat{c_i} = c_i + (\phi_i - \phi_{i-1})ci^=ci+(ϕi−ϕi−1)

 Ensures average cost over sequence ≤ amortized cost

 Used in sophisticated data structures like Fibonacci heaps

️ 4. Examples of Amortized Analysis

A. Stack with Push, Pop, and Multipop

 Operations: push(x), pop(), multipop(k)

 Worst-case: multipop(k) = O(k)
 Amortized analysis:
o Each element pushed → popped at most once
o Total cost over n operations = O(n) → Amortized cost = O(1) per operation

B. Dynamic Array / Vector

 Append operation:
o Most of the time O(1)
o Occasionally O(n) when array doubles
 Amortized cost per append = O(1) using aggregate / accounting method

C. Binary Counter Increment

 Problem: Increment n-bit counter

 Observation: Flipping 0 → 1 is cheap, 1 → 0 flips propagate
 Worst-case per increment: O(k) (all bits flip)
 Amortized cost over n increments: O(1) per increment

5. Key Insights
 Amortized cost = total cost of operations / number of operations
 Helps analyze dynamic arrays, stacks with multipop, binary counters, splay trees
 Average-case analysis vs amortized analysis:
o Average-case = assumes input distribution
o Amortized = guarantees average cost for any input sequence

⚡ 6. Comparison with Other Analyses

Analysis
Basis Example Guarantees
Type
Worst-case Single operation Array append = O(n) Guaranteed upper bound
Average-case Random input Hash table insert Expected cost over random inputs
Sequence of Dynamic array Average cost over all operations in
Amortized
operations append sequence

Minimum spanning trees

What is a Minimum Spanning Tree?
Definition:
A Minimum Spanning Tree (MST) of a weighted, connected, undirected graph is a subset of edges that:

1. Connects all vertices (spanning tree)

2. Has no cycles
3. Has minimum possible total edge weight

Key Terms
  Spanning Tree: Connects all vertices without forming cycles
 Edge Weight: Cost, distance, or value associated with each edge
 Graph Type: Weighted, undirected, connected

Example:

Graph:

Vertices: {A, B, C, D}
Edges: A-B(1), B-C(4), A-C(3), C-D(2), B-D(5)

 MST edges: A-B(1), C-D(2), A-C(3) → Total weight = 6

Applications

 Network design (telecom, roads, electricity)

 Clustering and data analysis
 Approximation algorithms (like TSP heuristics)
 Circuit design

⚡ 2. Properties of MST
1. Number of edges: n−1 (where n = number of vertices)
2. Acyclic: No cycles
3. Connected: Every vertex is reachable
4. Greedy choice works: Local optimum edges lead to global MST
5. Cut Property: For any cut, minimum-weight edge across cut belongs to some MST
6. Cycle Property: Maximum-weight edge in a cycle cannot be in MST

3. Algorithms for MST

A. Kruskal’s Algorithm (Edge-Based Greedy)

Idea:
Add edges in increasing order of weight while avoiding cycles.

Steps:

1. Sort all edges by weight

2. Initialize disjoint sets for vertices
3. For each edge (u,v) in sorted order:
o If u and v are in different sets → add edge to MST, union sets
o Else → skip (would form cycle)

Example:

Edge Weight
A-B 1
C-D 2
A-C 3
B-C 4
B-D 5
  MST edges = A-B, C-D, A-C → total weight = 6

Complexity:

 Sorting edges: O(E log E)

 Union-Find operations: O(E α(V)) → almost O(E)

✅ Best for: Sparse graphs

B. Prim’s Algorithm (Vertex-Based Greedy)

Idea:
Grow MST starting from any vertex, always adding smallest edge connecting MST to a new vertex.

Steps:

1. Start from any vertex (e.g., A)

2. Add the minimum-weight edge connecting MST to remaining vertices
3. Repeat until all vertices included

Example:

 Start A → choose edge A-B(1) → add A-C(3) → add C-D(2) → MST complete

Complexity:

 O(V²) using adjacency matrix

 O(E log V) using adjacency list + min-heap

✅ Best for: Dense graphs

C. Comparison of Kruskal vs Prim

Feature Kruskal Prim

Approach Edge-based Vertex-based
Data Structure Disjoint-set Priority queue / min-heap
Best For Sparse graphs Dense graphs
Edge Sorting Required Not required
Cycle Detection Needed (Union-Find) Implicitly handled

4. MST Example Step-by-Step

Graph:

Vertices: A, B, C, D, E
Edges & weights:
A-B(2), A-C(3), B-C(1), B-D(4), C-D(5), C-E(6), D-E(7)

Kruskal’s MST:

1. Sort edges: B-C(1), A-B(2), A-C(3), B-D(4), C-D(5), C-E(6), D-E(7)

2. Pick B-C → add
3. Pick A-B → add
 4. Pick A-C → forms cycle → skip
5. Pick B-D → add
6. Pick C-D → cycle → skip
7. Pick C-E → add

MST edges: B-C, A-B, B-D, C-E → Total weight = 1+2+4+6=13

Prim’s MST (Start A):

1. MST = {A}
2. Minimum edge from MST: A-B(2) → add B
3. Minimum edge from MST: B-C(1) → add C
4. Minimum edge: B-D(4) → add D
5. Minimum edge: C-E(6) → add E

MST edges: A-B, B-C, B-D, C-E → Same weight = 13

✅ MST may not be unique if edge weights tie.

5. Complexity Summary
Algorithm Time Complexity Space Complexity Best For
Kruskal O(E log E) O(V) Sparse graphs
Prim (Matrix) O(V²) O(V²) Dense graphs
Prim (Heap + List) O(E log V) O(V+E) Sparse graphs

6. Tips and Key Points

 MST exists only for connected, undirected graphs

 Edge weight tie → multiple MSTs possible
 Cycle detection crucial in Kruskal
 Greedy property holds for MST → global optimum obtained
 Applications include network design, clustering, approximation algorithms

Algorithm correctness and complexity classes

Algorithm Correctness
An algorithm is correct if it:

1. Terminates after a finite number of steps

2. Produces the correct output for all valid inputs

Correctness ensures that an algorithm does what it is intended to do.

Types of Correctness

1. Partial Correctness
o If the algorithm terminates, the output is correct
o Does not guarantee termination
2. Total Correctness
 o Algorithm terminates and produces correct output

Proving Correctness

A. Loop Invariants

 A condition that holds true:

o Before loop starts
o After each iteration
o After loop ends → used to prove correctness

Example: Selection Sort

 Loop invariant: “Subarray arr[0…i-1] contains the i smallest elements in sorted order”
 Holds before/after each iteration → proves algorithm correctness

B. Induction

 Prove algorithm works for base case

 Assume it works for size k
 Prove it works for size k+1

⚡ 2. Complexity Classes
Definition:
Complexity classes group problems based on resources needed (time or space) to solve them.

 Time complexity: How running time grows with input size (n)
 Space complexity: How memory usage grows with input size

A. Common Complexity Classes

Class Description Examples

O(1) – Constant Time does not depend on input size Access array element, push to stack

O(log n) – Divide-and-conquer, halves input each

Binary search
Logarithmic step

Time grows proportionally with input

O(n) – Linear Simple search, traversal of array/list
size

O(n log n) Divide-and-conquer, merges or sorts Merge sort, Heap sort

O(n²) – Quadratic Nested loops over n Bubble sort, Selection sort

O(2^n) – Exponential Subsets or combinatorial growth Recursive Fibonacci, TSP brute-force

N-Queens naive solution, TSP brute-

O(n!) – Factorial All permutations
force

B. Big O, Big Omega, Big Theta

 1. Big O (O(f(n)))
o Upper bound of running time
o Worst-case scenario
o Example: Merge sort → O(n log n)
2. Big Omega (Ω(f(n)))
o Lower bound
o Best-case running time
o Example: Linear search → Ω(1)
3. Big Theta (Θ(f(n)))
o Tight bound
o Both upper and lower bounds
o Example: Merge sort → Θ(n log n)

C. Other Important Classes

Class Meaning Typical Problems

P Solvable in polynomial time Sorting, shortest path (Dijkstra)

NP Verifiable in polynomial time SAT, Hamiltonian cycle

NP-Complete Hardest problems in NP 3-SAT, TSP (decision version)

NP-Hard At least as hard as NP-complete Optimization TSP, subset sum

PSPACE Solvable in polynomial space Puzzle solving, generalized games

3. Algorithm Correctness + Complexity Example

Binary Search

1. Correctness:
o Loop invariant: “Target x, if exists, lies within subarray arr[low…high]”
o Maintained each iteration → guarantees partial correctness
o Loop terminates → total correctness
2. Complexity:
o Worst-case comparisons: O(log n)
o Space: O(1) (iterative), O(log n) (recursive)

Selection Sort

1. Correctness:
o Loop invariant: smallest elements placed correctly at each iteration
o Proves algorithm sorts entire array
2. Complexity:
o Time: O(n²) worst, best, average
o Space: O(1)

4. Key Insights
 Correctness ensures reliability → algorithm produces intended results
 Complexity measures efficiency → how resources grow with input
 Proving correctness often uses loop invariants, induction, recursion proofs
 Classifying complexity helps compare algorithms and select best approach