Data Structure & Algorithm NOTES by anees ahmad

Contents
LINKED LIST.....................................................................5
1. What is a Linked List?.............................................5
Definition (Exam-Oriented)....................................5
Detailed Explanation..............................................5
Real-World Analogy................................................5
Structure of a Node................................................5
2. Why Linked List? (Need of Linked List)...................5
3. Linked List vs Array (VERY IMPORTANT).................5
Comparison Table...................................................5
Why Linked List is Better than Array.......................5
4. Representation of Linked List in Memory...............6
5. Traversing a Linked List...........................................6
Definition................................................................6
Traversal Steps.......................................................6
6. Searching in Linked List...........................................6
Definition................................................................6
Key Points...............................................................6
Real-Life Analogy....................................................6
7. Overflow and Underflow Conditions......................6
Overflow in Linked List...........................................6
Underflow in Linked List.........................................6
8. Operations in Linked List........................................6
A. Insertion Operations..........................................6
B. Deletion Operations...........................................7
9. Types of Linked List.................................................7
1. Singly Linked List.................................................7
2. Doubly Linked List...............................................7
3. Circular Linked List..............................................7
4. Circular Doubly Linked List..................................7
10. Differentiation Between Linked List Types...........7
11. Advantages of Linked List.....................................8
12. Disadvantages of Linked List.................................8
13. Complete Example Program (C++)........................8

1
 Data Structure & Algorithm NOTES by anees ahmad
14. Final Exam-Ready Summary.................................8
SEARCHING.....................................................................8
1. What is Searching?.................................................8
Definition (For Exams)............................................8
Why Searching is Important?.................................8
Real-Life Analogy....................................................8
2. What is Sequential Searching?...............................9
Meaning.................................................................9
3. Searching Algorithms (Overview)...........................9
4. Linear Search (Sequential Search)..........................9
Definition................................................................9
How Linear Search Works?.....................................9
Example..................................................................9
Characteristics........................................................9
Time Complexity Explanation.................................9
Linear Search Code (C++)........................................9
Advantages...........................................................10
Disadvantages......................................................10
5. Binary Search........................................................10
Definition..............................................................10
Mandatory Condition...........................................10
Working of Binary Search.....................................10
Example................................................................10
Real-World Analogy..............................................10
Time Complexity Explanation...............................10
Binary Search Code (C++).....................................10
Advantages...........................................................11
Disadvantages......................................................11
6. Binary Search Tree (BST) Searching......................11
Definition..............................................................11
How Searching Works in BST?..............................11
BST Search Code (C++)..........................................11
Time Complexity...................................................11
7. Comparison of Searching Algorithms (Very Important) 12

2
 Data Structure & Algorithm NOTES by anees ahmad
8. Which Searching Algorithm is Best?.....................12
Answer (Perfect Exam Statement)........................12
Best Choice Summary...........................................12
9. Final Revision Points (Write in Exam Conclusion). 12
SORTING.......................................................................12
1. What is Sorting?...................................................12
Exam-Oriented Definition.....................................12
Explanation...........................................................12
Example................................................................12
Real-World Analogies...........................................12
2. Why Sorting is Needed in DSA?............................13
Importance / Need of Sorting...............................13
Advantages of Sorting...........................................13
3. Classification of Sorting Algorithms......................13
(a) Comparison Based Sorting..............................13
(b) Based on Memory Usage................................13
4. Bubble Sort (Detailed)..........................................13
Definition..............................................................13
Working Principle.................................................13
Step-by-Step Example...........................................13
Analogy.................................................................13
Time Complexity...................................................13
Space Complexity.................................................14
Advantages...........................................................14
Disadvantages......................................................14
5. Selection Sort (Detailed).......................................14
Definition..............................................................14
Working Principle.................................................14
Example................................................................14
Analogy.................................................................14
Complexity............................................................14
Advantages...........................................................14
Disadvantages......................................................14
6. Insertion Sort (Detailed).......................................14
Definition..............................................................14

3
 Data Structure & Algorithm NOTES by anees ahmad
