Data Structure and Algorithms

Definition of Asymptotic Notations

Asymptotic Notations are mathematical notations used to describe the limiting behavior and growth rate of an algorithm’s running time or memory usage as the input size ($n$) approaches infinity.

The three primary standard notations are:

1. Big-O Notation ($\mathcal{O}$): Represents the asymptotic upper bound (worst-case scenario).
   $$f(n) = \mathcal{O}(g(n)) \iff \exists\, c > 0, n_0 > 0 \text{ such that } 0 \le f(n) \le c \cdot g(n) \quad \forall n \ge n_0$$
2. Big-Omega Notation ($\Omega$): Represents the asymptotic lower bound (best-case scenario).
   $$f(n) = \Omega(g(n)) \iff \exists\, c > 0, n_0 > 0 \text{ such that } 0 \le c \cdot g(n) \le f(n) \quad \forall n \ge n_0$$
3. Big-Theta Notation ($\Theta$): Represents the asymptotically tight bound (average-case behavior where upper and lower bounds coincide).
   $$f(n) = \Theta(g(n)) \iff \exists\, c_1, c_2 > 0, n_0 > 0 \text{ such that } c_1 \cdot g(n) \le f(n) \le c_2 \cdot g(n) \quad \forall n \ge n_0$$

Doubly Linked List (DLL)

A Doubly Linked List is a linear data structure in which each node contains three fields:

1. prev: A pointer/reference to the preceding node (or NULL if it is the first node).
2. data: The actual value or payload stored in the node.
3. next: A pointer/reference to the succeeding node (or NULL if it is the last node).

   NULL <--- [prev | 10 | next] <===> [prev | 20 | next] <===> [prev | 30 | next] ---> NULL
                ^                                                 ^
                |                                                 |
              HEAD                                              TAIL

Key Advantage:

Enables bidirectional traversal ($O(1)$ predecessor and successor access) and efficient deletion given a node pointer without requiring list traversal from head.

Definition of Stack

A Stack is a linear, restricted data structure that follows the LIFO (Last In, First Out) principle: the element inserted last is the first one to be removed.

Core Operations:

• push(item): Inserts an element onto the top of the stack ($O(1)$).
• pop(): Removes and returns the top element ($O(1)$).
• peek() / top(): Returns the element at the top without removing it ($O(1)$).
• isEmpty(): Checks whether the stack has zero elements ($O(1)$).

Applications:

Function call execution stack, undo/redo mechanisms, expression evaluation (postfix/infix conversion), and syntax/parenthesis matching.

Priority Queue

A Priority Queue is an abstract data type (ADT) similar to a regular queue or stack, but where each element is associated with a priority value.

Operating Principles:

1. Elements with higher priority are served before elements with lower priority.
2. If two elements have the same priority, they are served according to their arrival order (FIFO).
3. Types:
   • Max-Priority Queue: The element with the highest numerical key/priority is dequeued first.
   • Min-Priority Queue: The element with the lowest numerical key is dequeued first.
4. Optimal Implementation: Implemented using a Binary Heap (Min-Heap or Max-Heap), providing $O(\log n)$ insertion and $O(\log n)$ extraction.

Tail Recursion

Tail Recursion is a special form of recursion where the recursive function call is the very last operation performed in the function execution path before returning. No pending computations (such as additions or multiplications) remain to be performed after the recursive call finishes.

Example:

// Non-tail recursive (multiplication pending after return)
int fact(int n) {
    if (n <= 1) return 1;
    return n * fact(n - 1);
}

// Tail recursive (accumulates result; nothing pending)
int factTail(int n, int accum = 1) {
    if (n <= 1) return accum;
    return factTail(n - 1, n * accum);
}

Advantage:

Modern compilers can apply Tail Call Optimization (TCO), transforming the recursive call into a simple iterative jump (goto), thereby reusing the current stack frame and requiring $O(1)$ auxiliary stack space instead of $O(n)$.

Definition of a Balanced Tree

A Balanced Tree is a tree data structure whose height is bounded to $\mathcal{O}(\log n)$ where $n$ is the total number of nodes, ensuring that search, insertion, and deletion operations execute in logarithmic time.

Height-Balanced (AVL Tree Definition):

