Data Structures

1. Introduction to data structures

1.1 What is a data structure?

A data structure is a systematic way of organizing and storing data so it can be accessed and used efficiently. It has distinct characteristics that determine how data is arranged, manipulated, and retrieved.

1.2 Classification of data structures

Primitive data structures

Basic types supported directly by the machine / language.

Type	Role
Integer	Whole numbers (e.g. 5, -10)
Float / double	Decimal numbers (e.g. 3.14)
Character	Single letter, symbol, or digit
Boolean	true / false
Pointer	Holds the address of another variable

Non-primitive data structures

Derived from primitives; organize groups of data.

Structure	Idea
Array	Same type, contiguous memory, indexed access
Linked list	Nodes with data + link to next; flexible size
Stack	LIFO — push/pop at one end (“top”)
Queue	FIFO — enqueue at rear, dequeue at front

1.3 Characteristics

• Efficiency — cost of search, insert, delete
• Reusability — same abstraction usable across programs
• Abstraction — clean interface without exposing every implementation detail
• Flexibility — different problems suit different structures
• Memory management — logical layout affects space use

---

1.4 Advantages and disadvantages

Advantages	Disadvantages
Faster algorithms when structure matches the problem	Harder to design/implement (e.g. graphs, trees)
Easier to organize complex data	Extra memory (e.g. pointers in lists)
Reusable patterns (lists, stacks, …)	Trade-offs: good for one operation, worse for another
Scales to large datasets	Steep learning curve (algorithms + implementation)

---

1.5 Applications (by domain)

1. Operating systems — queues for scheduling; linked lists/trees for memory; trees/hash tables in file systems
2. Databases — B-trees, hash indexes; graphs for relationships and query planning
3. Networking — graphs for topology; shortest-path routing; queues for packets

---

2. Recursion

Recursion is a technique where a function calls itself directly or indirectly until a base case stops the process. It fits problems that decompose into smaller instances of the same problem (divide-and-conquer, trees, some math).

In C, each call is a fresh activation: parameters, locals, and return address live on the call stack until that call returns.

2.1 Syntax pattern (C)

returnType functionName(parameters) {
    if (base_case_condition) {
        // Base case: stop recursion
        return value;
    } else {
        // Recursive case: smaller/simpler subproblem
        return functionName(updated_parameters);
    }
}

• Base case — condition that ends recursion (prevents infinite calls).
• Recursive case — call with modified arguments moving toward the base case.

---

2.2 Characteristics

• Self-reference — the function appears in its own definition
• Base case required — must terminate
• Stack usage — each call waits on the stack until it returns
• Divide-and-conquer — split into subproblems

2.3 Advantages of recursion

• Matches recursive structures — trees, linked lists, and nested data are defined recursively; recursive code mirrors that structure and stays natural to read.
• Simplifies divide-and-conquer — break a problem into smaller identical subproblems with a clear base case; algorithms like mergesort and tree traversals are often shorter and clearer than iterative equivalents.

---

2.4 Types of recursion in C

Direct — the function calls itself.

void directRecursion(int n) {
    if (n > 0) {
        printf("%d ", n);
        directRecursion(n - 1);
    }
}

Recursive notation — a formula where each term depends on previous terms (e.g. F(n) = F(n-1) + F(n-2)).

Runtime stack — stores, for each active call: return value (if any), parameters, return address, and local variables.

---

2.5 Codes

Factorial

#include <stdio.h>
 
int fact(int n) {
    if (n <= 1)
        return 1;
 
    return n * fact(n - 1);
}
 
int main() {
    printf("Factorial = %d", fact(5));
    return 0;
}

GCD (Euclidean, recursive)

#include <stdio.h>
 
int gcd(int a, int b) {
    if (b == 0)
        return a;
 
    return gcd(b, a % b);
}
 
int main() {
    printf("GCD = %d", gcd(12, 18));
    return 0;
}

Fibonacci series

#include <stdio.h>
 
int fibo(int n) {
    if (n == 0)
        return 0;
 
    if (n == 1)
        return 1;
 
    return fibo(n - 1) + fibo(n - 2);
}
 
int main() {
    int i;
 
    for (i = 0; i < 6; i++)
        printf("%d ", fibo(i));
 
    return 0;
}

---

3. Dynamic memory allocation (C)

