AVL Tree, Heap versus Tree, and Construction

What is an AVL tree?

An AVL tree, named after Adelson-Velsky and Landis who proposed it in 1962, is a self-balancing binary search tree. It keeps the ordering of a binary search tree, every key in the left subtree of a node being smaller than the node and every key in the right subtree larger, and adds a height condition at every node: the heights of the left and right subtrees may differ by at most one.

The condition is expressed through the balance factor

$$BF = h(\text{left subtree}) - h(\text{right subtree})$$

which must remain one of $-1$, $0$ or $+1$. If an insertion or deletion drives some balance factor to $+2$ or $-2$, the tree is repaired by a rotation, a local rearrangement of a few links that preserves the ordering while reducing the height. There are four cases, named by the two links leading from the unbalanced node towards the newly inserted key: LL is fixed by a single right rotation, RR by a single left rotation, LR by a left rotation followed by a right rotation, and RL by a right rotation followed by a left rotation. Because the height of an AVL tree on $n$ nodes stays $O(\log n)$, search, insertion and deletion all run in $O(\log n)$ time.

How a heap differs from a tree

The essential point is that a heap constrains only the relation between a parent and its children and therefore supports fast access to the minimum or maximum, while a binary search tree constrains the whole ordering left to right and therefore supports fast search for any key.

Constructing an AVL tree for 24, 12, 8, 15, 35, 30, 57, 40, 45, 78

Throughout, the height of a leaf is counted as 1 and the height of an empty subtree as 0, and

$$BF(x) = h(\text{left subtree of } x) - h(\text{right subtree of } x)$$

must stay in ${-1, 0, +1}$. After each insertion the balance factors are checked upward from the new node, so that the lowest unbalanced ancestor is the one rotated.

Insert 24

24

The first key becomes the root and $BF(24) = 0$.

Insert 12

Since $12 < 24$, the key goes to the left of the root.

  24
 /
12

$BF(24) = 1 - 0 = +1$, still within range.

Insert 8

Since $8 < 24$ and $8 < 12$, the key becomes the left child of 12.

    24
   /
  12
 /
8

Now $BF(12) = 1 - 0 = +1$ is fine, but $BF(24) = 2 - 0 = +2$, so 24 is unbalanced. From 24 the path to the new key goes left and then left again, an LL case, repaired by a single right rotation at 24.

   12
  /  \
 8    24

$BF(12) = 1 - 1 = 0$, so the tree is balanced again.

Insert 15

Since $15 > 12$ the key goes right to 24, and $15 < 24$ makes it the left child of 24.

   12
  /  \
 8    24
     /
    15

$BF(24) = 1 - 0 = +1$ and $BF(12) = 1 - 2 = -1$. No rotation is needed.

Insert 35

Since $35 > 12$ and $35 > 24$, the key becomes the right child of 24.

   12
  /  \
 8    24
     /  \
    15   35

$BF(24) = 1 - 1 = 0$ and $BF(12) = 1 - 2 = -1$. No rotation is needed.

Insert 30

Since $30 > 12$ the key goes right to 24, $30 > 24$ sends it right to 35, and $30 < 35$ makes it the left child of 35.

   12
  /  \
 8    24
     /  \
    15   35
        /
      30

Checking upward from the new node, $BF(35) = 1 - 0 = +1$ is fine and

$$BF(24) = h(15) - h(35) = 1 - 2 = -1$$

is also fine, so node 24 is balanced. The root, however, gives

$$BF(12) = h(8) - h(24) = 1 - 3 = -2$$

so the lowest unbalanced node is the root 12, not 24. From 12 the path to the new key goes right to 24 and then right again into the subtree rooted at 35, which is the RR case, repaired by a single left rotation at 12. In that rotation 24 moves up to become the root and hands its left child 15 to 12.

      24
     /  \
   12    35
  /  \   /
 8   15 30

Now $BF(12) = 1 - 1 = 0$, $BF(35) = 1 - 0 = +1$ and $BF(24) = 2 - 2 = 0$, so the tree is balanced.

