🔹 1.

Insertion Sort
📘 Concept:

Insertion sort works like sorting cards in your hand.

It takes one element at a time and inserts it into its correct position among the already sorted part.

🔧 Algorithm Steps:

1. Start from index 1 (first element is assumed sorted).

2. Compare the current element with all previous elements.
3. Shift elements that are greater than the current one.
4. Insert the current element in its correct position.

🧠 Example:

Array: [5, 3, 4, 1]

Step Action Result

1 Take 3, compare with 5 → insert before 5 [3, 5, 4, 1]
2 Take 4, insert before 5 [3, 4, 5, 1]
3 Take 1, insert at start [1, 3, 4, 5]

Time Complexity:

Case Complexity
Best Case (already sorted) O(n)
Average Case O(n²)
Worst Case (reverse order) O(n²)

💾 Space Complexity:

O(1) (in-place)

Stability:

✅ Stable (does not change order of equal elements)

🔹 2. Selection Sort
📘 Concept:

Select the smallest (or largest) element and place it at the correct position.

🔧 Algorithm Steps:

1. Find the minimum element in the unsorted array.

2. Swap it with the first element.
3. Move to the next position and repeat.

🧠 Example:

Array: [29, 10, 14, 37, 14]

Step Action Result

1 Smallest = 10, swap with 29 [10, 29, 14, 37, 14]
2 Smallest = 14, swap with 29 [10, 14, 29, 37, 14]
3 Smallest = 14, swap with 29 [10, 14, 14, 37, 29]
4 Smallest = 29, swap with 37 [10, 14, 14, 29, 37]

Time Complexity:

Case Complexity
Best O(n²)
Average O(n²)
Worst O(n²)

💾 Space Complexity:

O(1) (in-place)

⚙️
Stability:

❌ Not stable (same elements’ order may change)

🔹 3. Bubble Sort
📘 Concept:

Repeatedly compare adjacent elements and swap them if they are in the wrong order.

🔧 Algorithm Steps:
 1. Compare adjacent pairs.
2. Swap if left element > right element.
3. Continue until array is sorted.

🧠 Example:

Array: [5, 3, 8, 4, 2]

Pass Result
1 [3, 5, 4, 2, 8]
2 [3, 4, 2, 5, 8]
3 [3, 2, 4, 5, 8]
4 [2, 3, 4, 5, 8]

Time Complexity:

Case Complexity
Best (already sorted) O(n)
Average O(n²)
Worst O(n²)

💾 Space Complexity:

O(1)

⚙️
Stability:

✅ Stable

🔹 4. Heap Sort
📘 Concept:

Uses binary heap (complete binary tree) to sort elements efficiently.

🔧 Algorithm Steps:

1. Build a max heap from the array.

2. Swap the root (max) with the last element.
3. Reduce heap size by one and heapify again.
4. Repeat until sorted.
🧠 Example:

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

1. Build Max Heap → [10, 5, 3, 4, 1]

2. Swap 10 with 1 → [1, 5, 3, 4, 10]
3. Heapify → [5, 4, 3, 1, 10]
4. Repeat…

Sorted → [1, 3, 4, 5, 10]

Time Complexity:

Case Complexity
Best O(n log n)
Average O(n log n)
Worst O(n log n)

💾 Space Complexity:

O(1)

⚙️
Stability:

❌ Not stable

🔹 5. Comparison of Sorting Algorithms

Algorithm Best Average Worst Space Stable Type
Insertion Sort O(n) O(n²) O(n²) O(1) ✅ Yes Comparison
Selection Sort O(n²) O(n²) O(n²) O(1) ❌ No Comparison
Bubble Sort O(n) O(n²) O(n²) O(1) ✅ Yes Comparison
Heap Sort O(n log n) O(n log n) O(n log n) O(1) ❌ No Comparison
Merge Sort O(n log n) O(n log n) O(n log n) O(n) ✅ Yes Comparison
Quick Sort O(n log n) O(n log n) O(n²) O(log n) ❌ No Comparison

🔹 6. Sorting in Linear Time (Non-Comparison Sorts)

🧩 A. Counting Sort
📘 Concept:

Counts occurrences of each element and places them in output according to count.
Used for integers within a known range.

🔧 Steps:

1. Find max element → k

2. Create count array of size k+1
3. Count each element.
4. Modify count array to store actual positions.
5. Place elements in output array.

🧠 Example:

Array: [4, 2, 2, 8, 3, 3, 1]

Count array → [0,1,2,2,1,0,0,0,1]

Output → [1,2,2,3,3,4,8]