Memory can be requested and released at runtime from the heap (as opposed to fixed stack frames or static storage). The main stdlib tools: malloc, calloc, realloc, free.

3.1 Quick comparison: malloc vs calloc

	malloc()	calloc()
Meaning	Memory allocation	Contiguous allocation
Initialization	Uninitialized (garbage)	All bits zero
Arguments	Total size in bytes	Count × size per element
Speed	Usually faster (no zero-fill)	Slightly slower (zero-fill)

---

3.2 malloc — memory allocation

Allocates a block of uninitialized bytes. Returns a pointer to the block, or **NULL** on failure.

Syntax:

void *malloc(size_t size);

Example — array of 5 ints:

#include <stdio.h>
#include <stdlib.h>
 
int main() {
    int *arr = malloc(5 * sizeof(int));
    int i;
 
    for (i = 0; i < 5; i++)
        arr[i] = i + 1;
 
    for (i = 0; i < 5; i++)
        printf("%d ", arr[i]);
 
    free(arr);
 
    return 0;
}

---

3.3 calloc — contiguous allocation

Like malloc, but allocates for num elements of size bytes each and zero-initializes the whole block.

Syntax:

void *calloc(size_t num, size_t size);

Question: Write a C program to dynamically allocate memory using calloc() and release the memory using free()

#include <stdio.h>
#include <stdlib.h>
 
int main() {
    int *arr = calloc(5, sizeof(int));
    int i;
 
    for (i = 0; i < 5; i++)
        printf("%d ", arr[i]);
 
    free(arr);
 
    return 0;
}

3.4 realloc — resize

Resizes a block previously allocated with malloc / calloc / realloc. May move data to a new address; always use the returned pointer.

---

3.5 free — release

void free(void *ptr);

---

Module 2

4. Searching

Searching is the process of finding the location of a data element within a given collection. The search is either successful (element found) or unsuccessful (element not present).

---

4.1 Linear search

The simplest search: compare the target with each element from beginning to end. Also called sequential search.

Algorithm

Linear_Search(A, N, ele)
  A — array of N elements
  ele — element to find
  pos — position of ele (–1 if not found)

  Step 1: pos ← –1
  Step 2: For i ← 0 to N–1 Do
              If A[i] = ele Then
                  pos ← i
                  Go to Step 3
              End If
          End For
  Step 3: If pos ≥ 0 Then
              Print "Search successful, element found at position", pos
          Else
              Print "Search unsuccessful"
  Step 4: Exit

Program (C)

#include <stdio.h>
 
int main() {
    int a[] = {10, 20, 30, 40, 50};
    int ele = 30;
    int i;
 
    for (i = 0; i < 5; i++) {
        if (a[i] == ele) {
            printf("%d found at index %d", ele, i);
            return 0;
        }
    }
 
    printf("%d not found", ele);
 
    return 0;
}

Advantages and disadvantages

Advantages	Disadvantages
Simple and easy to implement	Slow for large datasets
Works on unsorted and sorted arrays	Must scan every element in worst case

---

4.2 Binary search

Binary search requires a sorted array. It compares the target with the middle element and eliminates half the remaining elements each step.

How it works:

1. Compute mid = (low + high) / 2.
2. If ele == A[mid] → found.
3. If ele < A[mid] → search the left half: set high = mid – 1.
4. If ele > A[mid] → search the right half: set low = mid + 1.
5. If low > high → element not present.

Algorithm

Binary_Search(A, N, ele)
  A — sorted array of N elements
  ele — element to find

  Step 1: Set low ← 0, high ← N–1, pos ← –1
  Step 2: While low ≤ high Do
              mid ← (low + high) / 2
              If ele = A[mid] Then
                  pos ← mid
                  Go to Step 3
              Else If ele < A[mid] Then
                  high ← mid – 1
              Else
                  low ← mid + 1
          End While
  Step 3: If pos ≥ 0 Then
              Print "Search successful, element found at position", pos
          Else
              Print "Search unsuccessful"
  Step 4: Exit

Program (C)

#include <stdio.h>
 