A binary tree is height-balanced if, for every node $N$ in the tree, the difference in height between its left subtree $H_L$ and right subtree $H_R$ (known as the Balance Factor) is at most 1:

$$\text{Balance Factor } BF(N) = H_L - H_R \in \{-1, 0, +1\}$$

Common Balanced Tree Structures:

AVL Trees, Red-Black Trees, B-Trees, and B+ Trees.

Definition of Hashing

Hashing is a data storage and retrieval technique that transforms a search key of arbitrary size into a fixed-size index within an array (hash table) using a mathematical function known as a Hash Function:

$$\text{Index} = h(\text{key}) \pmod{\text{TableSize}}$$

Key Components:

1. Hash Function: Maps keys uniformly and deterministically across table indices.
2. Hash Table: Fixed array of buckets storing records or pointers.
3. Collision Resolution: Handling situations where two distinct keys hash to the same bucket (e.g., Chaining or Open Addressing like Linear Probing).

Time Complexity:

Achieves average-case $\mathcal{O}(1)$ time complexity for search, insert, and delete operations.

Degree of a Vertex in Graph Theory

The degree of a vertex $V$ in a graph $G = (V, E)$ is the total number of edges incident to (connected to) that vertex.

In Undirected Graphs:

• $\deg(v)$: Total number of edges connected to vertex $v$ (a self-loop contributes 2 to the degree).
• Handshaking Lemma: The sum of degrees of all vertices equals twice the number of edges:
  $$\sum_{v \in V} \deg(v) = 2 |E|$$

In Directed Graphs (Digraphs):

• In-degree ($\deg^-(v)$): Number of incoming edges directed towards vertex $v$.
• Out-degree ($\deg^+(v)$): Number of outgoing edges directed away from vertex $v$.
• Total degree: $\deg(v) = \deg^-(v) + \deg^+(v)$.

Two Sorting Algorithms

Two fundamental sorting algorithms widely used in computer science are:

1. Merge Sort:

   • Paradigm: Divide-and-Conquer.
   • Method: Recursively divides the array into two halves, sorts each half, and merges the sorted halves.
   • Time Complexity: Worst: $\mathcal{O}(n \log n)$, Best: $\mathcal{O}(n \log n)$, Average: $\mathcal{O}(n \log n)$.
   • Stability: Stable sort; requires $\mathcal{O}(n)$ auxiliary space.

2. Quick Sort:

   • Paradigm: Divide-and-Conquer (Partitioning).
   • Method: Selects a ‘pivot’ element, partitions the array such that elements smaller than pivot precede it and larger elements follow it, then recursively sorts the sub-arrays.
   • Time Complexity: Average/Best: $\mathcal{O}(n \log n)$, Worst: $\mathcal{O}(n^2)$.

Why Huffman Algorithm is Needed

The Huffman Algorithm is an optimal greedy algorithm needed for lossless data compression (statistical encoding).

Technical Rationale:

1. Variable-Length Prefix Coding: Traditional character encoding systems (such as ASCII or Unicode) assign a fixed number of bits (e.g., 8 bits) to every character regardless of how often it appears.
2. Frequency-Based Economy: Huffman coding assigns shorter bit strings to characters that appear with high frequency (e.g., ‘e’, ‘t’, space) and longer bit strings to rarely occurring characters (e.g., ‘z’, ‘q’).
3. Prefix Property: Ensures that no code word is a prefix of any other code word, allowing unambiguous, instant streaming decompression without delimiters.
4. Significant Bandwidth/Storage Savings: Reduces text file and multimedia payload sizes by 20% to 70%.

Abstract Data Type (ADT)

An Abstract Data Type (ADT) is a mathematical model for data types where a data type is defined solely by its behavior (semantics) from the perspective of a consumer—specifically in terms of possible values and permissible operations—completely independent of any specific physical implementation or programming language.

Key Principles of ADT:

1. Data Abstraction: Hides internal data representation and memory layout from external callers.
2. Encapsulation: Access to data elements is restricted exclusively through a well-defined public interface (functions/methods).
3. Implementation Independence: The internal implementation can be changed (e.g., switching from array-based to linked list-based) without affecting existing client code that relies on the ADT interface.

Concrete Example: List ADT

