Unit Notes & Reference

STACK Array Representation & Implementation

A stack is a linear data structure that follows LIFO (Last In, First Out) order — the element added last is the first one removed. Think of a stack of plates: you place a new plate on top, and you also pick up the topmost plate first.

Array Representation

A stack can be implemented using a one-dimensional array stack[0...n-1] along with a variable top that always points to the index of the topmost element.

• top = -1 means the stack is empty.
• top = n - 1 means the stack is full (n = size of the array).

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

STACK Operations: Push & Pop

Push (Insert)

Adds a new element to the top of the stack. Before pushing, check for stack overflow (stack already full).

function push(stack, top, value):
    if top == MAX - 1:
        print "Stack Overflow"
        return
    top = top + 1
    stack[top] = value

Pop (Delete)

Removes and returns the topmost element. Before popping, check for stack underflow (stack already empty).

function pop(stack, top):
    if top == -1:
        print "Stack Underflow"
        return
    value = stack[top]
    top = top - 1
    return value

Worked Example

Let MAX = 5 and the stack starts empty (top = -1):

APPLICATION Infix → Prefix & Postfix Conversion

Stacks are used to convert human-readable infix expressions (e.g., A + B) into prefix (+ A B) or postfix (A B +) form, which computers evaluate more easily without needing parentheses or precedence rules at evaluation time.

Infix → Postfix Algorithm

function infixToPostfix(expression):
    initialize empty stack for operators
    initialize empty string "result"

    for each character ch in expression:
        if ch is an operand (letter/digit):
            append ch to result
        else if ch == '(':
            push ch onto stack
        else if ch == ')':
            while stack top != '(':
                pop operator, append to result
            pop the '(' and discard
        else: // ch is an operator
            while stack is not empty and
                  precedence(stack.top()) >= precedence(ch):
                pop operator, append to result
            push ch onto stack

    while stack is not empty:
        pop operator, append to result

    return result

Worked Example — Convert A + B * C to Postfix

Infix → Prefix (Shortcut Method)

1. Reverse the infix expression (swap every ( with ) and vice versa).
2. Convert the reversed expression to postfix using the algorithm above.
3. Reverse the resulting postfix string to get the prefix expression.

Example: A + B * C → reversed: C * B + A → postfix of reversed: C B * A + → reverse it: + A * B C (the prefix form).

APPLICATION Evaluating Postfix & Prefix Expressions

Evaluating Postfix Using a Stack

function evaluatePostfix(expression):
    initialize empty stack

    for each token in expression:
        if token is an operand:
            push token onto stack
        else: // token is an operator
            b = pop()
            a = pop()
            result = a (token) b   // e.g., a + b, a * b
            push result

    return pop()   // final answer

Worked Example — Evaluate 5 3 4 * +

Final result = 17, which matches the infix expression 5 + (3 * 4) = 17.

Evaluating Prefix Using a Stack

Scan the expression right to left. If you see an operand, push it. If you see an operator, pop two operands — the first pop is the left operand and the second pop is the right operand (order matters for subtraction and division).

function evaluatePrefix(expression):
    initialize empty stack

    for each token in expression, scanned right to left:
        if token is an operand:
            push token onto stack
        else:
            a = pop()   // left operand
            b = pop()   // right operand
            result = a (token) b
            push result

    return pop()

APPLICATION Other Applications of Stack

• Function call management: every function call is pushed onto the call stack; when the function returns, its frame is popped — this is exactly how recursion works internally.
• Balanced parentheses checking: push opening brackets, pop when a matching closing bracket appears; if the stack isn't empty (or a mismatch occurs) at the end, the expression is unbalanced.
• Undo/Redo in editors: each action is pushed onto an "undo stack"; pressing Ctrl+Z pops the most recent action.
• Browser back button: visited pages are pushed onto a stack; "Back" pops the most recently visited page.

STACK Recursion

Recursion is when a function calls itself, directly or indirectly, to solve smaller instances of the same problem. Every recursive call is pushed onto the system (call) stack; when a call returns, it is popped.

Two Essential Parts

• Base case: the condition that stops the recursion (prevents infinite calls).
• Recursive case: the function calling itself with a smaller/simpler input, moving toward the base case.

Student-Friendly Example — Factorial

function factorial(n):
    if n == 0:           // base case
        return 1
    return n * factorial(n - 1)   // recursive case

Tracing factorial(4) using the call stack:

factorial(4)
 → 4 * factorial(3)
       → 3 * factorial(2)
             → 2 * factorial(1)
                   → 1 * factorial(0)
                         → returns 1   (base case hit)
                   ← returns 1 * 1 = 1
             ← returns 2 * 1 = 2
       ← returns 3 * 2 = 6
 ← returns 4 * 6 = 24

Each call waits on the stack until the call above it returns — just like the stack of plates: the innermost call (factorial(0)) finishes first, just as the topmost plate is removed first.

STACK Towers of Hanoi Problem

Classic recursion example: move n disks from a source peg (A) to a destination peg (C), using an auxiliary peg (B), under these rules:

• Only one disk can be moved at a time.
• Only the topmost disk of any peg can be moved.
• A larger disk can never be placed on top of a smaller disk.

Recursive Idea

To move n disks from A to C (using B as auxiliary):

1. Move the top n - 1 disks from A to B (using C as auxiliary).
2. Move the largest (n-th) disk directly from A to C.
3. Move the n - 1 disks from B to C (using A as auxiliary).

function towerOfHanoi(n, source, auxiliary, destination):
    if n == 0:
        return
    towerOfHanoi(n - 1, source, destination, auxiliary)
    print "Move disk", n, "from", source, "to", destination
    towerOfHanoi(n - 1, auxiliary, source, destination)

Worked Example — 3 Disks (A → C, via B)

Move disk 1 from A to C
Move disk 2 from A to B
Move disk 1 from C to B
Move disk 3 from A to C
Move disk 1 from B to A
Move disk 2 from B to C
Move disk 1 from A to C

It takes exactly 7 moves for 3 disks — in general, the minimum number of moves required is 2ⁿ - 1.

Space is O(n) because the recursion depth (and hence the call stack height) is at most n at any point in time.

QUEUE Array Representation & Implementation

A queue is a linear data structure that follows FIFO (First In, First Out) order — the element added first is the first one removed. Think of a line of people waiting to buy movie tickets: whoever joined the line first gets served first.

Array Representation

A simple queue can be implemented using an array queue[0...n-1] with two pointers:

• front — index of the first element (next to be removed).
• rear — index of the last element (most recently added).

Initially, front = -1 and rear = -1 indicate an empty queue.

// Declaration
int queue[MAX];
int front = -1, rear = -1;

QUEUE Operations: Insert, Delete, Full & Empty

Insert (Enqueue)

function enqueue(queue, value):
    if rear == MAX - 1:
        print "Queue Full"
        return
    if front == -1:
        front = 0
    rear = rear + 1
    queue[rear] = value

Delete (Dequeue)

function dequeue(queue):
    if front == -1 or front > rear:
        print "Queue Empty"
        return
    value = queue[front]
    front = front + 1
    return value

Checking Full / Empty

• Empty: front == -1 (or front > rear after some dequeues).
• Full (simple/linear queue): rear == MAX - 1.

Worked Example

Let MAX = 5, queue starts empty:

QUEUE Circular Queue

A circular queue connects the last position of the array back to the first position, forming a logical circle. This reuses the empty slots left behind by dequeued elements, instead of wasting them like a simple queue does.

Key Formulas

front = (front + 1) mod MAX     // after dequeue
rear  = (rear + 1) mod MAX      // after enqueue

Full / Empty Conditions

• Empty: front == -1
• Full: (rear + 1) mod MAX == front

Worked Example — Circular Queue of size 5

Picture 5 slots arranged in a circle: 0 → 1 → 2 → 3 → 4 → back to 0.

Notice how F was placed back into slot 0 — the slot freed earlier by A — because rear = (4 + 1) mod 5 = 0. This is the "circular" part in action.

QUEUE Applications of Queues

• CPU/process scheduling: processes waiting for the CPU are held in a ready queue and served in the order they arrive (e.g., round-robin scheduling, which uses a circular queue).
• Printer/spooler queue: print jobs are queued and printed in the order they were submitted.
• Breadth-First Search (BFS): uses a queue to visit nodes of a graph or tree level by level.
• Handling requests on a single shared resource: e.g., customer service call centers, where calls are answered in the order received.
• Buffering data streams: e.g., keystrokes typed faster than they can be processed, or video streaming buffers.

LINKED LIST Singly Linked List: Representation & Implementation

A linked list is a linear data structure where each element (called a node) stores its data and a pointer/reference to the next node. Unlike arrays, the nodes are not stored in contiguous memory — they are scattered, and connected only through these pointers.

Node Structure

struct Node {
    int data;
    Node* next;     // pointer/address of the next node
};

Node* head = NULL;   // head points to the first node; NULL means empty list

A singly linked list means each node has only one link — pointing forward to the next node. You can only move forward, never backward.