Working Principle.................................................14
Example................................................................14
Analogy.................................................................15
Complexity............................................................15
Advantages...........................................................15
Disadvantages......................................................15
7. Quick Sort (Detailed)............................................15
Definition..............................................................15
Working Principle.................................................15
Example................................................................15
Analogy.................................................................15
Complexity............................................................15
Advantages...........................................................15
Disadvantages......................................................15
8. Comparison Table (VERY IMPORTANT).................15
9. Which Sorting Algorithm is Best?.........................16
Exam Answer:.......................................................16
Best Use Summary................................................16
10. Final Exam Conclusion........................................16
MERGE SORT................................................................16
1. What is Merge Sort?.............................................16
Exam-Oriented Definition.....................................16
2. Basic Idea / Concept of Merge Sort......................16
Key Point for Exam...............................................16
3. Real-Life Analogy..................................................16
4. Working of Merge Sort (Step-by-Step).................16
Example................................................................16
Step 1: Divide........................................................16
Step 2: Merge & Sort............................................17
Step 3: Final Merge...............................................17
5. Characteristics of Merge Sort...............................17
6. Time & Space Complexity (VERY IMPORTANT).....17
Time Complexity...................................................17
Space Complexity.................................................17
7. Advantages of Merge Sort....................................17

4
 Data Structure & Algorithm NOTES by anees ahmad
8. Disadvantages of Merge Sort................................17
9. Merge Sort Algorithm (Steps for Exam)................17
10. Simple C++ Program for Merge Sort...................17
11. Updated Comparison Table (Including Merge Sort) 18
12. Quick Exam Question:.........................................18
Exam Answer:.......................................................18
13. Final Conclusion (Write This!).............................18
TREE.............................................................................18
1. What is a Tree?.....................................................19
Exam-Oriented Definition.....................................19
Explanation...........................................................19
Key Exam Points...................................................19
Real-World Analogies...........................................19
2. Basic Terminology of Trees (VERY IMPORTANT)...19
1. Node.................................................................19
2. Root..................................................................19
3. Parent Node.....................................................19
4. Child Node........................................................19
5. Sibling...............................................................19
6. Leaf Node (External Node)................................19
7. Internal Node....................................................19
8. Edge..................................................................19
9. Degree of a Node..............................................20
10. Degree of Tree................................................20
11. Level of Node..................................................20
12. Height of Tree.................................................20
13. Depth of Node................................................20
14. Subtree...........................................................20
3. Properties of Tree (Exam-Relevant)......................20
4. Representation of Tree in Memory......................20
(A) Linked Representation (Most Used)................20
Why Linked Representation?................................20
5. Classification / Types of Trees..............................20
5.1 General Tree.......................................................20
Definition..............................................................20

5
 Data Structure & Algorithm NOTES by anees ahmad
Example................................................................20
Disadvantages......................................................21
5.2 Binary Tree ⭐⭐⭐.................................................21
Definition..............................................................21
Properties.............................................................21
Uses......................................................................21
6. Types of Binary Trees............................................21
6.1 Full Binary Tree...............................................21
6.2 Complete Binary Tree.....................................21
6.3 Perfect Binary Tree.........................................21
6.4 Skewed Binary Tree........................................21
7. Binary Search Tree (BST) ⭐⭐⭐⭐⭐..........................21
Definition (VERY IMPORTANT)..............................21
Example................................................................21
Advantages...........................................................21
Time Complexity (BST)..........................................21
8. Tree Traversal (VERY IMPORTANT EXAM TOPIC)..22
8.1 Depth First Traversal (DFS).................................22
(a) Inorder Traversal.............................................22
(b) Preorder Traversal...........................................22
(c) Postorder Traversal.........................................22
Example Tree........................................................22
8.2 Breadth First Traversal (BFS)..............................22
Level Order Traversal............................................22
9. Operations on Tree...............................................22
1. Insertion...........................................................22
2. Deletion (BST)...................................................22
3. Searching..........................................................23
4. Traversal...........................................................23
10. Advantages of Tree.............................................23
11. Disadvantages of Tree........................................23
12. Applications of Trees..........................................23
13. Simple Binary Tree Program (Exam-Friendly).....23
14. Tree vs Linear Data Structures (EXAM COMPARISON) 23
15. Final Exam Conclusion (WRITE THIS)..................24

6
Data Structure & Algorithm NOTES by anees ahmad

LINKED LIST
(Data Structures & Algorithms – Final Exam Notes)

1. What is a Linked List?

Definition (Exam-Oriented)

A Linked List is a dynamic linear data structure

in which data elements are stored in the form of
nodes, where each node contains:

1. Data
2. A pointer (link) that stores the address of
the next node in the list.

The nodes are not stored in contiguous memory

locations.

Detailed Explanation

 In a linked list, memory is allocated at

runtime
 Nodes can be stored anywhere in memory
 Logical order is maintained using pointers
 Access to elements is sequential, not direct