+--------------------------------------------------------+
|                     List ADT Interface                 |
| - insert(index, item)   - remove(index)                |
| - get(index)            - size()          - isEmpty()  |
+---------------------------+----------------------------+
                            |
           +----------------+----------------+
           |                                 |
           v                                 v
+-----------------------+        +-----------------------+
| Array Implementation  |        | Singly Linked List    |
| (Contiguous memory,   |        | Implementation        |
| O(1) random access)   |        | (Dynamic nodes, O(1)  |
|                       |        | head insertion)       |
+-----------------------+        +-----------------------+

In this model, software modules call insert() or get() without needing to know whether items are stored in contiguous memory blocks or dynamically linked heap nodes.

Worst-Case Time Complexity

The Worst-Case Time Complexity of an algorithm expresses the maximum amount of time (or number of elementary operations) that the algorithm requires to execute on any input of size $n$. It is formally denoted using Big-O notation ($\mathcal{O}(f(n))$).

Mathematical Definition:

Let $T(n)$ be the running time of an algorithm on an input $I$ belonging to the set of all possible inputs $D_n$ of size $n$:

$$W(n) = \max_{I \in D_n} \{ T(I) \}$$

Why Worst-Case Analysis is Essential in Software Engineering:

1. Performance Guarantees (Upper Bound): Provides a strict mathematical guarantee that the algorithm will never perform worse than this threshold, regardless of how pathological the input distribution might be.
2. Mission-Critical / Real-Time Systems: In avionics, medical devices, banking transactions, and automated driving, systems cannot tolerate unpredictable performance spikes; worst-case boundaries must be strictly bounded.
3. Benchmarking Comparison: Provides an objective, reproducible metric to compare competing algorithms without depending on hardware variations.

Illustrative Examples:

• Linear Search: Worst case occurs when the target is absent or at the very end $\implies \mathcal{O}(n)$.
• Quick Sort: Worst case occurs when pivot selection always yields the most unbalanced partition (e.g., sorted array with last-element pivot) $\implies \mathcal{O}(n^2)$.
• Merge Sort: Worst case is strictly bounded to $\mathcal{O}(n \log n)$ under all circumstances.

Preorder Traversal of a Binary Tree

In a Preorder Traversal (Depth-First Traversal), nodes are visited in the following strict recursive sequence:

$$\textbf{Root} \longrightarrow \textbf{Left Subtree} \longrightarrow \textbf{Right Subtree}$$

C++ Function Implementation:

#include <iostream>
using namespace std;

// Binary Tree Node Structure
struct Node {
    int data;
    Node* left;
    Node* right;

    Node(int val) : data(val), left(nullptr), right(nullptr) {}
};

// Recursive Preorder Traversal Function
void preorderTraversal(Node* root) {
    // Base Case: empty tree / leaf child
    if (root == nullptr) {
        return;
    }

    // 1. Visit Current Root Node
    cout << root->data << " ";

    // 2. Traverse Left Subtree Recursively
    preorderTraversal(root->left);

    // 3. Traverse Right Subtree Recursively
    preorderTraversal(root->right);
}

Execution Example:

Consider the binary tree:

       1
      / \
     2   3
    / \
   4   5

• Preorder Sequence: Visit 1 $\to$ Visit 2 $\to$ Visit 4 $\to$ Visit 5 $\to$ Visit 3 $\implies$ 1, 2, 4, 5, 3
• Complexity: Time: $\mathcal{O}(n)$ (each node visited once), Space: $\mathcal{O}(h)$ call stack frames (where $h$ is tree height).

Practical Applications of Queue Data Structure

A Queue operates strictly on a FIFO (First In, First Out) discipline. Its core applications span systems programming, networking, and algorithmic computing:

1. CPU Process Scheduling (Operating Systems):
   • The OS Ready Queue stores processes waiting to be allocated CPU time slots in Round-Robin or Multi-Level Feedback Queue scheduling algorithms.
2. Asynchronous I/O Buffering:
   • Real-world hardware devices (keyboards, printers, network disk buffers) communicate via queues (e.g., printer spooling queue where print jobs execute in arrival order).
3. Graph Traversal (Breadth-First Search - BFS):
   • BFS algorithms require a FIFO queue to track discovered vertices and explore the graph level-by-level (used in shortest path algorithms on unweighted graphs).