Time Complexity:

O(n + k)
(where k = range of elements)

💾 Space Complexity:

O(n + k)

⚙️
Stability:

✅ Stable

🧩 B. Bucket Sort

📘 Concept:

Divide elements into buckets, sort each bucket (using insertion sort), then combine.

🔧 Steps:

1. Create n buckets (for value ranges)

2. Distribute elements
 3. Sort individual buckets
4. Concatenate buckets

🧠 Example:

Array: [0.42, 0.32, 0.23, 0.52, 0.25, 0.47]

Buckets:

 B1: [0.23, 0.25, 0.32]

 B2: [0.42, 0.47, 0.52]

Sorted → [0.23, 0.25, 0.32, 0.42, 0.47, 0.52]

Time Complexity:

Case Complexity
Best O(n + k)
Average O(n + k)
Worst O(n²)

💾 Space Complexity:

O(n + k)

⚙️
Stability:

✅ Stable

🔹 1. Terminology Used with Graph

📘 Definition:

A graph is a collection of nodes (vertices) and edges that connect pairs of nodes.

👉 Formally:
A graph G = (V, E) where

 V → Set of vertices (or nodes)

 E → Set of edges connecting pairs of vertices

🧠 Basic Terms:

Term Meaning Example

Vertex (Node) Fundamental unit of a graph A, B, C, D

Edge Connection between two vertices (A, B)

Adjacent vertices Two vertices connected directly by an edge A and B are adjacent

If A has 3 edges → degree =

Degree of a vertex Number of edges connected to a vertex
3

Path Sequence of edges connecting a series of vertices A → B → C

Cycle Path that starts and ends at the same vertex A→B→C→A

Every vertex can be reached from every other

Connected Graph —
vertex

Disconnected Graph Some vertices are unreachable —

Directed Graph
Edges have direction (A → B) A→B but not B→A
(Digraph)

Undirected Graph Edges have no direction (A, B) = (B, A)

Weighted Graph Each edge has a cost/weight (A, B, 5) means weight=5

🔹 2. Data Structures for Graph Representation

Graphs can be represented in 3 main ways:
🧩 A. Adjacency Matrix

📘 Definition:

A 2D array (matrix) of size V × V where V = number of vertices.

 matrix[i][j] = 1 if an edge exists between vertex i and vertex j

 Otherwise 0

🧠 Example:

Graph:

A -- B
| /
C

Vertices: A, B, C

ABC

A011

B101

C110

Time & Space:

Operation Complexity

Space O(V²)

Check edge (u,v) O(1)

Add/Delete edge O(1)

✅ Best for dense graphs (many edges)

🧩 B. Adjacency List
📘 Definition:

Each vertex stores a list of all vertices connected to it.

🧠 Example:

Graph:

A -- B
| /
C

Adjacency List:

A → [B, C]
B → [A, C]
C → [A, B]

Time & Space:

Operation Complexity

Space O(V + E)

Add/Delete edge O(1)

Check edge (u,v) O(V) in worst case

✅ Best for sparse graphs (few edges)

🧩 C. Incidence Matrix (Less Common)

Matrix of size V × E
Each row → vertex, each column → edge
Value is 1 if vertex is part of that edge, else 0.

🔹 3. Graph Traversal (Searching Techniques)

Traversal = visiting all vertices systematically.

Two main types:

1. Depth First Search (DFS)

 2. Breadth First Search (BFS)

🧩 A. Depth First Search (DFS)

📘 Concept:

Explore as far as possible along each branch before backtracking.

🔧 Steps:

1. Start from a source vertex.

2. Visit and mark as visited.
3. Recursively visit all unvisited adjacent vertices.

🧠 Example:

Graph:

A - B - D
| |
C E

Adjacency List:

A → [B, C]
B → [A, D, E]
C → [A]
D → [B]
E → [B]

DFS from A:
A→B→D→E→C

🧩 Implementation:

Usually done using Recursion or Stack

Time & Space:

Complexity Value

Time O(V + E)

Space O(V) (stack)

Use:

 Detecting cycles
 Topological sorting
 Path finding

🧩 B. Breadth First Search (BFS)

📘 Concept:

Explore all neighbors first, then move to next level.

🔧 Steps:

1. Start from a source vertex.

2. Visit all its adjacent vertices.
3. Move to next level.

🧠 Example:

Using same graph as above.

BFS from A:
A→B→C→D→E

🧩 Implementation:

Uses Queue data structure

Time & Space:

Complexity Value

Time O(V + E)

Space O(V) (queue)