Insert 57

Since $57 > 24$ and $57 > 35$, the key becomes the right child of 35.

      24
     /  \
   12    35
  /  \   / \
 8   15 30  57

$BF(35) = 1 - 1 = 0$ and $BF(24) = 2 - 2 = 0$. No rotation is needed.

Insert 40

Since $40 > 24$ the key goes right to 35, $40 > 35$ sends it right to 57, and $40 < 57$ makes it the left child of 57.

      24
     /  \
   12    35
  /  \   / \
 8   15 30  57
            /
          40

Here $BF(57) = 1 - 0 = +1$,

$$BF(35) = h(30) - h(57) = 1 - 2 = -1, \qquad BF(24) = h(12) - h(35) = 2 - 3 = -1$$

Every balance factor is in range, so no rotation is needed.

Insert 45

The key travels right to 35, right to 57, left to 40, and since $45 > 40$ it becomes the right child of 40.

      24
     /  \
   12    35
  /  \   / \
 8   15 30  57
            /
          40
            \
             45

Now $BF(40) = 0 - 1 = -1$ is fine, but

$$BF(57) = h(40) - 0 = 2 - 0 = +2$$

so 57 is the lowest unbalanced node. From 57 the path goes left to 40 and then right to 45, which is the LR case: first a left rotation at 40, then a right rotation at 57. The subtree rooted at 57 therefore becomes

    45
   /  \
 40    57

and the whole tree is

      24
     /  \
   12    35
  /  \   / \
 8   15 30  45
            / \
          40   57

with $BF(45) = 1 - 1 = 0$, $BF(35) = 1 - 2 = -1$ and $BF(24) = 2 - 3 = -1$, all in range.

Insert 78

The key travels right to 35, right to 45, right to 57, and becomes the right child of 57.

      24
     /  \
   12    35
  /  \   / \
 8   15 30  45
            / \
          40   57
                 \
                  78

Checking upward, $BF(57) = 0 - 1 = -1$ and $BF(45) = h(40) - h(57) = 1 - 2 = -1$ are fine, but

$$BF(35) = h(30) - h(45) = 1 - 3 = -2$$

so 35 is the lowest unbalanced node. From 35 the path goes right to 45 and then right again into the subtree rooted at 57, the RR case, repaired by a single left rotation at 35, in which 45 moves up and hands its left child 40 to 35.

      24
     /  \
   12    45
  /  \   /  \
 8   15 35   57
        / \    \
      30   40   78

Now $BF(35) = 1 - 1 = 0$, $BF(57) = 0 - 1 = -1$, $BF(45) = 2 - 2 = 0$ and $BF(24) = 2 - 3 = -1$, so the tree is balanced.

Final AVL tree

            24
         /      \
       12         45
      /  \       /   \
     8   15    35     57
              /  \      \
             30  40      78

The balance factors are $0$ at 8, 15, 30, 40 and 78, $0$ at 12, $0$ at 35, $-1$ at 57, $0$ at 45 and $-1$ at the root 24, every one of them inside ${-1, 0, +1}$, so the tree satisfies the AVL property. It stands four levels deep, the fewest possible for 10 nodes, and four rotations were needed in all: a right rotation at 24 (LL) when 8 was inserted, a left rotation at 12 (RR) when 30 was inserted, a left-right double rotation at 57 when 45 was inserted, and a left rotation at 35 (RR) when 78 was inserted.

List, Stack Using Linked List, and Circular Linked List

1. Definition of List

A list is a linear data structure that stores a collection of elements in a specific order. Each element in the list has a definite position (first, second, ..., last).

There are two main ways to implement a list:

• Contiguous List (Array-based): A large enough array is defined to hold all items. The first item is placed at position 0, and successive items occupy successive positions. Insertion and deletion can be done anywhere within the list.
• Linked List: Nodes are connected using pointers. Each node contains a data field (info) and a pointer field (next) that points to the next node. This is called a self-referential structure. The NULL value of the next field of the last node indicates the end of the list.

