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}$

Binary search is a searching algorithm that works only on a sorted list of elements. It repeatedly divides the search space in half by comparing the target element with the middle element of the current sublist, eliminating half of the r...

Big Oh notation is an asymptotic notation used to describe the upper bound on the growth rate of a function. In algorithm analysis, it tells us the worst-case rate at which the running time or space requirement of an algorithm grows as t...

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}$

Big Oh notation is an asymptotic notation used to describe the upper bound on the growth rate of a function. In algorithm analysis, it tells us the worst-case rate at which the running time or space requirement of an algorithm grows as t...

Binary search is a searching algorithm that works only on a sorted list of elements. It repeatedly divides the search space in half by comparing the target element with the middle element of the current sublist, eliminating half of the r...

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.

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

A stack is a linear data structure in which insertion and deletion of elements takes place at only one end, called the top. It follows the LIFO (Last In First Out) principle, meaning the last element inserted is the first one to be remov...

--- A circular linked list is a linked list in which the last node does not contain a NULL pointer. Instead, the link field of the last node points back to the first node of the list, forming a circle or loop. Every node in the list has ...

Binary Search Tree: Definition, Insertion and Deletion

Definition of Binary Search Tree (BST)

A Binary Search Tree (BST) is a binary tree that is either empty or in which every node contains a key (value) and satisfies the following conditions:

• All keys in the left sub-tree of the root are smaller than the key in the root node.
• All keys in the right sub-tree of the root are greater than the key in the root node.
• The left and right sub-trees of the root are again binary search trees (recursive definition).

Example:

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

Here, every left child < parent < right child.

Node Structure

Each node in a BST contains:

• A data/key field
• A pointer to the left child
• A pointer to the right child

C Program: BST Insertion and Deletion

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

/* ── Node structure ── */
struct Node {
    int data;
    struct Node *left;
    struct Node *right;
};

/* ── Helper: create a new node ── */
struct Node* createNode(int value) {
    struct Node *newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data  = value;
    newNode->left  = NULL;
    newNode->right = NULL;
    return newNode;
}

/* ════════════════════════════════
   INSERTION
   ════════════════════════════════
   Algorithm:
   1. If tree is empty, new node becomes root.
   2. If value < current node data, go LEFT.
   3. If value > current node data, go RIGHT.
   4. Repeat until NULL position found; insert there.
*/
struct Node* insert(struct Node *root, int value) {
    /* Base case: empty tree or reached insertion point */
    if (root == NULL) {
        return createNode(value);
    }

    if (value < root->data) {
        /* Insert in left sub-tree */
        root->left = insert(root->left, value);
    }
    else if (value > root->data) {
        /* Insert in right sub-tree */
        root->right = insert(root->right, value);
    }
    else {
        /* Duplicate keys are not inserted */
        printf("Value %d already exists in BST.\n", value);
    }

    return root;
}

/* ════════════════════════════════
   FIND MINIMUM NODE
   (Used during deletion)
   Returns the node with minimum key
   in a given sub-tree (leftmost node).
════════════════════════════════ */
struct Node* findMin(struct Node *root) {
    while (root->left != NULL) {
        root = root->left;
    }
    return root;
}

/* ════════════════════════════════
   DELETION
   ════════════════════════════════
   Three cases:
   Case 1: Node has NO child (leaf)
           --> Simply delete the node.

   Case 2: Node has ONE child
           --> Replace node with its child.

   Case 3: Node has TWO children
           --> Find in-order successor
               (smallest in right sub-tree).
           --> Copy successor's value to node.
           --> Delete the in-order successor.
*/
struct Node* deleteNode(struct Node *root, int value) {
    /* Base case: value not found */
    if (root == NULL) {
        printf("Value %d not found in BST.\n", value);
        return NULL;
    }

    if (value < root->data) {
        /* Value lies in left sub-tree */
        root->left = deleteNode(root->left, value);
    }
    else if (value > root->data) {
        /* Value lies in right sub-tree */
        root->right = deleteNode(root->right, value);
    }
    else {
        /* Node to be deleted is found */

        /* Case 1: Leaf node (no children) */
        if (root->left == NULL && root->right == NULL) {
            free(root);
            return NULL;
        }

        /* Case 2a: Only right child exists */
        else if (root->left == NULL) {
            struct Node *temp = root->right;
            free(root);
            return temp;
        }

        /* Case 2b: Only left child exists */
        else if (root->right == NULL) {
            struct Node *temp = root->left;
            free(root);
            return temp;
        }

        /* Case 3: Node has two children */
        else {
            /* Find in-order successor (min of right sub-tree) */
            struct Node *successor = findMin(root->right);

            /* Copy successor's value to current node */
            root->data = successor->data;

            /* Delete the in-order successor from right sub-tree */
            root->right = deleteNode(root->right, successor->data);
        }
    }

    return root;
}

/* ════════════════════════════════
   IN-ORDER TRAVERSAL (Left-Root-Right)
   Prints BST in sorted order
════════════════════════════════ */
void inorder(struct Node *root) {
    if (root != NULL) {
        inorder(root->left);
        printf("%d ", root->data);
        inorder(root->right);
    }
}

/* ════════════════════════════════
   MAIN FUNCTION
════════════════════════════════ */
int main() {
    struct Node *root = NULL;

    /* Inserting nodes */
    root = insert(root, 50);
    root = insert(root, 30);
    root = insert(root, 70);
    root = insert(root, 20);
    root = insert(root, 40);
    root = insert(root, 60);
    root = insert(root, 80);

    printf("Inorder traversal of BST: ");
    inorder(root);
    printf("\n");

    /* Delete a leaf node */
    root = deleteNode(root, 20);
    printf("After deleting 20: ");
    inorder(root);
    printf("\n");

    /* Delete a node with one child */
    root = deleteNode(root, 30);
    printf("After deleting 30: ");
    inorder(root);
    printf("\n");

    /* Delete a node with two children */
    root = deleteNode(root, 50);
    printf("After deleting 50: ");
    inorder(root);
    printf("\n");

    return 0;
}

Sample Output:

Inorder traversal of BST: 20 30 40 50 60 70 80
After deleting 20: 30 40 50 60 70 80
After deleting 30: 40 50 60 70 80
After deleting 50: 40 60 70 80

Explanation

Deleting 20 removes a leaf node directly. Deleting 30 removes a node with only one child (40), so 40 takes its place. Deleting 50 (the root, which now has two children 40 and 70) is handled by Case 3: the in-order successor, 60 (the smallest value in the right sub-tree rooted at 70), replaces 50's value, and the original node holding 60 is then removed from the right sub-tree. The in-order traversal after each deletion confirms that the BST property (left < parent < right at every node) is preserved throughout, which is why the printed sequence always stays sorted.

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.

The GCD (Greatest Common Divisor) of two numbers is based on the Euclidean Algorithm: - If b == 0, then GCD(a, b) = a - Otherwise, GCD(a, b) = GCD(b, a % b) This is a naturally recursive problem, and Recursion helps solve problems that a...

--- A Queue is a linear data structure that follows the FIFO (First In First Out) principle, meaning the element inserted first is the one removed first. It is analogous to a real-life queue (e.g., people standing in a line). A Queue ADT...

• Numbers to build max heap: ${10, 12, 53, 34, 23, 77, 59, 66, 5, 8}$ (10 elements) --- The pivot ends up in the first or last position after partitioning when the array is already sorted (ascending or descending), assuming the pivot i...

--- Tail recursion is a special form of recursion where the recursive call is the last operation performed in the function. That is, after the recursive call returns, there is nothing left to do in the calling function. Because of this p...