Real-World Analogy

Think of a train:

 Each coach is a node

 Each coach has:
o Passengers (data)
o A connection to the next coach
(pointer)
 Coaches are connected logically, not placed
together in memory

7
 Data Structure & Algorithm NOTES by anees ahmad
Structure of a Node

[data | next]
4. Representation of Linked List in
Memory

2. Why Linked List? (Need of Linked  Each node is stored anywhere in RAM
List)  Pointer stores the address of the next node
 First node is pointed by HEAD
Arrays have limitations:  Last node points to NULL
 HEAD
 Fixed size  ↓
 Memory wastage  [10|•] → [20|•] → [30|NULL]
 Costly insertion and deletion

Linked lists solve these problems by using dynamic 5. Traversing a Linked List
memory allocation.
Definition

Traversing is the process of visiting each node of

3. Linked List vs Array (VERY the linked list exactly once to access or display its
IMPORTANT) data.

Comparison Table

Feature Array Linked List Traversal Steps

Size Fixed Dynamic 1. Start from head
2. Read data
Memory Allocation Compile time Run time 3. Move to next node
Memory Location Contiguous Non-contiguous 4. Stop when NULL is reached

Insertion Difficult (shifting) Easy

Deletion Difficult Easy Code (Traversal)

void traverse(Node* head) {
Memory Wastage Yes No
Node* temp = head;
Access Time Fast (O(1)) Slow (O(n)) while(temp != NULL) {
cout << temp->data << " ";
Implementation Simple Complex temp = temp->next;
}
}

Why Linked List is Better than Array

6. Searching in Linked List
 Efficient memory utilization
 No overflow until memory is exhausted Definition
 Best for dynamic data
 Faster insertion & deletion

8
 Data Structure & Algorithm NOTES by anees ahmad
Searching is the process of finding a specific  New node points to head
element in a linked list by checking each node  Head moves to new node
sequentially.  newNode->next = head;
 head = newNode;

Key Points
2. Insertion at End
 No random access
 Time complexity = O(n)  Traverse till last node
 Works same for sorted and unsorted lists  Last node’s next → new node

Real-Life Analogy 3. Insertion at Specific Position

Finding a word in a dictionary without  Traverse till required position

alphabetical order — you must check page by  Adjust pointers
page.

B. Deletion Operations
7. Overflow and Underflow Conditions
1. Deletion from Beginning
Overflow in Linked List
 Head moves to next node
Occurs when:  Old head deleted

 System is unable to allocate memory for a

new node
2. Deletion from End
Cause: Heap memory exhausted
 Traverse to second last node
 Last node deleted

Underflow in Linked List

Occurs when: 3. Deletion of Specific Node

 Deletion is attempted on an empty linked  Search element

list  Adjust links
 Free memory

8. Operations in Linked List

9. Types of Linked List
A. Insertion Operations

1. Insertion at Beginning

9
 Data Structure & Algorithm NOTES by anees ahmad
1. Singly Linked List  Flexible data storage

 Each node has one pointer

 Forward traversal only
12. Disadvantages of Linked List
 [data | next]
 Extra memory for pointers
 Slower access
 Complex implementation
2. Doubly Linked List  No random access
 Each node has two pointers
 Backward + forward traversal
13. Complete Example Program (C+
 [prev | data | next] +)
 #include <iostream>
 using namespace std;
3. Circular Linked List 
 struct Node {
 Last node points to head  int data;
 No NULL pointer  Node* next;
 };
 LAST → HEAD

 int main() {
 Node* head = new Node();
4. Circular Doubly Linked List  Node* second = new Node();
 Node* third = new Node();
 Doubly + circular 
 Efficient traversal in all directions  head->data = 10;
 head->next = second;

10. Differentiation Between Linked  second->data = 20;
List Types  second->next = third;

Feature Singly Doubly Circular
 third->data = 30;
Pointers per node 1 2 1  third->next = NULL;

Traversal One-way Two-way Circular  Node* temp = head;
 while(temp != NULL) {
Memory Used Least Maximum Medium  cout << temp->data << " ";
Last Node Points To NULL NULL Head  temp = temp->next;
 }

 return 0;
11. Advantages of Linked List  }

 Dynamic size
 Efficient insertion & deletion
 No memory wastage

10
 Data Structure & Algorithm NOTES by anees ahmad