2. Implementing Stack Using Linked List

A stack is a linear data structure that follows the LIFO (Last In, First Out) principle. The two primary operations are:

• PUSH - Insert an element at the top
• POP - Remove an element from the top

In a linked list implementation, the head (start) pointer acts as the TOP of the stack.

Node Structure

struct node {
    int info;
    struct node *next;
};
typedef struct node NodeType;
NodeType *top = NULL;

PUSH Operation (Insert at top)

Algorithm PUSH(item):
1. Create a new node:
       newnode = (NodeType*) malloc(sizeof(NodeType))
2. If newnode == NULL then
       Print "Stack Overflow"
       Return
3. Set newnode->info = item
4. Set newnode->next = top
5. Set top = newnode
6. End.

Diagram:

Before PUSH(30):    top -> [20] -> [10] -> NULL
After  PUSH(30):    top -> [30] -> [20] -> [10] -> NULL

POP Operation (Delete from top)

Algorithm POP():
1. If top == NULL then
       Print "Stack Underflow"
       Return
2. Set temp = top
3. Set item = temp->info
4. Set top = top->next
5. Free(temp)
6. Return item
7. End.

Diagram:

Before POP():    top -> [30] -> [20] -> [10] -> NULL
After  POP():    top -> [20] -> [10] -> NULL   (30 is returned)

Advantages of Linked List over Array for Stack

3. Circular Linked List

Definition

A circular linked list is a list where the link field (next) of the last node points back to the very first node of the list, instead of pointing to NULL.

Circular linked lists can be used to help traverse the same list again and again if needed. A circular list is very similar to the linear list where the pointer of the last node points not to NULL but to the first node.

Diagram:

start
  |
  v
[10] -> [20] -> [30] -> [40]
  ^_______________________________|

C Representation

struct node {
    int info;
    struct node *next;
};
typedef struct node NodeType;
NodeType *start = NULL;
NodeType *last  = NULL;

Identifying the First Node

In a circular linked list, there are two methods to know if a node is the first node:

1. An external pointer start (or list) points to the first node.
2. A header node is placed as the first node of the circular list. The header node can be separated from others by:
   • Having a sentinel (dummy) value as the info part, OR
   • Having a dedicated flag variable to specify if the node is a header node.

Inserting a Node at the Beginning

Algorithm INSERT_BEGINNING(item):
1. newnode = (NodeType*) malloc(sizeof(NodeType))
2. If start == NULL then
       newnode->info = item
       newnode->next = newnode      // points to itself
       start = newnode
       last  = newnode
   End if
3. Else
       newnode->info  = item
       newnode->next  = start       // new node points to old first node
       start          = newnode     // update start to new node
       last->next     = newnode     // last node points to new first node
   End else
4. End.

Inserting a Node at the End

Algorithm INSERT_END(item):
1. newnode = (NodeType*) malloc(sizeof(NodeType))
2. If start == NULL then
       newnode->info = item
       newnode->next = newnode      // points to itself
       start = newnode
       last  = newnode
   End if
3. Else
       newnode->info  = item
       last->next     = newnode     // old last node points to new node
       last           = newnode     // update last pointer
       last->next     = start       // new last node points to start
   End else
4. End.

Advantages of Circular Linked List

• Any node can be a starting point; the entire list can be traversed from any node.
• Useful in round-robin scheduling, circular queues, and multiplayer games.
• No need to check for NULL while traversing (stop when you reach the start again).

Summary Table:

4. Conclusion

A list is an ordered collection of elements that can be held either contiguously in an array or as a chain of nodes joined by pointers. The linked representation is the natural one for a stack, because both PUSH and POP touch only the head of the chain and therefore run in O(1) time, while the stack grows and shrinks with the actual number of items instead of being limited by a fixed array size. A circular linked list changes only one pointer, the next of the last node, so that it addresses the first node, and that single change makes endless traversal from any starting node possible, which is why it is the structure behind round robin CPU scheduling and circular queues.