Diagram

head
 |
 v
[10|next] -> [20|next] -> [30|next] -> NULL

Creating a Node

function createNode(value):
    newNode = allocate memory for Node
    newNode.data = value
    newNode.next = NULL
    return newNode

LINKED LIST Traversing & Searching

Traversal

Traversing means visiting every node in the list, one by one, starting from head and following next pointers until you reach NULL.

function traverse(head):
    current = head
    while current != NULL:
        print current.data
        current = current.next

Worked Example

Given the list 10 -> 20 -> 30 -> NULL:

Searching

To search for a value, traverse the list and compare each node's data with the target value. Stop as soon as a match is found (or you reach the end without a match).

function search(head, key):
    current = head
    position = 0
    while current != NULL:
        if current.data == key:
            return position    // found!
        current = current.next
        position = position + 1
    return -1    // not found

LINKED LIST Insertion & Deletion

Insertion at the Beginning

function insertAtBeginning(head, value):
    newNode = createNode(value)
    newNode.next = head
    head = newNode
    return head

Example: inserting 5 before 10 -> 20 -> NULL gives 5 -> 10 -> 20 -> NULL. Only the new node's pointer and head change — nothing needs to "shift", unlike an array.

Insertion at the End

function insertAtEnd(head, value):
    newNode = createNode(value)
    if head == NULL:
        return newNode
    current = head
    while current.next != NULL:
        current = current.next
    current.next = newNode
    return head

Insertion at a Given Position

function insertAtPosition(head, value, pos):
    if pos == 0:
        return insertAtBeginning(head, value)
    newNode = createNode(value)
    current = head
    for i from 0 to pos - 2:
        current = current.next
    newNode.next = current.next
    current.next = newNode
    return head

Deletion of a Node (by value)

function deleteNode(head, key):
    if head == NULL:
        return head
    if head.data == key:        // deleting the first node
        temp = head
        head = head.next
        free(temp)
        return head

    current = head
    while current.next != NULL and current.next.data != key:
        current = current.next

    if current.next != NULL:    // node found
        temp = current.next
        current.next = current.next.next
        free(temp)

    return head

Worked Example — Delete 20 from 10 → 20 → 30

Notice that node 20 is "skipped over" by simply changing one pointer — its memory is then freed. No elements need to be shifted, unlike deleting from the middle of an array.

LINKED LIST Doubly Linked List

A doubly linked list (DLL) is like a singly linked list, but each node has two pointers: one to the next node and one to the previous node. This lets you traverse the list in both directions.

Node Structure

struct Node {
    int data;
    Node* prev;     // pointer to previous node
    Node* next;     // pointer to next node
};

Diagram

NULL <- [10|prev|next] <-> [20|prev|next] <-> [30|prev|next] -> NULL
             ^
           head

Insertion at the Beginning

function insertAtBeginning(head, value):
    newNode = createNode(value)
    newNode.next = head
    newNode.prev = NULL
    if head != NULL:
        head.prev = newNode
    head = newNode
    return head

Deletion of a Node

function deleteNode(head, target):
    if target.prev != NULL:
        target.prev.next = target.next
    else:
        head = target.next      // deleting the first node

    if target.next != NULL:
        target.next.prev = target.prev

    free(target)
    return head

LINKED LIST Circular Doubly Linked List

A circular doubly linked list (CDLL) is a doubly linked list where the next pointer of the last node points back to the first node, and the prev pointer of the first node points to the last node — forming a closed loop in both directions.

Diagram

      +-----------------------------------------+
      |                                         |
      v                                         |
    [10|prev|next] <-> [20|prev|next] <-> [30|prev|next]
      ^                                         |
      |                                         |
      +-----------------------------------------+
                     (head points to node 10)

Key Differences from a Plain DLL

• No node's pointer is ever NULL — the list has no "true" start or end while traversing.
• To detect when traversal has completed one full loop, compare the current pointer back to head instead of checking for NULL.

Traversal (forward, full loop)

function traverse(head):
    if head == NULL:
        return
    current = head
    do:
        print current.data
        current = current.next
    while current != head

Insertion at the End

function insertAtEnd(head, value):
    newNode = createNode(value)
    if head == NULL:
        newNode.next = newNode
        newNode.prev = newNode
        return newNode

    last = head.prev          // last node, since head.prev always = last node
    last.next = newNode
    newNode.prev = last
    newNode.next = head
    head.prev = newNode
    return head

APPLICATION Implementing Priority Queue Using Linked List