4. Network Packet Routing & Traffic Congestion:
   • Internet routers, switches, and load balancers queue incoming TCP/IP packets into FIFO buffer queues before processing and forwarding.
5. Event-Driven Architectures & Message Brokers:
   • Enterprise message queues (e.g., RabbitMQ, Apache Kafka, AWS SQS) buffer asynchronous messages between decoupled microservices.

Binary Search vs. Linear Search

Parameter	Linear Search (Sequential Search)	Binary Search
Prerequisite	None (works on both unsorted and sorted data).	Data must be sorted in ascending or descending order.
Strategy	Sequentially scans elements one-by-one from beginning to end.	Divide-and-Conquer: Compares target with middle element, halving the search space each step.
Data Structure	Works on Arrays, Linked Lists, Streams.	Requires contiguous direct-indexed arrays ($O(1)$ random access).
Time Complexity (Best)	$\mathcal{O}(1)$ (element found at index 0).	$\mathcal{O}(1)$ (element found at exact middle).
Time Complexity (Worst)	$\mathcal{O}(n)$ (all $n$ elements inspected).	$\mathcal{O}(\log_2 n)$ (logarithmic reduction).
Time Complexity (Average)	$\mathcal{O}(n)$.	$\mathcal{O}(\log_2 n)$.
Performance Example ($n = 1,000,000$)	Up to $1,000,000$ comparisons.	At most $\lceil \log_2(1,000,000) \rceil = \mathbf{20}$ comparisons!

Breadth First Traversal (BFS) of a Graph

Breadth First Search (BFS) is a graph exploration algorithm that visits vertices in increasing order of their distance (number of edges) from an arbitrary starting source vertex $S$. It systematically visits all immediate adjacent neighbors (distance 1), then all neighbors of neighbors (distance 2), and so forth.

Core Data Structures:

1. FIFO Queue: Stores discovered vertices waiting to have their adjacent edges explored.
2. Visited Boolean Array: Prevents processing vertices multiple times and avoids infinite loops in cyclic graphs.

Algorithmic Procedure:

Algorithm BFS(Graph G, SourceVertex s):
1. Create a boolean array visited[] initialized to false.
2. Create an empty Queue Q.
3. Mark s as visited (visited[s] = true) and push s into Q: Q.enqueue(s).
4. While Q is NOT empty:
     a. u = Q.dequeue()
     b. Process / Print vertex u
     c. For each vertex v adjacent to u:
          if visited[v] == false:
              visited[v] = true
              Q.enqueue(v)

Complexity:

• Time Complexity: $\mathcal{O}(V + E)$ where $V$ is vertices and $E$ is edges (using Adjacency List).
• Space Complexity: $\mathcal{O}(V)$ for queue and visited map.

Recursive Algorithm to Find Factorial of $n$

The mathematical definition of factorial for a non-negative integer $n$ is defined recursively as:

$$n! = \begin{cases} 1 & \text{if } n = 0 \text{ or } n = 1 \quad \text{(Base Case)} \\ n \times (n - 1)! & \text{if } n > 1 \quad \text{(Recursive Step)} \end{cases}$$

Pseudocode / Algorithm:

Algorithm Factorial(n):
Input: An integer n >= 0
Output: The factorial value n!

Step 1: [Check Input Validation]
        If n < 0 Then:
            Write "Error: Factorial undefined for negative numbers"
            Return -1
Step 2: [Base Case]
        If n == 0 or n == 1 Then:
            Return 1
Step 3: [Recursive Case]
        Else:
            Return n * Factorial(n - 1)

Call Stack Execution Trace for $n = 4$:

• Factorial(4) calls $4 \times \text{Factorial}(3)$
• Factorial(3) calls $3 \times \text{Factorial}(2)$
• Factorial(2) calls $2 \times \text{Factorial}(1)$
• Factorial(1) hits base case $\implies$ returns $1$
• Returns $2 \times 1 = 2 \implies 3 \times 2 = 6 \implies 4 \times 6 = \mathbf{24}$.
• Complexity: Time: $\mathcal{O}(n)$, Space: $\mathcal{O}(n)$ stack frames.

AVL Tree Construction: Step-by-Step