Circular Queue, Queue vs Stack, and Linear Queue Implementation

1. Definition of Circular Queue (2 marks)

A circular queue is a linear data structure that arranges data elements in a circular pattern, where the last element is connected back to the first element. It overcomes the major drawback of a linear queue (wastage of memory space).

In a circular queue:

• Insertion and deletion follow the FIFO (First-In-First-Out) principle.
• When the rear pointer reaches the end of the array, it wraps around to the beginning (index 0), reusing the freed spaces.
• This eliminates the problem where storage space at the beginning of the array is discarded and never used again (as happens in a linear queue).

Condition:

• Queue is empty when front == -1
• Queue is full when (rear + 1) % SIZE == front

2. Differences Between Queue and Stack (3 marks)

As stated in the notes: "The stack works as LIFO (last-in-first-out) technique but the queue works as FIFO technique (first-in-first-out) i.e., the first element inserted into the queue is the first element to be removed."

3. Program to Implement Linear Queue (5 marks)

A linear queue is an ordered collection where:

• Elements are inserted at the rear end.
• Elements are deleted from the front end.
• It follows the FIFO principle.

Note: The main problem with linear queue is that both rear and front indices are increased but never decreased, leading to wastage of storage space.

#include <stdio.h>
#include <stdlib.h>

#define SIZE 5   /* Maximum size of the queue */

int queue[SIZE];
int front = -1;
int rear  = -1;

/* ---- Function to check if queue is empty ---- */
int isEmpty()
{
    if (front == -1 || front > rear)
        return 1;
    return 0;
}

/* ---- Function to check if queue is full ---- */
int isFull()
{
    if (rear == SIZE - 1)
        return 1;
    return 0;
}

/* ---- Enqueue: Insert element at rear ---- */
void enqueue(int value)
{
    if (isFull())
    {
        printf("Queue Overflow! Cannot insert %d\n", value);
        return;
    }
    if (front == -1)
        front = 0;   /* First element being inserted */

    rear = rear + 1;
    queue[rear] = value;
    printf("Inserted: %d\n", value);
}

/* ---- Dequeue: Delete element from front ---- */
void dequeue()
{
    if (isEmpty())
    {
        printf("Queue Underflow! Queue is empty.\n");
        return;
    }
    printf("Deleted: %d\n", queue[front]);
    front = front + 1;

    /* Reset queue when all elements are removed */
    if (front > rear)
    {
        front = -1;
        rear  = -1;
    }
}

/* ---- Display all elements in the queue ---- */
void display()
{
    int i;
    if (isEmpty())
    {
        printf("Queue is empty.\n");
        return;
    }
    printf("Queue elements (front to rear): ");
    for (i = front; i <= rear; i++)
    {
        printf("%d  ", queue[i]);
    }
    printf("\n");
}

/* ---- Main Function ---- */
int main()
{
    int choice, value;

    printf("=== Linear Queue Implementation ===\n");

    do {
        printf("\n1. Enqueue (Insert)");
        printf("\n2. Dequeue (Delete)");
        printf("\n3. Display");
        printf("\n4. Exit");
        printf("\nEnter your choice: ");
        scanf("%d", &choice);

        switch (choice)
        {
            case 1:
                printf("Enter value to insert: ");
                scanf("%d", &value);
                enqueue(value);
                break;
            case 2:
                dequeue();
                break;
            case 3:
                display();
                break;
            case 4:
                printf("Exiting...\n");
                break;
            default:
                printf("Invalid choice!\n");
        }
    } while (choice != 4);

    return 0;
}

Sample Output

=== Linear Queue Implementation ===

1. Enqueue (Insert)
2. Dequeue (Delete)
3. Display
4. Exit
Enter your choice: 1
Enter value to insert: 10
Inserted: 10

Enter your choice: 1
Enter value to insert: 20
Inserted: 20