14. Final Exam-Ready Summary 2. What is Sequential Searching?

 Linked list = dynamic linear structure Meaning

 Uses pointers for connection
 Better than arrays for dynamic data Sequential searching means checking each
 Types: singly, doubly, circular element one by one in sequence until the
 Supports efficient insertion & deletion required element is found or the list ends.

SEARCHING This is also called Linear Search.

(Data Structures & Algorithms – Detailed Exam

Notes) 3. Searching Algorithms (Overview)

Common searching algorithms used in DSA:

1. What is Searching?
1. Linear (Sequential) Search
Definition (For Exams) 2. Binary Search
3. Binary Search Tree (BST) Search
Searching is the process of locating a particular
element (called key or target) in a collection of
data and determining whether it exists or not. 4. Linear Search (Sequential Search)
If the element exists → its position is returned
Definition
If it does not exist → search fails
Linear search is a searching algorithm in which
elements are compared sequentially starting
from the first element until the desired element is
Why Searching is Important? found or the list is fully traversed.
 Used in databases
 Used in file systems
 Used in search engines
How Linear Search Works?
 Used in data retrieval operations
 Almost every program uses searching in
1. Start from first element
some form
2. Compare current element with key
3. If equal → stop (success)
4. Else → move to next element
5. Repeat until end of list
Real-Life Analogy

 Finding a roll number in class list

 Searching a contact in mobile
Example
 Finding a book in library
Array:
[12, 45, 23, 89, 34]
Key: 23

11
 Data Structure & Algorithm NOTES by anees ahmad
 Steps:  cout << "Element found at
 12 ❌ index " << pos;
 45 ❌  else
 23 ✅ (found)  cout << "Element not
found";

Characteristics  return 0;
 }
 Works on sorted and unsorted data
 Simple algorithm
 Slow for large data Advantages

 Easy to implement
 No sorting required
Time Complexity Explanation  Useful for small datasets

 Best Case: O(1) Disadvantages

(Element found at first position)
 Worst Case: O(n)  Inefficient for large datasets
(Element at last position or not present)  More comparisons
 Average Case: O(n)

5. Binary Search
Linear Search Code (C++)
Definition
 #include <iostream>
 using namespace std; Binary search is an efficient searching algorithm
 that works by repeatedly dividing a sorted list
 int linearSearch(int arr[], int n, into two halves and searching in the appropriate
int key) { half.
 for(int i = 0; i < n; i++) {
 if(arr[i] == key)
 return i;
 } Mandatory Condition
 return -1;
 } ⚠️Binary Search only works on SORTED data

 int main() {
 int arr[] = {12, 45, 23, 89,
34}; Working of Binary Search
 int key = 23;
 1. Find middle element
 int pos = linearSearch(arr, 5, 2. Compare key with middle
key); 3. If equal → found

4. If key < middle → search left half
 if(pos != -1)
5. If key > middle → search right half
6. Repeat until found or search space ends

12
 Data Structure & Algorithm NOTES by anees ahmad
 low = mid + 1;
 else
Example  high = mid - 1;
 }
Sorted Array:  return -1;
[10, 20, 30, 40, 50]  }
Key: 30 
 int main() {
 Steps:  int arr[] = {10, 20, 30, 40,
 Middle = 30 → Found 50};
 int key = 30;

Real-World Analogy  int pos = binarySearch(arr, 5,
key);
Dictionary search: 
 if(pos != -1)
 Open middle page  cout << "Element found at
 Decide left or right index " << pos;
 Repeat until word is found  else
 cout << "Element not
found";

Time Complexity Explanation  return 0;
 }
 Best Case: O(1)
 Worst Case: O(log n)
 Average Case: O(log n) Advantages
Binary search is much faster than linear search.  Very fast
 Efficient for large datasets