Use:

 Shortest path in unweighted graph

 Level-wise traversal
🔹 4. Connected Components
📘 Definition:

A connected component is a subgraph in which any two vertices are connected by a path, and
which is connected to no additional vertices in the supergraph.

Example:

Graph:

A - B - C D - E

 There are 2 connected components: {A,B,C} and {D,E}

🧩 To Find Connected Components:

1. Start DFS or BFS from a vertex.

2. Mark all reachable vertices.
3. Repeat for unvisited vertices.
4. Each traversal = 1 connected component.

Time Complexity:

O(V + E) (using DFS/BFS)

Directed Graphs:
A graph in which edges have a direction, i.e., the edges have arrows
indicating the direction of traversal.

9. Undirected Graphs
An undirected graph is a graph where edges do not have a specific direction,
meaning connections go both ways. If two places are connected, you can
travel in either direction. Examples include friendships on social media and
two-way roads.

10. Weighted Graphs

A weighted graph is a graph where each edge has a number (weight) that
represents distance, cost, or time. These graphs help find the shortest or
cheapest paths. Examples include Google Maps, airline routes, and delivery

networks.

An unweighted graph is a graph where all edges are treated equally, with
no extra values like distance or cost. It simply shows connections between
points. Examples include basic social networks and metro maps without
travel times.
20. Connected or Disconnected Graph
Graph G is said to be connected if any pair of vertices (Vi, Vj) of a graph G is
reachable from one another. Or a graph is said to be connected if there
exists at least one path between each and every pair of vertices in graph G,
otherwise, it is disconnected. A null graph with n vertices is a disconnected
graph consisting of n components. Each component consists of one vertex
and no edge.

Last par t :

🌳 TREE DATA STRUCTURE – Detailed Notes (for STET Exam)

🔹 1. Basic Terminology Used with Trees

A Tree is a non-linear hierarchical data structure consisting of nodes connected by edges.
🧩 Basic Terms

Term Description Example

Node A single element in a tree e.g., A, B, C

Root Node The topmost node (starting point) A

Parent Node A node having child nodes A is parent of B, C

Child Node Nodes that have a parent B and C are children of A

Leaf Node Node with no children D, E, F

Edge Connection between parent and child A→B

Siblings Nodes having the same parent B, C

Sequence of edges from one node to

Path A→B→D
another

Max number of edges on root-to-leaf

Height of a Tree Length of the longest path from root to leaf
path

Depth of a Node Number of edges from root to that node Depth(root)=0

Degree of a Node Number of children of a node If A→B,C then degree(A)=2

Tree formed by any node and its

Subtree Node B and its children form subtree
descendants

🧠 Example Tree:
A
/ \
B C
/ \
D E

 Root = A
 Children of A = B, C
 Leaf nodes = D, E, C
 Height = 2
 Degree of A = 2
🔹 2. Binary Tree
📘 Definition:

A binary tree is a tree where each node has at most two children —
commonly known as left child and right child.

🧠 Example:
1
/ \
2 3
/ \
4 5

Here:

 Root = 1
 Left child of 1 = 2
 Right child of 1 = 3
 Left child of 2 = 4
 Right child of 2 = 5

🧩 Properties of Binary Tree:

1. Maximum nodes at level l = 2ˡ

3. Minimum height for n nodes = ⌈log₂(n+1)⌉ − 1

2. Maximum nodes in tree with height h = 2^(h+1) − 1

🔹 3. Binary Tree Representation

Binary trees are represented mainly in two ways:

🧩 A. Array Representation

Each node is stored at an index in an array.

If root is at index 1 (or 0), then:
 Relationship Formula

Root at index i —

Left child 2*i

Right child 2*i+1

Parent i / 2 (integer division)

🧠 Example:
A
/ \
B C
/ \
D E

Array (1-based index):

Index → 1 2 3 4 5
Value → A B C D E

So,

 Left child of A (1) → index 2

 Right child of A (1) → index 3
 Parent of D (4) → index 2

✅ Simple but wastes space for sparse trees

🧩 B. Pointer (Linked List) Representation

Each node has:

 Data
 Pointer to left child
 Pointer to right child

Node structure in C-like format:

struct Node {
int data;
struct Node* left;
struct Node* right;
};

🧠 Example:
10
 / \
20 30

Represented as:

↙ ↘
Node(10)

Node(20) Node(30)

✅ Memory efficient for dynamic trees

🔹 4. Binary Search Tree (BST)

📘 Definition:

A Binary Search Tree is a binary tree with a special property:

For every node,

 All keys in the left subtree are smaller

 All keys in the right subtree are greater

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

 Left subtree of 50 has values < 50

 Right subtree of 50 has values > 50

🔧 Operations in BST:

Operation Description Time Complexity

Search Compare value, go left or right O(h)

Insert Same as search, place node at leaf O(h)

Operation Description Time Complexity

Delete Remove node and fix tree O(h)

👉 where h = height of tree

✅ For balanced BST → O(log n)
❌ For skewed BST → O(n)

🧮 BST Traversals:

1. Inorder (L, Root, R) → sorted order

2. Preorder (Root, L, R) → copy of tree
3. Postorder (L, R, Root) → delete tree

Example:

4
/ \
2 5
/ \
1 3
Traversal Order

Inorder 12345

Preorder 4 2 1 3 5

Postorder 1 3 2 5 4

🔹 5. Complete Binary Tree

📘 Definition:

A complete binary tree is a binary tree where:

 All levels are completely filled

 The last level may be incomplete, but all nodes are as far left as possible

🧠 Example:

✅ Complete:
 1
/ \
2 3
/
4

❌ Not Complete:

1
/ \
2 3
\
4

📏 Properties:

 Height = ⌊log₂ n⌋
 Max nodes at height h = 2^(h+1) - 1
 Efficiently represented using arrays (used in heaps)

🔹 6. Extended Binary Tree (2-Tree)

📘 Definition:

An extended binary tree (or 2-tree) is a modified binary tree in which every node has either 0
or 2 children.

Sometimes, null children are replaced by special external nodes.

🧠 Example:

Normal Binary Tree:

A
/ \
B C
/ \
D E

Extended Binary Tree:

A
/ \
 B C
/ \ / \
D E NULL NULL

So every internal node has exactly two children (either real or NULL).

✅ Helps in defining full binary tree and expression tree evaluations.

🧮 Comparison Table
Type Property Example

Binary Tree Max 2 children Any structure

BST Left < Root < Right Sorted tree

Complete Binary Tree All levels filled except possibly last Heap

Extended Binary Tree Each node has 0 or 2 children Expression tree

🎯 Time & Space Complexity Summary

Operation Binary Tree BST (avg) Complete Binary Tree

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

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

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

Traversal O(n) O(n) O(n)

Space O(n) O(n) O(n)

🌳 ADVANCED TREE CONCEPTS – Detailed Notes for STET Exam

🔹 1. Extended Binary Trees (or 2-Trees)

📘 Definition:

An Extended Binary Tree is a binary tree where each node has either 0 or 2 children.

 Nodes with 0 children = External Nodes (Leaves)

 Nodes with 2 children = Internal Nodes

Used to convert incomplete binary trees into full binary trees by replacing null links with
special external nodes.
🧠 Example:

Normal Binary Tree:

A
/ \
B C
/
D

Extended Binary Tree:

A
/ \
B C
/ \ / \
D NULL NULL NULL
/ \
NULL NULL

Now, every internal node has exactly two children (either real or null).

✅ Use: Helpful in expression trees and tree traversal algorithms.

🔹 2. Tree Traversal Algorithms

Traversal = visiting all nodes exactly once in a specific order.

🧩 3 types of Depth First Traversals (DFS):

A. Inorder Traversal (Left → Root → Right)

Used for BSTs to get data in sorted order.

Example:

A
/ \
B C

Traversal → B, A, C
B. Preorder Traversal (Root → Left → Right)

Used to copy or serialize a tree.

Example:

A
/ \
B C

Traversal → A, B, C

C. Postorder Traversal (Left → Right → Root)

Used for deletion or expression evaluation.

Example:

A
/ \
B C

Traversal → B, C, A

D. Level Order Traversal (BFS type)

Visited level by level (uses Queue).

Example:

1
/ \
2 3
/ \
4 5

Level Order → 1, 2, 3, 4, 5

🕒 Time Complexity (all traversals):

O(n) → Every node visited once
Space Complexity: O(h) → h = tree height (stack/queue space)

🔹 3. Constructing Binary Tree from Given Traversals

To construct a unique binary tree, two traversals are needed:

 Inorder + Preorder, or
 Inorder + Postorder

🧠 Example:

Given:

 Preorder: A B D E C F
 Inorder: D B E A F C

Steps:

1. Preorder first element → Root = A

2. In inorder, find A → left part (D, B, E), right part (F, C)
3. Recursively repeat.

Constructed Tree:

A
/ \
B C
/ \ \
D E F

✅ Rule:

 Preorder → helps identify root first

 Inorder → divides into left and right subtrees

🔹 4. Operations in Binary Search Tree (BST)