Enter your choice: 1
Enter value to insert: 30
Inserted: 30

Enter your choice: 3
Queue elements (front to rear): 10  20  30

Enter your choice: 2
Deleted: 10

Enter your choice: 3
Queue elements (front to rear): 20  30

Enter your choice: 4
Exiting...

4. Limitation of This Linear Queue

Once rear reaches SIZE - 1, isFull() reports the queue as full even if elements have already been dequeued from the front and slots 0 to front-1 are sitting empty, because rear and front only ever move forward and are never wrapped back to the start of the array. This wasted space is exactly the drawback that the circular queue (Section 1) fixes, by wrapping rear and front around to index 0 with the modulo operation once the array end is reached, so the same allocated storage can be reused indefinitely instead of being abandoned after one pass through the array.

Infix to Postfix Conversion Using Stack

STEP 1 - EXTRACT (Given Data)

Infix expression: A+(((B-C)*(D-E)+F)/G$(H-I))

Note: The original problem text shows an apparent typo with unbalanced parentheses. Counting the brackets:

• Open parens: ( before ((, giving 4 opening: ( ( ( (
• Actually reading A+(((B-C)*(D-E)+F)/G$(H-I)) the balanced form has 4 opens and 4 closes.

I take the balanced expression: A+(((B-C)*(D-E)+F)/G$(H-I))

Operator precedence ($ = exponentiation, highest):

$ is right-associative; *, /, +, - are left-associative.

STEP 2 - SOLVE (Scan left to right)

Explanation of key steps:

• At the + after (D-E): top of stack (inside brackets) is *, which has higher precedence than +, so * is popped, then + is pushed.
• At final ): pop $ then / until matching (.
• At End: pop remaining +.

Final Postfix Expression

$$\boxed{A\ B\ C-D\ E-*\ F+G\ H\ I-$\ /\ +}$$

That is: ABC-DE-*F+GHI-$/+

Verification: evaluating the postfix from left to right, A B C - builds (B-C), D E - builds (D-E), the * multiplies them, F + adds F, then G H I - $ builds G raised to (H-I), the / divides the bracketed sum by it, and the final + adds A, which reproduces the original infix expression exactly. The stack is empty at the end and every opening parenthesis was matched by a closing one, so the conversion is complete and correct.

Application of Spanning Tree and MST Construction

Applications of Spanning Tree

Spanning trees have several important practical applications:

1. Network Design: Used in designing minimum cost communication networks, electrical grids, and computer networks where all nodes must be connected with minimum wiring/cabling cost.

2. Routing Algorithms: Network routing protocols (like OSPF, STP in Ethernet) use spanning trees to avoid loops and ensure packets reach every node.

3. Cluster Analysis: Used in machine learning and data mining to group similar data points.

4. Circuit Design: Used in designing electronic circuits to minimize the total wire length connecting components.

5. Transportation Networks: Used to find the minimum cost road/rail network connecting all cities.

Minimum Spanning Tree (MST) - Example with 8 Vertices and 11 Edges

Graph Definition

Consider a graph G = (V, E) with:

• Vertices: V = {A, B, C, D, E, F, G, H}
• Edges with weights (11 edges):

Constructing MST using Kruskal's Algorithm

Step 1: Sort all edges in non-decreasing order of weight:

Step 2: Select edges one by one, avoiding cycles:

At this point we have 7 edges connecting all 8 vertices -- MST is complete.

Total MST Cost = 2 + 2 + 3 + 3 + 4 + 5 + 5 = 24

MST Diagram

A
|  \
3    2
|      \
C ---- B
        |
        5
        |
        D
        |
        4
        |
        F
        |
        5
        |
        H
        |
        2
        |
        G
        |
        3
        |
        E

MST Edges:

A ---3--- C ---2--- B ---5--- D ---4--- F ---5--- H ---2--- G ---3--- E

Total Minimum Cost = 2 + 2 + 3 + 3 + 4 + 5 + 5 = 24

The MST contains exactly n - 1 = 7 edges for 8 vertices, which satisfies the spanning tree property.

Shell Sort: {82, 73, 12, 39, 26, 88, 2, 9, 60, 41}

Step 1 - Given Data

• $n = 10$
• Increment sequence chosen: $k = 5, 2, 1$ (standard $n/2$ halving)

Step 2 - Solve

Pass 1: Increment $k = 5$

Sub-files (elements 5 positions apart):

Array after Pass 1:

Pass 2: Increment $k = 2$

Sub-files (elements 2 positions apart):

• Even indices ${0,2,4,6,8}$: {82, 9, 26, 73, 60} $\rightarrow$ {9, 26, 60, 73, 82}
• Odd indices ${1,3,5,7,9}$: {2, 39, 88, 12, 41} $\rightarrow$ {2, 12, 39, 41, 88}

Interleave back:

Pass 3: Increment $k = 1$ (standard insertion sort)

Start: {9, 2, 26, 12, 60, 39, 73, 41, 82, 88}

• Insert 2: {2, 9, 26, 12, 60, 39, 73, 41, 82, 88}
• Insert 26: no change
• Insert 12: {2, 9, 12, 26, 60, 39, 73, 41, 82, 88}
• Insert 60: no change
• Insert 39: {2, 9, 12, 26, 39, 60, 73, 41, 82, 88}
• Insert 73: no change
• Insert 41: {2, 9, 12, 26, 39, 41, 60, 73, 82, 88}
• Insert 82: no change
• Insert 88: no change

Final Sorted Array

Result: ${2, 9, 12, 26, 39, 41, 60, 73, 82, 88}$

Hashing, Linear Probing, and Rehashing

What is Hashing?

Hashing is a technique used to map data (keys) to specific locations (indices) in a hash table using a hash function. The hash function converts a key into an index within the range of the table size.

General form:

h(x) = x % table_size

The main advantage of hashing is that it allows O(1) average time for insertion, deletion, and search operations.

Hash Collision

A collision occurs when two distinct keys produce the same hash value (i.e., map to the same index). Collision resolution is necessary for correct operation.

Linear Probing

Linear probing is an open addressing collision resolution technique. When a collision occurs at index h(x), the algorithm searches sequentially for the next empty slot in the table.

Formula:

h(x, i) = (h(x) + i) % table_size

where i = 1, 2, 3, ... is the probe number.

Disadvantage: Linear probing suffers from primary clustering -- a group of consecutive occupied slots forms, slowing down future insertions.

Example of Linear Probing

Insert keys: {89, 49, 18, 58} into a hash table of size 10.

Hash function: h(x) = x % 10

Final Hash Table:

Rehashing

Rehashing is a collision resolution technique where, upon collision, a new hash function is applied to the key to find another location.

Formula:

h_i(x) = (h(x) + i * h'(x)) % table_size

Or simply, a second independent hash function is used:

h2(x) = R - (x % R)

where R is a prime number smaller than the table size.

Rehashing is also performed when the load factor (ratio of filled slots to table size) becomes too high -- in that case, the table size is doubled and all keys are re-inserted using the new hash function.

Steps in Rehashing:

1. Apply the primary hash function h(x).
2. If collision occurs, apply a secondary hash function h2(x).
3. Probe at positions: (h(x) + i * h2(x)) % table_size for i = 1, 2, 3, ...

Example of Rehashing (Double Hashing)

Insert keys: {89, 49}, table size = 10, R = 7

• h(x) = x % 10
• h2(x) = 7 - (x % 7)

Final Table:

Summary

Node Insertion and Deletion at Specified Position in Doubly Linked List

Insertion at Specified Position in Doubly Linked List

In a doubly linked list, each node has three fields: prev, info, and next.

Algorithm

Algorithm: Insert a node at a specified position in a doubly linked list
Input: Position (pos), Data (val)

Steps:

1. Create a new node and set newnode->info = val
2. If head = NULL, then:
   • Set newnode->next = NULL
   • Set newnode->prev = NULL
   • Set head = newnode
   • Exit
3. If pos = 1 (insert at beginning), then:
   • Set newnode->next = head
   • Set newnode->prev = NULL
   • Set head->prev = newnode
   • Set head = newnode
   • Exit
4. Else, traverse to the specified position:
   • Set temp = head
   • Set count = 1
   • While count < pos - 1 and temp != NULL:
     • temp = temp->next
     • count = count + 1
   • End While
5. If temp = NULL, then print "Position out of range" and Exit
6. Set newnode->next = temp->next
7. Set newnode->prev = temp
8. If temp->next != NULL, then:
   • Set temp->next->prev = newnode
9. Set temp->next = newnode
10. End

Deletion at Specified Position in Doubly Linked List

Algorithm

Algorithm: Delete a node from a specified position in a doubly linked list
Input: Position (pos)

Steps:

1. If head = NULL, then print "Empty list" and Exit
2. Set temp = head
3. If pos = 1 (delete from beginning), then:
   • Set hold = head
   • Set head = head->next
   • If head != NULL, then set head->prev = NULL
   • Free (hold)
   • Exit
4. Else, traverse to the specified position:
   • Set count = 1
   • While count < pos and temp != NULL:
     • temp = temp->next
     • count = count + 1
   • End While
5. If temp = NULL, then print "Position out of range" and Exit
6. Set hold = temp
7. If temp->prev != NULL, then:
   • Set temp->prev->next = temp->next
8. If temp->next != NULL, then:
   • Set temp->next->prev = temp->prev
9. Free (hold)
10. End

Diagram Illustration

Before Insertion at position 2:

[NULL|10|-->]  <-->  [-->|20|-->]  <-->  [-->|30|NULL]

After Inserting 15 at position 2:

[NULL|10|-->] <--> [-->|15|-->] <--> [-->|20|-->] <--> [-->|30|NULL]

Key Point: In a doubly linked list, both the next pointer of the previous node and the prev pointer of the next node must be updated during insertion and deletion to maintain bidirectional linkage.

Short Notes

a. Breadth First Search (BFS) Traversal of Graph

Definition: BFS is one of the simplest methods of graph searching/traversal. It explores a graph level by level, visiting all neighbors of a vertex before moving to the next level.

Algorithm / Steps:

1. Choose some vertex arbitrarily as the root (starting vertex).
2. Visit the root and add all vertices and edges that are incident on the root. These newly added vertices form Level 1 of the BFS tree.
3. From the set of vertices at Level 1, find other vertices that are connected by edges to Level 1 vertices. These form Level 2.
4. Repeat the above step until all vertices are visited/added.
5. A queue data structure is used to keep track of vertices to be visited next.

Example:

Graph:
    A
   / \
  B   C
 / \
D   E

BFS Order: A -> B -> C -> D -> E

Key Features:

• Uses a Queue (FIFO)
• Visits vertices in order of their distance from the source
• Guarantees the shortest path in an unweighted graph

b. Tower of Hanoi (TOH)

Definition: Tower of Hanoi is a classic recursive problem that involves moving n disks from a source peg to a destination peg using an auxiliary (helper) peg, following specific rules.

Rules:

1. Only one disk can be moved at a time.
2. A disk can only be placed on top of a larger disk or on an empty peg.
3. Only the top disk of any peg can be moved.

Recursive Algorithm: To move n disks from Source (S) to Destination (D) using Auxiliary (A):

1. Move n-1 disks from S to A (using D as auxiliary)
2. Move the nth (largest) disk from S to D
3. Move n-1 disks from A to D (using S as auxiliary)

Example (n = 3 disks, S -> D using A):

Total moves = 2^n - 1 = 2^3 - 1 = 7 moves

Key Features:

• Classic example of recursion
• Minimum number of moves required = 2^n - 1
• Time Complexity: O(2^n)