An AVL Tree is a self-balancing Binary Search Tree (BST) where the balance factor $BF = \text{height}(\text{left}) - \text{height}(\text{right}) \in \{-1, 0, +1\}$ at every node. If $|BF| > 1$, balance is restored via tree rotations (LL, RR, LR, RL).

Given Input Sequence: 14, 16, 22, 19, 15, 12, 21

---

Step 1: Insert 14

• Tree: (14) [$BF=0$]

Step 2: Insert 16

• $16 > 14$, insert right child of 14.
• Tree:

    14 (BF = -1)
      \
       16 (BF = 0)
  

• Balanced.

Step 3: Insert 22

• $22 > 14$ and $22 > 16$, insert right child of 16.
• Tree:

    14 (BF = -2)  <-- Unbalanced! Right-Right (RR) imbalance at node 14
      \
       16 (BF = -1)
         \
          22 (BF = 0)
  

• Fix: Perform Left Rotation (RR rotation) around node 14.
• New Root: 16

       16 (BF = 0)
      /  \
    14    22 (BF = 0)
  

Step 4: Insert 19

• $19 > 16$ and $19 < 22$, insert left child of 22.
• Tree:

       16 (BF = -1)
      /  \
    14    22 (BF = 1)
         /
        19 (BF = 0)
  

• Balanced ($|BF| \le 1$).

Step 5: Insert 15

• $15 < 16$ and $15 > 14$, insert right child of 14.
• Tree:

       16 (BF = 0)
      /  \
    14    22
      \   /
      15 19
  

• Balanced ($BF(16)=0, BF(14)=-1, BF(22)=1$).

Step 6: Insert 12

• $12 < 14$, insert left child of 14.
• Subtree at 14:

        14 (BF = 0)
       /  \
      12   15
  

• Tree remains completely balanced!

Step 7: Insert 21

• $21 > 16, 21 < 22, 21 > 19$. Insert right child of 19.
• Subtree at 22:

        22 (BF = 2)  <-- Imbalance! Left child (19) has right child (21) => Left-Right (LR)
       /
      19 (BF = -1)
        \
         21
  

• Fix: Perform Left-Right (LR) Rotation on node 22:
  1. Left-rotate node 19: 21 becomes parent of 19.
  2. Right-rotate node 22: 21 becomes parent of 22.
• Subtree becomes:

        21
       /  \
      19   22
  

---

Final AVL Tree Structure:

            16 (BF = 0)
          /    \
        14      21 (BF = 0)
       /  \    /  \
      12  15  19   22

All balance factors are 0. The tree is completely balanced with height $h = 2$!

Quick Sort Algorithm Trace

Given Input Data Array:

[17, 8, 91, 10, 111] ($n = 5$, indices $0$ to $4$)

Quick Sort follows the Divide-and-Conquer principle using the Lomuto partition scheme (choosing the last element as the pivot):

---

Pass 1: Partition Full Array [17, 8, 91, 10, 111]

• low = 0, high = 4, pivot = array[high] = 111
• Initialize boundary index: $i = \text{low} - 1 = -1$.
• Scan $j$ from $0$ to $3$:
  • $j = 0: \text{array}[0] = 17 \le 111 \implies i = 0$, swap $\text{array}[0]$ with $\text{array}[0] \implies [17, 8, 91, 10, 111]$
  • $j = 1: \text{array}[1] = 8 \le 111 \implies i = 1$, swap $\text{array}[1]$ with $\text{array}[1] \implies [17, 8, 91, 10, 111]$
  • $j = 2: \text{array}[2] = 91 \le 111 \implies i = 2$, swap $\text{array}[2]$ with $\text{array}[2] \implies [17, 8, 91, 10, 111]$
  • $j = 3: \text{array}[3] = 10 \le 111 \implies i = 3$, swap $\text{array}[3]$ with $\text{array}[3] \implies [17, 8, 91, 10, 111]$
• Place pivot at correct sorted position: swap $\text{array}[i+1]$ with $\text{array}[\text{high}]$:
  • Swap $\text{array}[4]$ with $\text{array}[4]$ (already at position 4).
• Pivot 111 is fixed at index 4. Sub-problem: sort sub-array [17, 8, 91, 10] from index $0$ to $3$.

