*** FULL DSA NOTES (UNIT 3–5) ***
=====================
UNIT 3 — TREES
=====================
DEFINITION:
A tree is a non-linear hierarchical data structure consisting of nodes connected by edges.
TERMINOLOGY:
Node, Root, Parent, Child, Leaf, Sibling, Subtree, Height, Depth, Level.
TYPES OF TREES:
General Tree, Binary Tree, Full Binary Tree, Complete Binary Tree, Skewed Tree.
BINARY TREE TRAVERSAL:
Inorder: L Root R
Preorder: Root L R
Postorder: L R Root
EXAMPLE:
/\
BC
/\\
DEF
Inorder: D B E A C F
Preorder: A B D E C F
Postorder: D E B F C A
BST (Binary Search Tree):
Left < Root < Right.
BST INSERTION:
Insert 50,30,70,20,40,60,80
Forms the standard BST.
BST DELETION CASES:
Case 1: Leaf
Case 2: One child
Case 3: Two children → replace with inorder successor.
AVL TREE:
Balanced BST. Balance Factor = Height(L) − Height(R)
ROTATIONS:
LL, RR, LR, RL
HEAP:
Complete binary tree.
Max Heap: parent >= children
Min Heap: parent <= children
Heap Insert: place at end, heapify up.
B-TREE:
Used in DBMS indexing.
Multi-way balanced tree.
=====================
UNIT 4 — SEARCHING, SORTING, HASHING
=====================
SEARCHING:
Linear Search: O(n)
Binary Search: O(log n), sorted array only.
SORTING:
Bubble Sort: O(n²)
Selection Sort: O(n²)
Insertion Sort: O(n²)
Merge Sort: O(n log n)
Quick Sort: Pivot-based, average O(n log n)
Heap Sort: Build heap + extract, O(n log n)
HASHING:
Hash Function: maps key→index
Collision: two keys map to same index
Collision Resolution:
→ Chaining
→ Open Addressing (Linear, Quadratic, Double Hashing)
Load Factor α = n/m
=====================
UNIT 5 — GRAPHS
=====================
GRAPH:
G = (V, E)
Types: Directed, Undirected, Weighted, Unweighted.
REPRESENTATION:
Adjacency Matrix: n×n matrix
Adjacency List: list of neighbours
BFS:
Uses Queue.
Level-wise traversal.
DFS:
Uses Stack/Recursion.
Deep traversal.
MST (Minimum Spanning Tree):
Prim’s Algorithm
Kruskal’s Algorithm
Shortest Path:
Dijkstra’s Algorithm
Bellman-Ford (when negative weights)
=====================
LAST DAY REVISION NOTES
=====================
Trees:
• Definitions, types
• Traversals (Inorder/Preorder/Postorder)
• BST rules + insert/delete
• AVL rotations (LL, RR, LR, RL)
• Heap insert/delete
Sorting:
• Merge sort steps
• Quick sort partition
• Heap sort idea
Searching:
• Linear vs Binary
Hashing:
• Hashing + Collision methods
Graphs:
• Matrix vs List
• BFS, DFS
• Prim & Kruskal
=====================
PREDICTED QUESTIONS
=====================
1. Perform inorder, preorder, postorder traversal.
2. BST insertion + deletion with diagram.
3. AVL rotation (LL/RR/LR/RL).
4. Heap insertion + heapify.
5. Merge sort working with example.
6. Quick sort partition.
7. Hashing + collision resolution.
8. Graph representation (Matrix/List).
9. BFS and DFS explanation.
10. MST using Prim/Kruskal with example.