A priority queue is a queue where each element has a priority, and the element with the highest priority is removed first — regardless of the order it was inserted (unlike a normal FIFO queue).

Idea Using a Linked List

Keep the linked list always sorted by priority. Every new node is inserted at the correct position so the list stays sorted — the head is always the highest-priority element, ready to be removed in O(1) time.

struct Node {
    int data;
    int priority;     // lower number = higher priority (1 = most urgent)
    Node* next;
};

Insertion (Keeping List Sorted by Priority)

function insert(head, value, priority):
    newNode = createNode(value, priority)

    if head == NULL or priority < head.priority:
        newNode.next = head
        return newNode          // becomes new head

    current = head
    while current.next != NULL and current.next.priority <= priority:
        current = current.next

    newNode.next = current.next
    current.next = newNode
    return head

Deletion (Always Remove the Head)

function deleteHighestPriority(head):
    if head == NULL:
        print "Queue Empty"
        return head
    temp = head
    head = head.next
    print "Removed:", temp.data
    free(temp)
    return head

Worked Example

Insert patients with priority 1 = most urgent:

Even though Anil was inserted first and Bala was inserted second, Bala (priority 1) is treated first because the list is always kept sorted by priority.

APPLICATION Polynomial Representation Using Linked Lists & Addition

A polynomial like 4x³ + 3x² + 2x + 5 can be represented as a linked list where each node stores one term: its coefficient and exponent. Terms are usually kept in decreasing order of exponent.

Node Structure

struct Node {
    int coefficient;
    int exponent;
    Node* next;
};

Diagram — Representing 4x³ + 3x² + 2x + 5

[coeff=4|exp=3] -> [coeff=3|exp=2] -> [coeff=2|exp=1] -> [coeff=5|exp=0] -> NULL

Adding Two Polynomials

To add two polynomials, walk through both lists together (similar to merging two sorted lists):

• If the exponents of the current nodes in both lists are equal, add their coefficients and create one node with that exponent.
• If one exponent is larger, copy that term as-is into the result and move forward only in that list.
• Continue until both lists are fully traversed.

function addPolynomials(poly1, poly2):
    result = NULL   // head of result list
    p1 = poly1
    p2 = poly2

    while p1 != NULL and p2 != NULL:
        if p1.exponent == p2.exponent:
            insertTerm(result, p1.coefficient + p2.coefficient, p1.exponent)
            p1 = p1.next
            p2 = p2.next
        else if p1.exponent > p2.exponent:
            insertTerm(result, p1.coefficient, p1.exponent)
            p1 = p1.next
        else:
            insertTerm(result, p2.coefficient, p2.exponent)
            p2 = p2.next

    // copy any remaining terms from whichever list isn't finished
    while p1 != NULL:
        insertTerm(result, p1.coefficient, p1.exponent)
        p1 = p1.next
    while p2 != NULL:
        insertTerm(result, p2.coefficient, p2.exponent)
        p2 = p2.next

    return result

Worked Example

Add P1 = 4x³ + 3x² + 5 and P2 = 5x² + 2x + 1:

Final result: 4x³ + 8x² + 2x + 6.

where m and n are the number of terms in each polynomial — every term is visited at most once.

TREE Basic Terminology

A tree is a hierarchical, non-linear data structure made up of nodes connected by edges, starting from a single root node — unlike stacks, queues, or linked lists, which are all linear.

Key Terms

• Root: the topmost node of the tree (has no parent).
• Parent: a node that has one or more nodes branching from it.
• Child: a node directly connected below a parent node.
• Leaf (terminal node): a node with no children.
• Siblings: nodes that share the same parent.
• Edge: the connection/link between a parent and a child.
• Degree of a node: the number of children it has.
• Depth/Level of a node: the number of edges from the root to that node (root is at level 0).
• Height of a tree: the number of edges on the longest path from the root to a leaf.
• Subtree: any node along with all of its descendants, treated as a smaller tree on its own.

Diagram

            A          ← root, level 0
          /   \
         B     C        ← level 1 (children of A, siblings of each other)
        / \     \
       D   E     F      ← level 2 (D, E, F are leaves)

Here, A is the root; B and C are children of A; D, E are leaves and children of B; B and C are siblings; the height of this tree is 2 (longest path A→B→D or A→B→E).

TREE Binary Trees — Full, Complete & Extended

A binary tree is a tree where every node has at most two children, usually called the left child and right child.

Full Binary Tree

Every node has either 0 or 2 children — never exactly 1.

        A
       / \
      B   C
     / \
    D   E