---

Pass 2: Partition Sub-array [17, 8, 91, 10]

• low = 0, high = 3, pivot = array[3] = 10
• Boundary index: $i = -1$.
• Scan $j$ from $0$ to $2$:
  • $j = 0: \text{array}[0] = 17 > 10$ (No swap)
  • $j = 1: \text{array}[1] = 8 \le 10 \implies i = 0$, swap $\text{array}[i]$ and $\text{array}[j]$:
    • Swap $\text{array}[0]$ (17) and $\text{array}[1]$ (8) $\implies [8, 17, 91, 10]$
  • $j = 2: \text{array}[2] = 91 > 10$ (No swap)
• Place pivot: swap $\text{array}[i+1]$ (index 1: value 17) with $\text{array}[\text{high}]$ (index 3: value 10):
  • Array becomes: [8, 10, 91, 17]
• Pivot 10 is fixed at index 1.
• Left sub-array: [8] (size 1, already sorted).
• Right sub-array: [91, 17] (indices 2 to 3).

---

Pass 3: Partition Sub-array [91, 17]

• low = 2, high = 3, pivot = array[3] = 17
• Boundary index: $i = 1$.
• Scan $j = 2: \text{array}[2] = 91 > 17$ (No swap).
• Place pivot: swap $\text{array}[i+1]$ (index 2: value 91) with $\text{array}[\text{high}]$ (index 3: value 17):
  • Array becomes: [8, 10, 17, 91, 111]
• Pivot 17 is fixed at index 2.
• Sub-array [91] has size 1 (base case).

---

Final Sorted Output:

$$\mathbf{[8, 10, 17, 91, 111]}$$

Minimum Spanning Tree (MST) Using Kruskal’s Algorithm

A Minimum Spanning Tree (MST) connects all vertices of a connected, edge-weighted undirected graph with the minimum total edge weight and without forming any cycles ($|V| - 1$ edges).

Graph Specification:

Vertices: $V = \{A, B, C, D, E, F\}$ ($|V| = 6$ vertices, required MST edges $= 6 - 1 = 5$). Edges with weights:

• $(B, C): 1$
• $(A, C): 2$
• $(D, E): 2$
• $(E, F): 3$
• $(A, B): 4$
• $(B, D): 5$
• $(D, F): 6$
• $(C, D): 8$
• $(C, E): 10$

---

Step 1: Sort All Edges in Non-Decreasing Order of Weight

Edge	Weight	Action	Reason
$(B, C)$	1	ACCEPT	Connects disjoint sets $\{B\}$ and $\{C\}$.
$(A, C)$	2	ACCEPT	Connects $\{A\}$ and $\{B, C\}$.
$(D, E)$	2	ACCEPT	Connects $\{D\}$ and $\{E\}$.
$(E, F)$	3	ACCEPT	Connects $\{E, D\}$ and $\{F\}$.
$(A, B)$	4	REJECT	$A, B$ already connected via path $A-C-B$ (Forms cycle $A-B-C-A$).
$(B, D)$	5	ACCEPT	Connects component $\{A, B, C\}$ to $\{D, E, F\}$.
$(D, F)$	6	REJECT	Cycle $D-E-F-D$.
$(C, D)$	8	REJECT	Cycle $C-B-D-C$.
$(C, E)$	10	REJECT	Cycle $C-B-D-E-C$.

---

Resulting MST Edges:

1. $(B, C)$ with weight $1$
2. $(A, C)$ with weight $2$
3. $(D, E)$ with weight $2$
4. $(E, F)$ with weight $3$
5. $(B, D)$ with weight $5$

   (A)
     \ [2]
      (C) --- [1] --- (B)
                        \ [5]
                        (D) --- [2] --- (E) --- [3] --- (F)

Total Minimum Weight of MST:

$$\text{Weight} = 1 + 2 + 2 + 3 + 5 = \mathbf{13}$$

Algorithms for Insertion and Deletion in a Binary Search Tree (BST)

A Binary Search Tree (BST) satisfies the property: for every node $X$, all keys in the left subtree are smaller ($< \text{key}(X)$) and all keys in the right subtree are greater ($> \text{key}(X)$).

---

1. Insertion Algorithm in BST