📘 Definition:
A BST is a binary tree with:

 Left child < Parent

 Right child > Parent

🔧 A. Insertion

1. Compare new value with root.

2. Go left if smaller, right if greater.
3. Insert at empty position.

Example:
Insert 40 into this BST:

50
/ \
30 70

→ Goes left of 50 → right of 30

Result:

50
/ \
30 70
\
40

Time: O(h), where h = height (O(log n) if balanced, O(n) if skewed)

🔧 B. Searching

Same as insertion — recursively go left/right until found or null.

O(h)

🔧 C. Deletion

Three cases:

1. Node is leaf: delete directly

2. Node has one child: connect parent to child
 3. Node has two children:
o Replace node with inorder successor (or predecessor)
o Delete that node recursively

Example:
Delete 50 from

50
/ \
30 70
/
60

→ Replace 50 with inorder successor = 60

Result:

60
/ \
30 70

O(h)

🔧 D. Modification

Search the node and update its value while maintaining BST property.

🔹 5. Threaded Binary Tree

📘 Concept:

In a normal binary tree, many pointers are NULL.

Threaded Binary Tree utilizes these NULL pointers to make traversal faster without recursion
or stack.

🧩 Types:

1. Single Threaded: Each NULL right pointer points to inorder successor

2. Double Threaded:
o Left NULL → points to inorder predecessor
 o Right NULL → points to inorder successor

🧠 Example:

Inorder: 10 → 20 → 30 → 40

Threaded links:

 Right of 20 → 30 (successor)
 Left of 30 → 20 (predecessor)

✅ Advantage: Faster traversal without recursion

Time Complexity: O(n)
💾 Space Complexity: O(1)

🔹 6. Huffman Coding using Binary Tree

📘 Concept:

Huffman Coding is a compression technique using binary trees based on frequency of

characters.

Characters with higher frequency → shorter codes

Lower frequency → longer codes.

🔧 Steps:

1. Create leaf nodes for each character with its frequency.

2. Build a min-heap of these nodes.
3. Remove two smallest nodes, combine them, and insert their sum back.
4. Repeat until one node remains → Huffman Tree root.
5. Assign 0 to left edges, 1 to right edges → generate codes.

🧠 Example:
Character Frequency

A 5

B 9

C 12

D 13

E 16

F 45

Huffman Codes (example output):

F: 0
C: 100
D: 101
A: 1100
B: 1101
E: 111

✅ Applications:

 Data compression (ZIP, JPEG, MP3)

Time Complexity: O(n log n)

🔹 7. AVL Tree (Adelson-Velsky and Landis Tree)

📘 Definition:

An AVL Tree is a self-balancing Binary Search Tree.

For every node:

Balance Factor (BF) = height(left subtree) − height(right subtree)

|BF| ≤ 1 → tree is balanced

Otherwise → rotation required.
🔧 Rotations in AVL Tree:

When imbalance occurs, fix using rotations:

Case Type of Rotation

Left-Left (LL) Right Rotation

Right-Right (RR) Left Rotation

Left-Right (LR) Left + Right Rotation

Right-Left (RL) Right + Left Rotation

🧠 Example (LL Rotation):

Insert sequence: 30, 20, 10

30
/
20
/
10

→ Left-heavy → Apply Right Rotation

Result:

20
/ \
10 30

✅ Balanced BST

Time Complexity:
Insertion / Deletion / Search → O(log n)

🔹 8. B-Trees
📘 Concept:

A B-Tree is a self-balancing search tree used mainly in databases and file systems to store
data on disk.
Each node can have multiple keys and children (not just 2).

🧩 Properties:

1. All leaves are at the same level.

2. Every node can contain m/2 to m children (for order m).
3. Keys in a node are sorted.
4. Used for large data blocks and disk access efficiency.

🧠 Example (B-Tree of order 3):

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

✅ All data is kept sorted and balanced.

Time Complexities:

Operation Complexity

Search O(log n)

Insert O(log n)

Delete O(log n)

✅ Used in databases, file systems (NTFS, MySQL indexes)

🧮 Summary Table
Tree Type Key Feature Balance? Use

Binary Tree Max 2 children No General purpose

BST Ordered left-right No Searching

 Tree Type Key Feature Balance? Use

Extended Binary Tree Each node 0 or 2 children Yes Expression tree

Threaded Tree Fast traversal Yes Stackless traversal

Huffman Tree Weighted coding — Data compression

AVL Tree Self-balancing BST Yes Fast searching

B-Tree Multi-key balanced tree Yes Disk storage