Here A and B have 2 children each, and C, D, E have 0 children — no node has just one child, so this is a full binary tree.

Complete Binary Tree

Every level is completely filled except possibly the last level, and the last level is filled from left to right with no gaps.

        A
       / \
      B   C
     / \  /
    D  E F

Level 2 (D, E, F) isn't full (only 3 of the possible 4 slots are used) but the filled nodes are packed to the left with no gaps — so this is a complete binary tree.

Extended Binary Tree (2-Tree)

An extended binary tree is formed by adding special external nodes (shown as squares) wherever a node is missing a child, so that every node ends up with exactly 0 or 2 children — turning any binary tree into a full binary tree. This is commonly used to represent expressions, where original nodes (circles) hold operators/operands and external nodes (squares) act as placeholders.

Original node with 1 child:        After extending:
      A                                  A
     /                                 / \
    B                                 B   □   (□ = added external node)

TREE Array & Linked Representation of Binary Trees

Array Representation

Store the tree in an array such that for a node at index i (1-based indexing):

• Left child is at index 2i
• Right child is at index 2i + 1
• Parent is at index ⌊i / 2⌋

Worked Example

        A (1)
       /      \
     B (2)    C (3)
     /  \
  D (4) E (5)

Check: left child of B (index 2) = index 4 = D ✓. Right child of B = index 5 = E ✓. Parent of D (index 4) = ⌊4/2⌋ = index 2 = B ✓.

Linked Representation

Each node is a separate object with pointers to its left and right children — this is the more common and flexible representation, especially for trees that aren't complete.

struct Node {
    int data;
    Node* left;
    Node* right;
};

TREE Traversing Binary Trees

There are three classic ways to visit every node of a binary tree, differing only in when the root is visited relative to its left and right subtrees.

Inorder (Left → Root → Right)

function inorder(node):
    if node == NULL: return
    inorder(node.left)
    print node.data
    inorder(node.right)

Preorder (Root → Left → Right)

function preorder(node):
    if node == NULL: return
    print node.data
    preorder(node.left)
    preorder(node.right)

Postorder (Left → Right → Root)

function postorder(node):
    if node == NULL: return
    postorder(node.left)
    postorder(node.right)
    print node.data

Worked Example

        A
       / \
      B   C
     / \
    D   E

TREE Threaded Binary Trees

In a normal binary tree, many left/ right pointers are NULL (every leaf has two NULL pointers). A threaded binary tree reuses these wasted NULL pointers as "threads" — shortcuts that point directly to the node's inorder predecessor or successor, so you can traverse the tree without recursion or a stack.

Single-Threaded vs Double-Threaded

• Single-threaded: only the NULL right pointers are replaced with a thread to the inorder successor.
• Double-threaded: NULL left pointers are also replaced with a thread to the inorder predecessor.

Diagram (Right-Threaded)

        B
       / \
      A   D
         / \
        C   E

Inorder sequence: A, B, C, D, E