Disadvantages
Binary Search Code (C++)
 Data must be sorted
 #include <iostream>  Sorting takes extra time
 using namespace std;

 int binarySearch(int arr[], int n,
int key) { 6. Binary Search Tree (BST) Searching
 int low = 0, high = n - 1;
 Definition
 while(low <= high) {
 int mid = (low + high) / A Binary Search Tree is a tree data structure
2; where:

 if(arr[mid] == key)  Left child contains smaller values
 return mid;  Right child contains larger values
 else if(arr[mid] < key)

13
 Data Structure & Algorithm NOTES by anees ahmad
Feature Linear Search Binary Search BST Search

Speed Slow Fast Fast

How Searching Works in BST?
Complexity O(n) O(log n) O(log n)
1. Start from root
2. Compare key with root Memory Low Low Higher
3. Move left or right accordingly
4. Repeat until found or NULL Large sorted Dynamic
Best Use Small data
data data

BST Search Code (C++) 8. Which Searching Algorithm is Best?

 struct Node { Answer (Perfect Exam Statement)

 int data;
 Node* left; There is no single best searching algorithm. The
 Node* right; best algorithm depends on:
 };
  Data size
 Node* search(Node* root, int key)  Data order
{  Data structure
 if(root == NULL || root->data
== key)
 return root;
 Best Choice Summary
 if(key < root->data)
 return search(root->left,  Linear Search: Small or unsorted data
key);  Binary Search: Large sorted data
 else  BST Search: Dynamic data with frequent
 return search(root->right, insertion/deletion
key);
 }

9. Final Revision Points (Write in Exam

Time Complexity Conclusion)

 Average Case: O(log n)  Searching finds required data

 Worst Case: O(n) (skewed tree)  Linear search is simple but slow
 Binary search is fast but needs sorted data
 BST search is efficient for dynamic datasets
 Algorithm selection depends on situation
7. Comparison of Searching
Algorithms (Very Important) SORTING
Feature Linear Search Binary Search BST Search
(Complete & Detailed DSA Exam Notes)
Tree
Data Order Any Sorted only
structure

14
 Data Structure & Algorithm NOTES by anees ahmad
1. What is Sorting? o Searching time reduces significantly
2. Better Data Organization
o Data becomes meaningful and
Exam-Oriented Definition
readable
Sorting is the process of arranging data elements 3. Faster Data Processing
o Finding min, max, median becomes
in a specific logical order (ascending or
descending) based on one or more key values to easy
make data processing efficient. 4. Used in Databases
o SQL queries use sorting internally
5. Used in Real Systems
o Operating systems
o File systems
Explanation
o Search engines

In sorting, elements are compared with each other

and placed in a proper order.
Sorting does not change the data, it only changes
the arrangement of data. Advantages of Sorting

 Reduces computational complexity

 Improves performance of algorithms
Example  Helps in duplicate detection
 Makes reporting easier
 Unsorted list:
 72, 15, 98, 43, 10
 Sorted (Ascending): 3. Classification of Sorting Algorithms
 10, 15, 43, 72, 98
 Sorted (Descending): Sorting algorithms can be classified based on:
 98, 72, 43, 15, 10
(a) Comparison Based Sorting
Real-World Analogies  Bubble Sort
 Selection Sort
 Arranging files alphabetically in a cabinet  Insertion Sort
 Sorting exam results from highest to lowest  Quick Sort
 Arranging books by price in a shop
(b) Based on Memory Usage

2. Why Sorting is Needed in DSA?  In-place sorting (Bubble, Selection,

Insertion)
 Not in-place sorting
Importance / Need of Sorting

Sorting is a fundamental operation in data

structures because: 4. Bubble Sort (Detailed)

1. Efficient Searching Definition

o Binary Search works only on sorted
data

15
 Data Structure & Algorithm NOTES by anees ahmad
Bubble Sort is a simple comparison-based Disadvantages
sorting algorithm that repeatedly compares
adjacent elements and swaps them if they are in  Inefficient for large data
incorrect order until the list is sorted.  Too many comparisons

Working Principle 5. Selection Sort (Detailed)

 Adjacent elements are compared Definition

 Larger element moves to the end
 After each pass, one element is fixed Selection Sort repeatedly selects the smallest
element from the unsorted part and places it at
the correct position.

Step-by-Step Example

 Array: Working Principle

 5, 1, 4, 2
 Pass 1:  Find minimum element
 1, 5, 2, 4  Swap with first position
 Pass 2:  Repeat for remaining elements
 1, 2, 4, 5

Analogy Example

Like air bubbles rising upward in water —  29, 10, 14, 37, 13
heavier elements move to the end.  After first pass:
 10, 29, 14, 37, 13

Time Complexity Analogy

 Best Case: O(n) (already sorted) Selecting the shortest person and placing them first
 Average Case: O(n²) in a line.
 Worst Case: O(n²)

Space Complexity
Complexity
 O(1) (in-place)
 Best: O(n²)
 Average: O(n²)
 Worst: O(n²)
Advantages  Space: O(1)

 Simple
 Easy to implement

16
 Data Structure & Algorithm NOTES by anees ahmad
Advantages  Average: O(n²)
 Worst: O(n²)
 Minimum number of swaps  Space: O(1)
 Simple logic

Disadvantages
Advantages
 Still slow
 Not stable  Fast for small datasets
 Stable
 Adaptive

6. Insertion Sort (Detailed) Disadvantages

Definition  Inefficient for large data

Insertion Sort sorts the array by inserting each

element into its correct position in a sorted part
of the array. 7. Quick Sort (Detailed)

Definition

Working Principle Quick Sort is a divide-and-conquer algorithm

that selects a pivot and partitions the array such
 Divide array into sorted & unsorted part that smaller elements go left and larger go right.
 Pick element from unsorted part
 Insert into correct position

Working Principle

Example 1. Choose a pivot

2. Partition array
 8, 3, 5, 2 3. Recursively sort subarrays
 Steps:
 3, 8, 5, 2
 3, 5, 8, 2
 2, 3, 5, 8 Example

 10, 7, 8, 9, 1, 5
Analogy  Pivot = 5
 Result:
Sorting cards in hand while playing cards.  1 | 5 | 7, 8, 9, 10

Analogy
Complexity
Teacher divides class into short students and tall
 Best: O(n) (nearly sorted) students, then sorts each group.

17
 Data Structure & Algorithm NOTES by anees ahmad
 Memory availability

Complexity

 Best: O(n log n) Best Use Summary

 Average: O(n log n)
 Worst: O(n²)  Small data → Insertion Sort
 Space: O(log n)  Nearly sorted → Insertion Sort
 Large data → Quick Sort
 Learning purpose → Bubble Sort

Advantages
10. Final Exam Conclusion
 Very fast
 Widely used
Sorting is a fundamental operation in DSA that
improves efficiency, searching speed, and data
Disadvantages organization. Various algorithms are available, each
suitable for different conditions.
 Worst case exists
 Not stable
MERGE SORT
(Complete & Detailed Exam Notes)
8. Comparison Table (VERY
IMPORTANT)
Suitable
Algorithm Best Average Worst Space Stable
For 1. What is Merge Sort?

Bubble O(n) O(n²) O(n²) O(1) Yes Learning Exam-Oriented Definition

Selection O(n²) O(n²) O(n²) O(1) No Small data
Merge Sort is a divide-and-conquer sorting
Nearly algorithm that divides the array into smaller
Insertion O(n) O(n²) O(n²) O(1) Yes
sorted subarrays, sorts them individually, and then
merges them to produce a sorted array.
O(n O(n log
Quick O(n²) O(log n) No Large data
log n) n)

2. Basic Idea / Concept of Merge Sort

9. Which Sorting Algorithm is Best?
Merge Sort works in three main steps:
Exam Answer: 1. Divide the array into two halves
2. Conquer by recursively sorting each half
No single sorting algorithm is best for all
3. Merge the sorted halves into one sorted
situations.
array
The choice depends on:
This process continues until each subarray contains
 Size of input
only one element.
 Nature of data

18
 Data Structure & Algorithm NOTES by anees ahmad
 3, 9, 10, 27, 38, 43, 82

Key Point for Exam 5. Characteristics of Merge Sort

👉 Merge Sort does not sort in-place (it needs extra  Uses divide and conquer
memory).  Always gives same time complexity
 Suitable for large datasets
 Stable sorting algorithm
3. Real-Life Analogy

Imagine you have a big pile of exam papers: 6. Time & Space Complexity (VERY
IMPORTANT)
1. Split them into smaller piles
2. Sort each small pile
3. Merge the sorted piles together Time Complexity

That’s exactly how Merge Sort works. Case Complexity

Best Case O(n log n)

4. Working of Merge Sort (Step-by- Average Case O(n log n)

Step) Worst Case O(n log n)

Example
👉 Same in all cases (very important exam point)
 Array:
 38, 27, 43, 3, 9, 82, 10

Step 1: Divide Space Complexity

 [38, 27, 43, 3] [9, 82, 10]  O(n) (extra memory required)
 Keep dividing until:
 [38] [27] [43] [3] [9] [82] [10]
7. Advantages of Merge Sort
Step 2: Merge & Sort 1. Very efficient for large data
2. Guaranteed O(n log n) performance
 [27, 38] 3. Stable sorting algorithm
 [3, 43] 4. Works well with linked lists
 [9, 10]

Step 3: Final Merge 8. Disadvantages of Merge Sort

 [3, 27, 38, 43] 1. Requires extra memory

 [9, 10, 82] 2. Not in-place
 Final sorted array:

19
 Data Structure & Algorithm NOTES by anees ahmad
3. Slower for small datasets compared to  while (j < n2)
insertion sort  arr[k++] = R[j++];
 }

 void mergeSort(int arr[], int l,
9. Merge Sort Algorithm (Steps for int r) {
Exam)  if (l < r) {
 int m = (l + r) / 2;
1. Divide the array into halves  mergeSort(arr, l, m);
2. Recursively sort each half  mergeSort(arr, m + 1, r);
3. Merge sorted halves  merge(arr, l, m, r);
4. Repeat until sorted array is obtained  }
 }

 int main() {
10. Simple C++ Program for Merge
 int arr[] = {38, 27, 43, 3, 9,
Sort
82, 10};
 int n = 7;
(Easy & Exam-Friendly) 
 mergeSort(arr, 0, n - 1);
 #include <iostream>

 using namespace std;
 cout << "Sorted Array: ";

 for (int i = 0; i < n; i++)
 void merge(int arr[], int l, int
 cout << arr[i] << " ";
m, int r) {

 int i, j, k;
 return 0;
 int n1 = m - l + 1;
 }
 int n2 = r - m;

 int L[n1], R[n2]; 11. Updated Comparison Table
 (Including Merge Sort)
 for (i = 0; i < n1; i++) Suitable
 L[i] = arr[l + i]; Algorithm Best Average Worst Space Stable
For
 for (j = 0; j < n2; j++)
 R[j] = arr[m + 1 + j]; Bubble O(n) O(n²) O(n²) O(1) Yes Learning

 i = 0; j = 0; k = l; Selection O(n²) O(n²) O(n²) O(1) No Small data

Nearly
 while (i < n1 && j < n2) { Insertion O(n) O(n²) O(n²) O(1) Yes
sorted
 if (L[i] <= R[j])
 arr[k++] = L[i++]; O(n O(n log O(log
 else Quick O(n²) No Large data
log n) n) n)
 arr[k++] = R[j++];
 } O(n O(n log O(n Very large
Merge O(n) Yes
 log n) n) log n) data
 while (i < n1)
 arr[k++] = L[i++];


20
 Data Structure & Algorithm NOTES by anees ahmad
12. Quick Exam Question: Key Exam Points

Which is better: Merge Sort or Quick Sort?  Tree is connected

 Tree is acyclic
Exam Answer:  Only one path exists between any two
nodes
 Merge Sort → Guaranteed performance,
stable, needs extra memory
 Quick Sort → Faster in practice, less
memory, but worst case exists Real-World Analogies

 Family tree
 Company organizational chart
13. Final Conclusion (Write This!)  Computer folder system
Merge Sort is a powerful sorting algorithm that uses  HTML DOM structure
divide and conquer technique and guarantees O(n
log n) time complexity in all cases, making it
suitable for large datasets.
2. Basic Terminology of Trees (VERY
IMPORTANT)
TREE
1. Node
(Data Structures & Algorithms – Complete &
Detailed Exam Notes) A basic unit of a tree that contains:

 Data
 Links to other nodes
1. What is a Tree?

Exam-Oriented Definition
2. Root
A tree is a non-linear data structure that
represents data in a hierarchical form, consisting  The topmost node
of nodes connected by edges, where one node is  Has no parent
called the root and every node (except the root)  Only one root in a tree
has exactly one parent.

3. Parent Node
Explanation
A node that has one or more children
 Unlike arrays, stacks, and queues, a tree
does not store data linearly
 Data is organized in levels
 Relationship between nodes is parent–child 4. Child Node
 A tree has no cycles
A node that descends from another node

21
 Data Structure & Algorithm NOTES by anees ahmad
12. Height of Tree

5. Sibling Maximum number of edges from root to any leaf

Nodes having the same parent

13. Depth of Node

6. Leaf Node (External Node) Number of edges from root to that node

 Node with no children

 End point of a tree
14. Subtree

A tree formed by a node and all of its descendants

7. Internal Node

Node with at least one child

3. Properties of Tree (Exam-Relevant)

 A tree with n nodes has (n − 1) edges

 There is exactly one path between any two
8. Edge
nodes
 Tree is a connected acyclic graph
Connection between two nodes

4. Representation of Tree in Memory

9. Degree of a Node
(A) Linked Representation (Most Used)
Number of children of that node
Each node stores:

 Data
10. Degree of Tree  Pointer(s) to child nodes

Maximum degree of any node in the tree Example for Binary Tree:

 struct Node {
 int data;
11. Level of Node  Node* left;
 Node* right;
Distance from root  };

 Root is at level 0 or 1 (depends on

convention) Why Linked Representation?

 Dynamic size

22
 Data Structure & Algorithm NOTES by anees ahmad
 No memory wastage  Expression trees
 Efficient insertion & deletion  Searching
 Sorting

5. Classification / Types of Trees

6. Types of Binary Trees
5.1 General Tree
6.1 Full Binary Tree
Definition
 Every node has either 0 or 2 children
A tree in which a node can have any number of
children.

6.2 Complete Binary Tree

Example  All levels filled except possibly last
 Last level filled from left to right
 Folder structure
 Organization hierarchy

6.3 Perfect Binary Tree

Disadvantages  All internal nodes have 2 children
 All leaves at same level
 Complex traversal
 Difficult memory representation

6.4 Skewed Binary Tree

5.2 Binary Tree ⭐⭐⭐
 Each node has only one child
 Left-skewed or right-skewed
Definition

A binary tree is a tree in which each node can

have at most two children: left and right. 7. Binary Search Tree (BST) ⭐⭐⭐⭐⭐

Definition (VERY IMPORTANT)

Properties A Binary Search Tree is a binary tree in which
for each node:
 Maximum nodes at level L = 2ᴸ
 Maximum nodes in height h = 2ʰ⁺¹ − 1  Left subtree contains values less than the
node
 Right subtree contains values greater than
the node
Uses

23
 Data Structure & Algorithm NOTES by anees ahmad
Example (b) Preorder Traversal

 40 Root → Left → Right

 / \
 20 60 Used for:
 / \ / \
 10 30 50 70  Copying trees
 Prefix expression

Advantages

 Efficient searching (c) Postorder Traversal

 Sorted data access
Left → Right → Root

Used for:
Time Complexity (BST)
 Deleting tree
Operation Best Worst  Postfix expression

Search O(log n) O(n)

Insert O(log n) O(n) Example Tree

Delete O(log n) O(n)
 A
 / \
Worst case occurs when tree becomes skewed.  B C
 / \
 D E
Traversal Output
8. Tree Traversal (VERY IMPORTANT
EXAM TOPIC) Inorder DBEAC

Preorder ABDEC
Traversal means visiting each node exactly once.
Postorder DEBCA

8.1 Depth First Traversal (DFS)

8.2 Breadth First Traversal (BFS)

(a) Inorder Traversal Level Order Traversal

Left → Root → Right  Visits nodes level by level

 Uses Queue
👉 In BST, inorder gives sorted order

24
 Data Structure & Algorithm NOTES by anees ahmad
9. Operations on Tree 11. Disadvantages of Tree

 Complex implementation
1. Insertion  Extra memory for pointers
 Skewed trees reduce efficiency
 Insert node at correct position
 In BST → based on comparison
12. Applications of Trees

 File systems
2. Deletion (BST)  Database indexing (B-Trees, B+ Trees)
 Compiler syntax trees
Three cases:  Expression evaluation
 Decision trees
1. Leaf node  Artificial Intelligence
2. Node with one child
3. Node with two children (replace with
inorder successor)
13. Simple Binary Tree Program
(Exam-Friendly)
 #include <iostream>
3. Searching  using namespace std;

 Compare values  struct Node {
 Move left or right (BST)  int data;
 Node* left;
 Node* right;
 };
4. Traversal 
 Node* createNode(int val) {
 Inorder  Node* node = new Node();
 Preorder  node->data = val;
 Postorder  node->left = node->right =
 Level order
NULL;
 return node;
 }
10. Advantages of Tree 
 void inorder(Node* root) {
 Represents hierarchical data  if (root == NULL) return;
 Faster searching  inorder(root->left);
 Dynamic structure  cout << root->data << " ";
 Efficient data management  inorder(root->right);
 }

 int main() {
 Node* root = createNode(20);
 root->left = createNode(10);

25
 Data Structure & Algorithm NOTES by anees ahmad
 root->right = createNode(30);

 cout << "Inorder Traversal: ";
 inorder(root);

 return 0;
 }

14. Tree vs Linear Data Structures

(EXAM COMPARISON)
Feature Tree Array

Structure Non-linear Linear

Data Relation Hierarchical Sequential

Size Dynamic Fixed

Searching Faster Slower

15. Final Exam Conclusion (WRITE

THIS)

Trees are powerful non-linear data structures used

to represent hierarchical relationships efficiently.
Different types of trees and traversal techniques
make them suitable for complex applications in
computer science.

26