Algorithm BST_Insert(root, key):
Input: Root pointer of BST, value key to insert
Output: Updated root pointer

1. If root is NULL Then:
       Create a new node N with data = key, left = NULL, right = NULL
       Return N
2. If key < root.data Then:
       root.left = BST_Insert(root.left, key)
3. Else If key > root.data Then:
       root.right = BST_Insert(root.right, key)
4. Else:
       // Duplicate key; do not insert (or handle according to policy)
       Return root
5. Return root

• Time Complexity: Average: $\mathcal{O}(\log n)$, Worst (skewed tree): $\mathcal{O}(n)$.

---

2. Deletion Algorithm in BST

Deletion involves three distinct cases:

• Case 1 (Node is a Leaf): Simply delete the node and set parent pointer to NULL.
• Case 2 (Node has One Child): Bypass the node by linking its parent directly to its child.
• Case 3 (Node has Two Children): Find the node’s Inorder Successor (smallest value in its right subtree), overwrite the node’s data with the successor’s data, and recursively delete the inorder successor from the right subtree.

Algorithm BST_Delete(root, key):
Input: Root pointer of BST, value key to delete
Output: Updated root pointer

1. If root is NULL Then Return NULL
2. If key < root.data Then:
       root.left = BST_Delete(root.left, key)
3. Else If key > root.data Then:
       root.right = BST_Delete(root.right, key)
4. Else: // Found node to delete!
       // Case 1 & 2: Zero or One Child
       If root.left is NULL Then:
           temp = root.right
           free(root)
           Return temp
       Else If root.right is NULL Then:
           temp = root.left
           free(root)
           Return temp
       // Case 3: Two Children
       Else:
           succ = FindMin(root.right) // Inorder successor
           root.data = succ.data
           root.right = BST_Delete(root.right, succ.data)
5. Return root

Push and Pop Operations in Stack Using Linked List

When a stack is implemented using a Singly Linked List, dynamic memory allocation allows the stack to grow and shrink dynamically without fixed array limits (eliminating stack overflow unless heap memory is exhausted).

• The top pointer points to the head node of the linked list.
• All insertions (push) and deletions (pop) take place at the head node in strictly $\mathcal{O}(1)$ time.

---

1. PUSH Operation ($O(1)$)

Inserting new element val onto the stack:

1. Allocate memory for a new node: newNode = new Node(val).
2. Point newNode->next to the current top: newNode->next = top.
3. Update top to point to the new node: top = newNode.

Before Push(40):
  TOP ---> [ 30 | next ] ---> [ 20 | next ] ---> [ 10 | NULL ]

Step: Allocate newNode [ 40 | next ]
      newNode->next = TOP
      TOP = newNode

After Push(40):
  TOP ---> [ 40 | next ] ---> [ 30 | next ] ---> [ 20 | next ] ---> [ 10 | NULL ]

---

2. POP Operation ($O(1)$)

Removing the top element from the stack:

1. Check for Stack Underflow: If top == NULL, return error.
2. Store the current top node in a temporary pointer: temp = top.
3. Advance top to the next node: top = top->next.
4. Retrieve the data and free allocated heap memory: val = temp->data; delete temp; return val;.

Before Pop():
  TOP ---> [ 40 | next ] ---> [ 30 | next ] ---> [ 20 | next ] ---> [ 10 | NULL ]
            ^
            | (temp)

Step: TOP = TOP->next
      delete temp

After Pop():
  TOP ---> [ 30 | next ] ---> [ 20 | next ] ---> [ 10 | NULL ]
  Returned Value = 40

C++ Implementation:

struct Node {
    int data;
    Node* next;
    Node(int val) : data(val), next(nullptr) {}
};

class Stack {
private:
    Node* topNode;
public:
    Stack() : topNode(nullptr) {}

    void push(int val) {
        Node* newNode = new Node(val);
        newNode->next = topNode;
        topNode = newNode;
    }

    int pop() {
        if (isEmpty()) {
            cout << "Stack Underflow!\n";
            return -1;
        }
        Node* temp = topNode;
        int poppedVal = temp->data;
        topNode = topNode->next;
        delete temp;
        return poppedVal;
    }

    bool isEmpty() { return topNode == nullptr; }
};