Normal tree: A.right = NULL, C.right = NULL, E.right = NULL
Threaded:    A.right --thread--> B   (A's inorder successor)
             C.right --thread--> D   (C's inorder successor)
             E.right --thread--> NULL (E is the last node, no successor)

Each node also needs a boolean flag (often called rightThread) to tell whether its right pointer is a real child link or just a thread, so the traversal code knows the difference.

TREE Binary Search Tree (BST)

A binary search tree is a binary tree with one extra rule that makes searching fast:

• For every node, all values in its left subtree are smaller than the node's value.
• All values in its right subtree are greater than the node's value.
• Both the left and right subtrees must also be valid BSTs.

Example BST

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

Every left child is smaller and every right child is bigger than its parent — e.g., 20 and 40 are both less than 30, and 30 itself is less than 50.

Searching in a BST

function search(node, key):
    if node == NULL or node.data == key:
        return node
    if key < node.data:
        return search(node.left, key)
    else:
        return search(node.right, key)

Searching for 60: compare with 50 (60 > 50, go right) → compare with 70 (60 < 70, go left) → compare with 60 (match found!) — only 3 comparisons instead of checking all 7 nodes.

TREE Insertion & Deletion in BST

Insertion

function insert(node, key):
    if node == NULL:
        return createNode(key)
    if key < node.data:
        node.left = insert(node.left, key)
    else if key > node.data:
        node.right = insert(node.right, key)
    return node    // key already exists: do nothing

Worked Example — Insert 50, 30, 70, 20, 40

Final tree: 50 with left subtree (30 with children 20, 40) and right child 70.

Deletion — Three Cases

• Leaf node (no children): simply remove it.
• One child: replace the node with its only child.
• Two children: replace the node's value with its inorder successor (smallest value in the right subtree), then delete that successor node from the right subtree.

function deleteNode(node, key):
    if node == NULL: return NULL
    if key < node.data:
        node.left = deleteNode(node.left, key)
    else if key > node.data:
        node.right = deleteNode(node.right, key)
    else:
        if node.left == NULL:
            return node.right       // 0 or 1 child (right side)
        if node.right == NULL:
            return node.left        // 1 child (left side)
        // two children: find inorder successor (min of right subtree)
        successor = node.right
        while successor.left != NULL:
            successor = successor.left
        node.data = successor.data
        node.right = deleteNode(node.right, successor.data)
    return node

Worked Example — Delete 30 (Two Children)

Before:                  After:
        50                      50
       /  \                    /  \
     30    70                40    70
    /  \   /  \              /     /  \
  20   40 60   80           20   60    80

30 has two children (20, 40). Its inorder successor is 40 (smallest value in 30's right subtree). So 30's value is replaced with 40, and the original node holding 40 is removed.

TREE AVL Trees & Rotations

An AVL tree is a self-balancing BST. After every insertion or deletion, it automatically rebalances itself so the tree never becomes too skewed — this keeps search, insert, and delete operations at O(log n), even in the worst case.

Balance Factor

Balance Factor = height(left subtree) − height(right subtree)

An AVL tree requires every node's balance factor to be −1, 0, or +1. If any node's balance factor becomes −2 or +2 after an operation, a rotation is needed to restore balance.

The Four Rotation Cases

Single Right Rotation (LL Case)

Unbalanced (BF of 30 = +2):        After Right Rotation:
        30                                  20
       /                                  /    \
      20                                10      30
     /
    10

function rotateRight(y):
    x = y.left
    T = x.right
    x.right = y
    y.left = T
    return x      // x is the new root of this subtree

Single Left Rotation (RR Case)

Unbalanced (BF of 10 = -2):        After Left Rotation:
    10                                      20
      \                                   /    \
      20                                10      30
        \
        30

function rotateLeft(x):
    y = x.right
    T = y.left
    y.left = x
    x.right = T
    return y      // y is the new root of this subtree

LR and RL Cases

These need two rotations because a single rotation alone wouldn't fix the imbalance:

• LR: rotate the left child left first, then rotate the unbalanced node right.
• RL: rotate the right child right first, then rotate the unbalanced node left.

TREE Insertion & Deletion in AVL Trees

Insertion Algorithm

function insertAVL(node, key):
    if node == NULL:
        return createNode(key)
    if key < node.data:
        node.left = insertAVL(node.left, key)
    else if key > node.data:
        node.right = insertAVL(node.right, key)
    else:
        return node    // duplicates not allowed

    updateHeight(node)
    balance = getBalanceFactor(node)

    if balance > 1 and key < node.left.data:        // LL
        return rotateRight(node)
    if balance < -1 and key > node.right.data:       // RR
        return rotateLeft(node)
    if balance > 1 and key > node.left.data:         // LR
        node.left = rotateLeft(node.left)
        return rotateRight(node)
    if balance < -1 and key < node.right.data:       // RL
        node.right = rotateRight(node.right)
        return rotateLeft(node)

    return node    // already balanced

Worked Example — Insert 10, 20, 30

Insert 10:           Insert 20:           Insert 30 → triggers RR case:
  10                   10                    10                  20
                         \                     \                /  \
                         20                     20      →      10   30
                                                   \
                                                    30

After inserting 30, node 10 has balance factor −2 (right-heavy by 2), and 30 is in the right subtree of the right child — an RR case. A single left rotation on node 10 fixes it, producing the balanced tree shown above with 20 as the new root.

Deletion Algorithm

Deletion in an AVL tree works like normal BST deletion (the three cases: leaf, one child, two children), but after removing the node, you must walk back up the tree, update heights, and check the balance factor at every ancestor — applying the same four rotation cases (LL, RR, LR, RL) wherever an imbalance appears.

function deleteAVL(node, key):
    if node == NULL: return NULL

    if key < node.data:
        node.left = deleteAVL(node.left, key)
    else if key > node.data:
        node.right = deleteAVL(node.right, key)
    else:
        // standard BST deletion (leaf / one child / two children)
        if node.left == NULL: return node.right
        if node.right == NULL: return node.left
        successor = minValueNode(node.right)
        node.data = successor.data
        node.right = deleteAVL(node.right, successor.data)

    updateHeight(node)
    balance = getBalanceFactor(node)

    // re-check and rotate, just like in insertion
    if balance > 1 and getBalanceFactor(node.left) >= 0:
        return rotateRight(node)
    if balance > 1 and getBalanceFactor(node.left) < 0:
        node.left = rotateLeft(node.left)
        return rotateRight(node)
    if balance < -1 and getBalanceFactor(node.right) <= 0:
        return rotateLeft(node)
    if balance < -1 and getBalanceFactor(node.right) > 0:
        node.right = rotateRight(node.right)
        return rotateLeft(node)

    return node

GRAPH Terminology

A graph is a collection of vertices (nodes) connected by edges. Unlike a tree, a graph has no fixed root and can have cycles — any vertex can connect to any other vertex.

Key Terms

• Vertex (node): a single point in the graph, e.g., a city.
• Edge: a connection between two vertices, e.g., a road between two cities.
• Adjacent vertices: two vertices directly connected by an edge.
• Degree of a vertex: the number of edges connected to it.
• Path: a sequence of vertices where each consecutive pair is connected by an edge.
• Cycle: a path that starts and ends at the same vertex without repeating any edge.
• Connected graph: a graph where there is a path between every pair of vertices.
• Weight/Cost: a number attached to an edge, e.g., distance or travel time between two cities.

Diagram

    A ---- B
    |      |
    |      |
    D ---- C

Vertices: {A, B, C, D}
Edges: {(A,B), (A,D), (B,C), (C,D)}
Degree of A = 2 (connected to B and D)

GRAPH Types of Graphs

Directed vs Undirected — Diagram

Directed:                Undirected:
   A --> B                  A --- B
   ^     |                  |     |
   |     v                  |     |
   D <-- C                  D --- C

In the directed graph, you can go A→B but not B→A directly — you'd have to go B→C→D→A. In the undirected graph, every edge can be traveled in both directions.

GRAPH Representations: Adjacency Matrix & Adjacency List

Adjacency Matrix

A 2D array of size V × V (V = number of vertices), where matrix[i][j] = 1 (or the edge weight) if there's an edge from vertex i to vertex j, and 0 otherwise.

Graph:                Adjacency Matrix:
   A --- B                  A  B  C  D
   |     |              A [ 0  1  0  1 ]
   D --- C              B [ 1  0  1  0 ]
                         C [ 0  1  0  1 ]
                         D [ 1  0  1  0 ]

Adjacency List

Each vertex stores a list of the vertices it's directly connected to. This is more space-efficient for sparse graphs (graphs with relatively few edges).

A -> [B, D]
B -> [A, C]
C -> [B, D]
D -> [A, C]

GRAPH Path / Transitive Closure of a Graph

The transitive closure of a graph tells you, for every pair of vertices (i, j), whether any path exists from i to j — not just a direct edge, but also through any number of intermediate vertices.

Path Matrix Notation

The transitive closure is usually stored as a matrix P, where P[i][j] = 1 if there is a path (of any length, including through other vertices) from i to j, and 0 otherwise.

Graph (directed):          Adjacency Matrix:        Transitive Closure:
  A --> B                       A B C                    A B C
  B --> C                   A [0 1 0]                A [1 1 1]
                             B [0 0 1]                B [0 1 1]
                             C [0 0 0]                C [0 0 1]

Even though there's no direct edge A→C, a path A→B→C exists, so the transitive closure marks P[A][C] = 1. Warshall's algorithm (next topic) is the standard method used to compute this matrix.

GRAPH Warshall's Algorithm

Warshall's algorithm computes the transitive closure of a graph by systematically checking, for every pair of vertices, whether a path can be "completed" by routing through each other vertex in turn.

Core Idea

For every intermediate vertex k, and every pair (i, j): if there's already a path from i to k, and a path from k to j, then there must be a path from i to j — so set P[i][j] = 1.

function warshall(P, n):     // P = adjacency matrix, n = number of vertices
    for k from 1 to n:
        for i from 1 to n:
            for j from 1 to n:
                P[i][j] = P[i][j] OR (P[i][k] AND P[k][j])
    return P

Worked Example

Initial matrix P (from adjacency matrix):
        A B C
     A [0 1 0]
     B [0 0 1]
     C [0 0 0]

k = A: no incoming edges into A, so nothing changes via A.

k = B: check P[i][B] AND P[B][j] for all i, j.
       P[A][B]=1 and P[B][C]=1  →  set P[A][C] = 1

Result after k = B:
        A B C
     A [0 1 1]
     B [0 0 1]
     C [0 0 0]

k = C: no outgoing edges from C, so nothing further changes.

Final transitive closure:
        A B C
     A [0 1 1]
     B [0 0 1]
     C [0 0 0]

This confirms what we reasoned earlier: A can reach both B and C (via the path A→B→C), but B can only reach C, and C can't reach anyone.

GRAPH Graph Traversals: BFS & DFS

Breadth-First Search (BFS)

Visits vertices level by level — all neighbors of the starting vertex first, then their neighbors, and so on. Uses a queue.

function BFS(graph, start):
    visited = set()
    queue = empty queue
    queue.enqueue(start)
    visited.add(start)

    while queue is not empty:
        vertex = queue.dequeue()
        print vertex
        for each neighbor of vertex:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.enqueue(neighbor)

Depth-First Search (DFS)

Explores as far as possible along one branch before backtracking. Uses a stack (or recursion, which uses the call stack).

function DFS(graph, vertex, visited):
    visited.add(vertex)
    print vertex
    for each neighbor of vertex:
        if neighbor not in visited:
            DFS(graph, neighbor, visited)

Worked Example

      A
     / \
    B   C
    |   |
    D   E

GRAPH Dijkstra's Shortest Path Algorithm

Dijkstra's algorithm finds the shortest (minimum total weight) path from a single source vertex to every other vertex in a weighted graph (with non-negative weights).

Algorithm

function dijkstra(graph, source):
    distance[source] = 0
    distance[all other vertices] = infinity
    visited = empty set

    while there are unvisited vertices:
        u = unvisited vertex with the smallest distance[u]
        mark u as visited

        for each neighbor v of u:
            newDist = distance[u] + weight(u, v)
            if newDist < distance[v]:
                distance[v] = newDist

    return distance

Worked Example

        4
   A ------- B
   |         |
  1|         |2
   |         |
   C ------- D
        5

Edges: A-B = 4, A-C = 1, B-D = 2, C-D = 5. Find shortest paths from A.

Final shortest distances from A: B = 4 (direct), C = 1 (direct), D = 6 (via either A→C→D = 1+5 = 6, or A→B→D = 4+2 = 6 — both equal here).

GRAPH Connected Components & Spanning Trees

Connected Component

A connected component is a maximal group of vertices where every vertex can reach every other vertex within that group, but there's no path connecting it to vertices outside the group.

Graph with 2 connected components:

  A --- B        E --- F
  |     |
  C --- D

Component 1: {A, B, C, D}
Component 2: {E, F}

If a graph has only one connected component covering all its vertices, the graph is said to be connected.

Spanning Tree

A spanning tree of a connected graph is a subgraph that:

• Includes all the vertices of the original graph.
• Is a tree — connected, with no cycles.
• Uses exactly V - 1 edges (V = number of vertices).

Original Graph:              One possible Spanning Tree:
   A --- B                       A --- B
   |     |                             |
   |     |                             |
   D --- C                       D --- C

(4 vertices, 4 edges,         (4 vertices, 3 edges,
 has a cycle A-B-C-D-A)        no cycle — removed edge A-D)

A connected graph can have multiple different spanning trees — any V−1 edges that keep the graph connected without forming a cycle will work.

GRAPH Minimum Cost Spanning Trees

When edges have weights, a minimum cost spanning tree (MCST) is the spanning tree whose edges add up to the smallest possible total weight among all possible spanning trees.

Kruskal's Algorithm (Edge-based approach)

Sort all edges by weight; repeatedly add the smallest edge that does not create a cycle, until V−1 edges have been added.

function kruskal(graph):
    result = empty set of edges
    sort all edges by weight, ascending
    for each edge (u, v) in sorted order:
        if adding (u, v) does not form a cycle:
            add (u, v) to result
        if result has (V - 1) edges:
            break
    return result

Worked Example

Graph:
        4
   A ------- B
   |  \      |
  1|   2\    |3
   |     \   |
   C ------- D
        5

Edges sorted by weight: A-C(1), A-D(2), B-D(3), A-B(4), C-D(5).

Minimum cost spanning tree edges: A-C, A-D, B-D, with total cost = 1 + 2 + 3 = 6.

Prim's Algorithm (Vertex-based approach)

Start from any vertex; repeatedly add the cheapest edge that connects a vertex already in the tree to a vertex not yet in the tree, until all vertices are included.

function prim(graph, start):
    visited = {start}
    result = empty set of edges

    while visited does not include all vertices:
        find the minimum-weight edge (u, v) where u is in visited
        and v is not in visited
        add (u, v) to result
        add v to visited

    return result