int main() {
    int arr[] = {1, 3, 5, 7, 9, 11, 13};
    int target = 11;
 
    int left = 0;
    int right = 6;
 
    while (left <= right) {
        int mid = (left + right) / 2;
 
        if (arr[mid] == target) {
            printf("Found at index %d\n", mid);
            return 0;
        }
 
        if (target > arr[mid]) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
 
    printf("Not found\n");
    return 0;
}

---

5. Sorting

Sorting is the process of arranging data elements in ascending or descending order.

Algorithm	Approach
Bubble sort	Swap adjacent
Selection sort	Find minimum
Insertion sort	Insert in place
Merge sort	Divide & conquer
Quick sort	Partition & pivot

---

5.1 Bubble sort

The simplest sort. Repeatedly swap adjacent elements that are out of order. After each pass the next-largest element “bubbles” to its final position.

• Each pass compares adjacent pairs and swaps if needed.
• After pass i, the i-th largest element is in place.
• Stops after N–1 passes (or earlier if no swaps occur).

Algorithm

Bubble_Sort(A[], N)
  Step 1: Start
  Step 2: Read N, then read A[0..N–1]
  Step 3: For i ← 0 to N–2 Do
              For j ← 0 to N–i–2 Do
                  If A[j] > A[j+1] Then
                      temp ← A[j]
                      A[j] ← A[j+1]
                      A[j+1] ← temp
                  End If
              End For
          End For
  Step 4: Print A[0..N–1]
  Step 5: Stop

Program (C)

#include <stdio.h>
 
int main(void) {
    int n, i, j, temp, a[10];
 
    printf("Enter the size of the List: ");
    scanf("%d", &n);
 
    printf("Enter %d integer values: ", n);
    for (i = 0; i < n; i++)
        scanf("%d", &a[i]);
 
    for (i = 0; i < n - 1; i++)
        for (j = 0; j < n - i - 1; j++)
            if (a[j] > a[j + 1]) {
                temp = a[j];
                a[j] = a[j + 1];
                a[j + 1] = temp;
            }
 
    printf("List after sorting is: ");
    for (i = 0; i < n; i++)
        printf("%d\t", a[i]);
 
    return 0;
}

---

5.2 Selection sort

Divides the array into a sorted part (left) and an unsorted part (right). On each pass, find the smallest element in the unsorted part and swap it into position.

1. Select the first unsorted element.
2. Compare it with every remaining element; track the minimum.
3. Swap the minimum into the current position.
4. Repeat for the next position until the entire array is sorted.

Algorithm

Selection_Sort(A[], N)
  Step 1: Start
  Step 2: Read N, then read A[0..N–1]
  Step 3: For i ← 0 to N–2 Do
              small ← A[i]
              pos ← i
              For j ← i+1 to N–1 Do
                  If A[j] < small Then
                      small ← A[j]
                      pos ← j
                  End If
              End For
              A[pos] ← A[i]
              A[i] ← small
          End For
  Step 4: Print A[0..N–1]
  Step 5: Stop

Program (C)

#include <stdio.h>
 
int main() {
    int a[] = {5, 2, 8, 1, 3};
    int i, j, min, temp;
 
    for (i = 0; i < 5; i++) {
        min = i;
 
        for (j = i + 1; j < 5; j++) {
            if (a[j] < a[min])
                min = j;
        }
 
        temp = a[i];
        a[i] = a[min];
        a[min] = temp;
    }
 
    for (i = 0; i < 5; i++)
        printf("%d ", a[i]);
 
    return 0;
}

---

5.3 Insertion sort

Works like sorting a hand of cards: pick each element and insert it into its correct position among the already-sorted elements to its left.

1. Assume the first element is already sorted.
2. Take the next element — compare it backward through the sorted portion.
3. Shift larger elements right; insert the element in its correct spot.
4. Repeat until the entire array is sorted.

Algorithm

Insertion_Sort(A, N)
  Step 1: For i ← 1 to N–1 Do
              j ← i
              While j ≥ 1 AND A[j] < A[j–1] Do
                  temp ← A[j]
                  A[j] ← A[j–1]
                  A[j–1] ← temp
                  j ← j – 1
              End While
          End For
  Step 2: Exit

Program (C)

#include <stdio.h>
 
int main() {
    int a[5] = {5, 2, 4, 1, 3};
    int i, j, key;
 
    for (i = 1; i < 5; i++) {
        key = a[i];
        j = i - 1;
 
        while (j >= 0 && a[j] > key) {
            a[j + 1] = a[j];
            j--;
        }
 
        a[j + 1] = key;
    }
 
    for (i = 0; i < 5; i++)
        printf("%d ", a[i]);
 
    return 0;
}

---

5.4 Merge sort

A divide-and-conquer algorithm: split the array into single-element sublists, then repeatedly merge adjacent sublists in sorted order until one sorted list remains.

Idea:

1. Divide the unsorted list into N sublists of 1 element each.
2. Merge adjacent pairs into sorted sublists of size 2 (N → N/2 lists).
3. Repeat until a single sorted list is obtained.
4. When merging, compare the front elements of both sublists — the smaller one goes into the result first.

Algorithm — MergeSort(A, low, high)

MergeSort(A, low, high)
  Step 1: If low < high Then
              mid ← (low + high) / 2
          Else
              Return
  Step 2: MergeSort(A, low, mid)
  Step 3: MergeSort(A, mid+1, high)
  Step 4: Merge(A, low, mid, high)
  Step 5: Return

Algorithm — Merge(A, low, mid, high)

Merge(A, low, mid, high)
  Step 1: i ← low, j ← mid+1, k ← low
  Step 2: While i ≤ mid AND j ≤ high Do
              If A[i] < A[j] Then
                  C[k] ← A[i];  i ← i+1;  k ← k+1
              Else
                  C[k] ← A[j];  j ← j+1;  k ← k+1
              End If
          End While
  Step 3: While i ≤ mid Do
              C[k] ← A[i];  i ← i+1;  k ← k+1
          End While
  Step 4: While j ≤ high Do
              C[k] ← A[j];  j ← j+1;  k ← k+1
          End While
  Step 5: For i ← low to high Do
              A[i] ← C[i]
          End For
  Step 6: Return

---

5.5 Quick sort

A divide-and-conquer sort that picks a pivot (here, the first element) and partitions the array so that everything left of the pivot is ≤ it and everything right is ≥ it. Then recursively sort each side.

How partitioning works:

1. Use two index variables: i starts at low + 1, j starts at high.
2. key = A[low] is the pivot.
3. Increment i while key ≥ A[i].
4. Decrement j while key < A[j].
5. If i < j, swap A[i] and A[j] and repeat.
6. When i ≥ j, swap A[low] with A[j] — now A[j] is in its final sorted position.
7. Recursively sort the left and right sub-arrays.

---

Module 3

---

1. Stack and Array-Based Implementation

A stack is a linear data structure where insertion and deletion happen from only one end called top.

It follows LIFO:

Last In, First Out

Example: In a stack of plates, the last plate placed is removed first.

Array Implementation

int stack[MAX];
int top = -1;

• stack[MAX] stores elements.
• top stores the index of the top element.
• top = -1 means the stack is empty.

Operations

Operation	Meaning	Condition Checked
push	Insert element	Overflow
pop	Delete top element	Underflow
peek	See top element	Empty stack
display	Show stack elements	Empty stack

Push

if (top == MAX - 1)
    printf("Stack Overflow");
else
    stack[++top] = item;

Pop

if (top == -1)
    printf("Stack Underflow");
else
    item = stack[top--];

Peek

if (top == -1)
    printf("Stack is Empty");
else
    printf("Top element = %d", stack[top]);

2. Queue and Types of Queues

A queue is a linear data structure where insertion happens at the rear and deletion happens at the front. It follows FIFO:

First In, First Out

Example: A line of people waiting for tickets.

Types of Queues

Type	Meaning	Use
Simple Queue	Normal queue with front and rear	Basic waiting line
Circular Queue	Last position connects to first position	Memory-efficient queue
Priority Queue	Element with higher priority is served first	Hospital emergency queue
Deque	Insertion and deletion at both ends	Browser history, undo-redo

---

3. Operations on Simple Queue

A simple queue performs operations using two ends: front and rear.

Main Operations

Operation	Meaning
enqueue	Insert element at rear
dequeue	Delete element from front
peek	Show front element
display	Show all elements

Example

Assume queue size is 3.

Operation	Queue
Enqueue 10	[10]
Enqueue 20	[10, 20]
Enqueue 30	[10, 20, 30]
Enqueue 40	Overflow
Dequeue	[20, 30]
Peek	20

Overflow and Underflow

• Overflow: Inserting into a full queue.
• Underflow: Deleting from an empty queue.

---

4. Difference Between Stack and Queue

Basis	Stack	Queue
Principle	LIFO	FIFO
Insertion	push	enqueue
Deletion	pop	dequeue
Ends used	One end, top	Two ends, front and rear
First deleted	Last inserted element	First inserted element
Example	Stack of plates	Ticket line

Example

Stack: Push 10, 20, 30 -> Pop gives 30
Queue: Enqueue 10, 20, 30 -> Dequeue gives 10

---

5. Binary Tree, BST, and Complete Binary Tree

Binary Tree

A binary tree is a tree where each node has at most two children: left child and right child.

    A
   / \
  B   C
 /
D

Binary Search Tree

A Binary Search Tree (BST) is a binary tree where:

• Left child is smaller than the parent.
• Right child is greater than the parent.

      50
     /  \
   30    70
  / \    /
20  40  60

Complete Binary Tree

A complete binary tree is a binary tree where all levels are full except possibly the last level, and the last level is filled from left to right.

      A
     / \
    B   C
   / \  /
  D  E F

---

6. Tree Terminologies

Consider this tree:

        A
      / | \
     B  C  D
    / \     |
   E   F    G

Term	Meaning	Example
Root Node	Topmost node	A
Degree of Node	Number of children of a node	Degree of A = 3
Degree of Tree	Maximum degree of any node	Degree of tree = 3
Terminal Node	Node with no children	C, E, F, G
Level	Position from root	A is level 0
Depth of Tree	Maximum level in tree	Depth = 2

---

7. Binary Search Tree Traversals

Example BST:

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

Traversal	Rule	Output
Inorder	Left, Root, Right	20, 30, 40, 50, 60, 70, 80
Preorder	Root, Left, Right	50, 30, 20, 40, 70, 60, 80
Postorder	Left, Right, Root	20, 40, 30, 60, 80, 70, 50
Level Order	Level by level	50, 30, 70, 20, 40, 60, 80

Inorder traversal of a BST gives sorted order.

---

8. Construct BST for Given Data

Data:

50, 30, 70, 20, 40, 60, 80, 90, 10, 20, 15

Rule:

• Smaller value goes left.
• Greater value goes right.
• Duplicate 20 is placed to the right of existing 20.

Insertion Trace

Value	Position
50	Root
30	Left of 50
70	Right of 50
20	Left of 30
40	Right of 30
60	Left of 70
80	Right of 70
90	Right of 80
10	Left of 20
20	Right of existing 20
15	Right of 10

Final BST

            50
          /    \
        30      70
       /  \    /  \
     20   40  60   80
    /  \            \
  10   20            90
    \
     15

---

1. Infix to Postfix and Evaluation

Given expression:

((3+3)*2/4 + (5^2/2+6))

Operator Priority

Operator	Priority
^	Highest
*, /	Medium
+, -	Lowest

Postfix Conversion

Token	Stack	Output
(	(
(	( (
3	( (	3
+	( ( +	3
3	( ( +	3 3
)	(	3 3 +
*	( *	3 3 +
2	( *	3 3 + 2
/	( /	3 3 + 2 *
4	( /	3 3 + 2 * 4
+	( +	3 3 + 2 * 4 /
(	( + (	3 3 + 2 * 4 /
5	( + (	3 3 + 2 * 4 / 5
^	( + ( ^	3 3 + 2 * 4 / 5
2	( + ( ^	3 3 + 2 * 4 / 5 2
/	( + ( /	3 3 + 2 * 4 / 5 2 ^
2	( + ( /	3 3 + 2 * 4 / 5 2 ^ 2
+	( + ( +	3 3 + 2 * 4 / 5 2 ^ 2 /
6	( + ( +	3 3 + 2 * 4 / 5 2 ^ 2 / 6
)	( +	3 3 + 2 * 4 / 5 2 ^ 2 / 6 +
)	Empty	3 3 + 2 * 4 / 5 2 ^ 2 / 6 + +

Final postfix expression:

3 3 + 2 * 4 / 5 2 ^ 2 / 6 + +

Postfix Evaluation

Token	Operation	Stack
3	Push	3
3	Push	3, 3
+	3 + 3 = 6	6
2	Push	6, 2
*	6 * 2 = 12	12
4	Push	12, 4
/	12 / 4 = 3	3
5	Push	3, 5
2	Push	3, 5, 2
^	5 ^ 2 = 25	3, 25
2	Push	3, 25, 2
/	25 / 2 = 12.5	3, 12.5
6	Push	3, 12.5, 6
+	12.5 + 6 = 18.5	3, 18.5
+	3 + 18.5 = 21.5	21.5

Final value:

21.5

---

2. Simple Queue Program and Circular Queue Limitation

C Program for Simple Queue

#include <stdio.h>
 
int q[5];
int front = -1, rear = -1;
 
void enqueue(int x) {
    if (front == -1)
        front = 0;
 
    q[++rear] = x;
}
 
void dequeue() {
    printf("Deleted: %d\n", q[front++]);
 
    if (front > rear)
        front = rear = -1;
}
 
void display() {
    int i;
 
    for (i = front; i <= rear; i++)
        printf("%d ", q[i]);
 
    printf("\n");
}
 
int main() {
    enqueue(10);
    enqueue(20);
    enqueue(30);
 
    display();
 
    dequeue();
 
    display();
 
    return 0;
}

Limitation of Simple Queue

In array-based simple queue, deleted spaces at the front cannot be reused.

Size = 5
Before deletion:
[10] [20] [30] [40] [50]
 front               rear
After deleting 10 and 20:
[  ] [  ] [30] [40] [50]
           front    rear

Now insertion is not possible because rear is at the last index, even though two spaces are empty.

Circular Queue Solution

Circular queue connects the last index back to the first index.

[60] [70] [30] [40] [50]
 rear      front

So, circular queue reuses empty spaces and avoids memory wastage.

---

3. Simple Queue Program and Types of Linked Lists

Use the same simple queue program shown in Question 2.

Types of Linked Lists

Type	Structure	Suitable Use
Singly Linked List	10 -> 20 -> NULL	Stack, simple list
Doubly Linked List	NULL <- 10 <-> 20 -> NULL	Music playlist, browser navigation
Circular Singly Linked List	Last node points to first	Round-robin scheduling
Circular Doubly Linked List	Both directions in circle	Advanced playlist, task scheduling

Diagrams

Singly: 10 -> 20 -> 30 -> NULL
Doubly: NULL <- 10 <-> 20 <-> 30 -> NULL
Circular Singly:
10 -> 20 -> 30
^           |
|___________|

---

4. Linked List: Insert at End, Delete First, Display

#include <stdio.h>
 
struct Node {
    int data;
    struct Node *next;
};
 
void display(struct Node *p) {
    while (p) {
        printf("%d -> ", p->data);
        p = p->next;
    }
    printf("NULL\n");
}
 
int main() {
    struct Node n3 = {30, NULL};
    struct Node n2 = {20, &n3};
    struct Node n1 = {10, &n2};
 
    struct Node *head = &n1;
    struct Node *temp;
 
    display(head);
 
    temp = head;
    printf("Deleted: %d\n", temp->data);
    head = head->next;
 
    display(head);
 
    return 0;
}

---

Linked List Operations

Operation	Meaning
Traversal	Visit every node
Insertion	Add a new node
Deletion	Remove a node
Searching	Find a value
Counting	Count total nodes
Reversing	Change link direction

---

6. Arrays vs Linked List and Count Nodes Program

Difference Between Arrays and Linked List

Basis	Array	Linked List
Memory	Continuous	Non-continuous
Size	Fixed	Dynamic
Access	Direct using index	Sequential
Insertion	Difficult	Easy
Deletion	Difficult	Easy
Extra memory	No pointer needed	Pointer needed

C Program to Count Nodes (or elements)

#include <stdio.h>
 
struct Node {
    int data;
    struct Node *next;
};
 
int countNodes(struct Node *p) {
    int count = 0;
 
    while (p) {
        count++;
        p = p->next;
    }
 
    return count;
}
 
int main() {
    struct Node n3 = {30, NULL};
    struct Node n2 = {20, &n3};
    struct Node n1 = {10, &n2};
 
    printf("%d", countNodes(&n1));
 
    return 0;
}

---

1. Playlist, Search in SLL, and Tree Traversals

Playlist Data Structure

For a playlist where the user can move forward and backward, use a doubly linked list.

NULL <- Song A <-> Song B <-> Song C -> NULL

Forward traversal:

Song A -> Song B -> Song C

Backward traversal:

Song C -> Song B -> Song A

Search in Singly Linked List

int search(struct Node *p, int key) {
    int pos = 1;
 
    while (p) {
        if (p->data == key)
            return pos;
 
        p = p->next;
        pos++;
    }
 
    return -1;
}

Tree Traversal Difference

Example tree:

        A
       / \
      B   C
     / \
    D   E

Traversal	Order	Output
Preorder	Root, Left, Right	A B D E C
Inorder	Left, Root, Right	D B E A C
Postorder	Left, Right, Root	D E B C A

---

BST from Inorder and Postorder

Given:

Inorder   : 10, 20, 30, 40, 50, 60, 70
Postorder : 10, 30, 20, 50, 70, 60, 40

In postorder, the last element is the root.

Root = 40

Left subtree from inorder:

10, 20, 30

Right subtree from inorder:

50, 60, 70

Final BST:

        40
       /  \
     20    60
    / \    / \
  10  30  50  70

Preorder traversal:

40, 20, 10, 30, 60, 50, 70

---

Employee IDs in BST

Example:

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

Searching for 60:

1. Compare with 50; 60 is greater, go right.
2. Compare with 70; 60 is smaller, go left.
3. 60 is found.

BST search is efficient because at every step we ignore one side of the tree.

Case	Time
Balanced BST	O(log n)
Skewed BST	O(n)

When BST Becomes Inefficient

If values are inserted in sorted order like 10, 20, 30, 40, the BST becomes skewed.

10
  \
   20
     \
      30
        \
         40

This works like a linked list, so searching becomes slow.

---

4. Queue Using Linked List and BST Construction

C Program for Queue Using Linked List

#include <stdio.h>
#include <stdlib.h>
 
struct Node {
    int data;
    struct Node *next;
};
 
struct Node *front = NULL, *rear = NULL;
 
void enqueue(int x) {
    struct Node *n = malloc(sizeof(struct Node));
 
    n->data = x;
    n->next = NULL;
 
    if (front == NULL)
        front = rear = n;
    else {
        rear->next = n;
        rear = n;
    }
}
 
void dequeue() {
    struct Node *temp = front;
 
    front = front->next;
    free(temp);
}
 
void display() {
    struct Node *p = front;
 
    while (p != NULL) {
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");
}
 
int main() {
    enqueue(10);
    enqueue(20);
    enqueue(30);
 
    display();
 
    dequeue();
 
    display();
}

BST Insertion Rule

• Smaller value goes to the left.
• Greater value goes to the right.
• Repeat until an empty position is found. Elements:

45, 20, 60, 10, 30, 50, 70

BST After Each Insertion

Insert 45:

45

Insert 20:

   45
  /
20

Insert 60:

   45
  /  \
20    60

Insert 10:

      45
     /  \
   20    60
  /
10

Insert 30:

      45
     /  \
   20    60
  /  \
10    30

Insert 50:

      45
     /  \
   20    60
  /  \   /
10   30 50

Insert 70:

      45
     /  \
   20    60
  /  \   / \
10   30 50 70

Final BST:

      45
     /  \
   20    60
  /  \   / \
10   30 50 70

From the tree:

• Root: A
• Left subtree: B → C with children D and E
• Right subtree: F → G with children H and I

Inorder Traversal (Left → Root → Right)

Sequence: D, C, E, B, A, F, H, G, I

Preorder Traversal (Root → Left → Right)

Sequence: A, B, C, D, E, F, G, H, I

Postorder Traversal (Left → Right → Root)

Sequence: D, E, C, B, H, I, G, F, A

The given binary tree is:

          1
        /   \
       7     9
      / \     \
     2   6     9
        / \   /
       5  11 5

Array Representation of Binary Tree

Using 1-based indexing:

• Root node is stored at index 1
• Left child of node at index i → 2i
• Right child of node at index i → 2i + 1

Index	Value
1	1
2	7
3	9
4	2
5	6
6	NULL
7	9
8	NULL
9	NULL
10	5
11	11
12	NULL
13	NULL
14	5
15	NULL

Final Array

[1, 7, 9, 2, 6, NULL, 9, NULL, NULL, 5, 11, NULL, NULL, 5, NULL]

(If using 0-based indexing, positions will shift accordingly.)