🎯 DATA STRUCTURES — MASTER EXAM PLAN

Exam: Tomorrow | Time Available: ~5 Hours | Language: Python

---

⏱️ YOUR 5-HOUR BATTLE PLAN

|------|-------|-------|

---

🔥 TEACHER'S PRIORITY PROGRAMS (Nail These!)

1. ✅ Linked List → programs/01_linked_list.py
2. ✅ Queue → programs/02_queue.py
3. ✅ Infix to Postfix using Stack → programs/03_infix_to_postfix.py
4. ✅ Bubble, Merge, Quick Sort → programs/04_sorting.py
5. ✅ Binary Search Tree → programs/05_bst.py

---

📌 MOST IMPORTANT CONCEPTS (If you only have 30 min)

1. Big O Notation — O(1), O(log n), O(n), O(n log n), O(n²)
2. Linked List — singly, insert, delete, traverse
3. Stack — LIFO, push/pop, infix→postfix conversion
4. Queue — FIFO, enqueue/dequeue
5. Bubble Sort — O(n²), stable
6. Merge Sort — O(n log n), divide & conquer, stable
7. Quick Sort — O(n log n) avg, pivot, in-place
8. BST — left < root < right, insert/search/delete
9. BFS vs DFS — queue vs stack
10. Hashing — hash function, collision resolution

---

💡 VIVA GOLDEN RULES

• Always say time complexity for every algorithm you mention
• Always explain real-world use (browser history → linked list, etc.)
• Know the difference between similar structures (Stack vs Queue, Array vs Linked List)
• For every sort: know stable/unstable, in-place/not, best/avg/worst

---

Files in this folder:

final-material/
├── 00_MASTER_PLAN.md          ← YOU ARE HERE
├── 01_unit1_foundations.md    ← Big O, Recursion, ADT
├── 02_unit2_linear_ds.md      ← Arrays, LL, Stack, Queue
├── 03_unit3_sorting.md        ← All sorting algorithms
├── 04_unit4_nonlinear.md      ← Trees, Graphs, Hashing
├── 05_viva_questions.md       ← Q&A for exam viva
├── CHEATSHEET.md              ← Last-minute 1-page reference
└── programs/
    ├── 01_linked_list.py
    ├── 02_queue.py
    ├── 03_infix_to_postfix.py
    ├── 04_sorting.py
    └── 05_bst.py

📘 UNIT 1 — Foundations & Algorithmic Analysis

---

1.1 Data Structures & ADTs

What is a Data Structure?

A Data Structure is a way of organizing and storing data in memory so that it can be accessed and modified efficiently.

Two types:

• Primitive: int, float, char, bool
• Non-Primitive: Arrays, Linked Lists, Trees, Graphs, etc.

What is an ADT (Abstract Data Type)?

An ADT is a logical description of how data is organized and what operations can be performed — WITHOUT worrying about implementation details.

ADT = Data + Operations (no implementation detail)
Example: Stack ADT → push(), pop(), peek(), isEmpty()
         You don't care if it's implemented via array or linked list

Why ADTs? → Separation of concerns. The user of the ADT doesn't need to know HOW it works.

Common Operations on Data Structures:

|-----------|-------------|

---

1.2 Algorithm Analysis — The BIG PICTURE

Time Complexity

How the runtime grows as input size n increases.

Space Complexity

How memory usage grows as input size n increases.

---

1.3 Big O Notation — MASTER THIS!

Big O describes the upper bound (worst case).

O(f(n)) = algorithm's growth rate

The Complexity Ladder (Best → Worst):

|----------|------|---------|

Visual Memory Trick:

1 < log n < n < n log n < n² < n³ < 2ⁿ < n!
FAST ←————————————————————————————→ SLOW

Big Omega (Ω) — Lower Bound (Best Case)

Ω(n) = best-case scenario
Example: Linear search finds element at index 0 → Ω(1)

Big Theta (Θ) — Tight Bound (Average Case)

Θ(n) = both upper AND lower bound match
Example: Linear search in average case → Θ(n)

Simplification Rules:

# Rule 1: Drop constants
O(2n) → O(n)
O(100) → O(1)

# Rule 2: Drop lower order terms
O(n² + n) → O(n²)
O(n + log n) → O(n)

# Rule 3: Different inputs = different variables
def func(a, b):        # O(a + b), NOT O(n)
    for x in a: ...
    for y in b: ...

Examples to Know:

# O(1) — constant
def get_first(arr):
    return arr[0]

# O(n) — linear
def find(arr, target):
    for item in arr:
        if item == target:
            return True

# O(n²) — quadratic
def bubble(arr):
    for i in range(len(arr)):
        for j in range(len(arr)-1):  # nested loop!
            ...

# O(log n) — binary search
def binary_search(arr, target):
    lo, hi = 0, len(arr)-1
    while lo <= hi:
        mid = (lo + hi) // 2
        if arr[mid] == target: return mid
        elif arr[mid] < target: lo = mid + 1
        else: hi = mid - 1

---

1.4 Cases: Best / Average / Worst

|------|---------|------------------------|

---

1.5 Algorithm Design Paradigms

1. Divide & Conquer

Split problem → Solve subproblems recursively → Combine results
Examples: Merge Sort, Quick Sort, Binary Search

2. Greedy

At each step, pick the locally optimal choice
Hope: local optima → global optimum
Examples: Dijkstra's shortest path, Huffman encoding
Note: Doesn't always give the BEST answer globally

3. Dynamic Programming (DP)

Break into overlapping subproblems → Store results (memoization)
Avoid recomputing the same subproblems
Examples: Fibonacci, Knapsack, Longest Common Subsequence

|----------|----------|----------|

---

1.6 Recursion

What is Recursion?

A function that calls itself to solve a smaller version of the same problem.

Two Essential Parts:

1. Base Case — The stopping condition (prevents infinite loop)
2. Recursive Case — The function calling itself with a smaller input

# Classic: Factorial
def factorial(n):
    if n == 0:          # BASE CASE
        return 1
    return n * factorial(n - 1)  # RECURSIVE CASE

# Classic: Fibonacci
def fib(n):
    if n <= 1:          # BASE CASE
        return n
    return fib(n-1) + fib(n-2)  # RECURSIVE CASE

The Call Stack

factorial(4)
  → 4 * factorial(3)
       → 3 * factorial(2)
            → 2 * factorial(1)
                 → 1 * factorial(0)
                      → returns 1

Each function call is pushed onto the call stack and popped when it returns.

Recursion vs Iteration

|-|-----------|-----------|

---

🎯 UNIT 1 VIVA QUICK-FIRE

Q: What is Big O?

A: Upper bound of an algorithm's time complexity — worst-case growth rate.

Q: What's O(log n)?

A: Binary search — each step halves the input.

Q: Difference between O, Ω, Θ?

A: O = worst case upper bound, Ω = best case lower bound, Θ = tight/average bound.

Q: What is an ADT?

A: A mathematical model of a data type with defined operations but no implementation details.

Q: What is the base case in recursion?

A: The condition that stops recursion. Without it, you get infinite recursion / stack overflow.

Q: What is Divide & Conquer?

A: Break problem into smaller subproblems, solve recursively, then combine results. Example: Merge Sort.

Unit 2 — Linear Data Structures

Arrays

What is an Array? A collection of elements stored in contiguous (side-by-side) memory locations. All elements must be the same type.

Types:

• 1D Array: arr = [10, 20, 30, 40]
• 2D Array (Matrix): matrix = [[1,2],[3,4]]
• Static: Fixed size (C arrays)
• Dynamic: Resizable (Python list, Java ArrayList)

Complexity:

|-----------|------|-----|

Array vs Linked List:

|-|-------|-------------|

---

Linked Lists ⭐ EXAM PRIORITY

What is it? A sequence of Nodes where each node has DATA + a NEXT pointer to the next node. Nodes are scattered in memory, connected by pointers.

HEAD → [10|→] → [20|→] → [30|None]

The Node class (memorize this):

class Node:
    def __init__(self, data):
        self.data = data   # stores value
        self.next = None   # points to next node

Singly Linked List

Each node points FORWARD only. HEAD → A → B → C → None

Doubly Linked List

Each node has BOTH prev and next pointers.

None ← A ↔ B ↔ C → None

Use case: Browser history (back AND forward navigation)

Circular Linked List

Last node's next points BACK to HEAD. No None at end.

HEAD → A → B → C → (back to HEAD)

Use case: Round-robin scheduling, music playlist loop

Insert at HEAD — O(1):

new_node.next = self.head   # point new node to old head
self.head = new_node         # head now points to new node

Traversal — O(n):

current = self.head
while current:
    print(current.data)
    current = current.next

Delete by value — O(n):

# Special case: deleting head
if self.head.data == target:
    self.head = self.head.next
    return
# General case: find node BEFORE target
current = self.head
while current.next:
    if current.next.data == target:
        current.next = current.next.next  # skip target
        return
    current = current.next

Complexity Summary:

|-----------|------|

Real World Uses:

• Browser history (Doubly Linked List)
• Undo/Redo in text editors
• Music playlists (Circular)
• Dynamic memory allocation

---

Stacks (LIFO) ⭐ EXAM PRIORITY

What is it? Last In, First Out. Like a stack of plates — you add and remove from the TOP only.

     ┌───┐
     │ C │  ← TOP (last added, first removed)
     ├───┤
     │ B │
     ├───┤
     │ A │  ← BOTTOM (first added, last removed)
     └───┘

ADT Operations:

|-----------|-------------|------------|

Python Implementation:

stack = []
stack.append(10)    # push
stack.append(20)
top = stack[-1]     # peek
stack.pop()         # pop → removes 20

Real World Uses:

• Function call stack (recursion uses this!)
• Infix to Postfix conversion
• Undo/Redo operations
• Browser back button
• DFS graph traversal

---

Queues (FIFO) ⭐ EXAM PRIORITY

What is it? First In, First Out. Like a bank line — people join at REAR and leave from FRONT.

FRONT → [A] [B] [C] [D] ← REAR
dequeue ↑                  ↑ enqueue

ADT Operations:

|-----------|-------------|------------|

Python Implementation (use deque!):

from collections import deque
q = deque()
q.append(10)      # enqueue — add to rear
q.append(20)
q.popleft()       # dequeue — remove from front → returns 10
print(q[0])       # peek front

Types of Queues:

• Simple Queue: Basic FIFO
• Circular Queue: Rear connects to front — fixes wasted space
• Priority Queue: Elements have priorities, highest exits first (implemented with Heap)
• Deque: Insert/delete from BOTH ends

Real World Uses:

• CPU scheduling / Print queue
• BFS graph traversal
• Keyboard input buffer
• Call center waiting lines

---

Stack vs Queue — KEY COMPARISON

|---------|-------|-------|

Viva Quick-Fire

Q: What is a Linked List?

A: A data structure where nodes are stored in non-contiguous memory. Each node contains data and a pointer (next) to the next node.

Q: Difference between Array and Linked List?

A: Arrays use contiguous memory with O(1) random access but O(n) insert/delete. Linked Lists use scattered memory with O(n) access but O(1) insert/delete at a known node.

Q: What is LIFO?

A: Last In, First Out. Stack uses LIFO — the last element pushed is the first to be popped.

Q: What is FIFO?

A: First In, First Out. Queue uses FIFO — the first element enqueued is the first to be dequeued.

Q: What is the difference between Stack and Queue?

A: Stack is LIFO (one end — top for both push and pop). Queue is FIFO (two ends — rear for enqueue, front for dequeue).

Q: What is a Circular Linked List?

A: A linked list where the last node's next pointer points back to the head instead of None. Used in round-robin scheduling.

Q: What is a Doubly Linked List?

A: Each node has two pointers — next and prev. Allows traversal in both directions. Used in browser history.

Q: What is peek() in Stack?

A: Returns the top element without removing it from the stack. O(1) operation.

Q: Why use deque for Queue in Python?

A: list.pop(0) is O(n) because it shifts all elements. deque.popleft() is O(1) — no shifting needed.

Q: What is a Priority Queue?

A: A queue where elements have priorities. The element with highest priority is dequeued first regardless of insertion order. Implemented using a Heap.

Unit 3 — Sorting Algorithms

Key Terminology

|------|---------|---------|

---

Bubble Sort ⭐ EXAM PRIORITY

Idea: Compare adjacent elements. If left > right, swap them. The largest element "bubbles up" to its correct position after each pass.

Step-by-step with [64, 34, 25, 12]:

Pass 1: compare (64,34) → swap → compare (64,25) → swap → compare (64,12) → swap
        [34, 25, 12, 64]   ← 64 is in final position!
Pass 2: [25, 12, 34, 64]
Pass 3: [12, 25, 34, 64]   ← sorted!

The Code (memorize this pattern):

def bubble_sort(arr):
    n = len(arr)
    for i in range(n - 1):           # n-1 passes
        swapped = False
        for j in range(n - 1 - i):   # -i because last i are sorted
            if arr[j] > arr[j + 1]:  # wrong order?
                arr[j], arr[j+1] = arr[j+1], arr[j]  # swap!
                swapped = True
        if not swapped:               # already sorted — optimization
            break
    return arr

|------|------|-------|

Stable: YES | In-place: YES

---

Insertion Sort

Idea: Like sorting playing cards in your hand. Pick one card, slide it into the correct position in your already-sorted hand.

[5, 2, 4, 6, 1]
Take 2: insert before 5 → [2, 5, 4, 6, 1]
Take 4: insert between 2 and 5 → [2, 4, 5, 6, 1]
Take 1: insert at start → [1, 2, 4, 5, 6]

Best case O(n) — great for nearly-sorted data!

Stable: YES | In-place: YES

---

Selection Sort

Idea: Find the minimum in the unsorted portion, place it at the start. Repeat.

O(n²) always. Unstable. In-place.

---

Merge Sort ⭐ EXAM PRIORITY

Idea: Divide & Conquer. Keep splitting array in half until you have individual elements (already sorted). Then merge sorted halves back together.

Trace with [38, 27, 43, 3]:

DIVIDE:
[38, 27, 43, 3]
  [38, 27]    [43, 3]
  [38] [27]   [43] [3]

MERGE (each pair in sorted order):
  [27, 38]    [3, 43]
[3, 27, 38, 43]  ← done!

The TWO functions (learn separately!):

# Function 1: SPLIT (just divides recursively)
def merge_sort(arr):
    if len(arr) <= 1:        # BASE CASE: single element is sorted
        return arr
    mid = len(arr) // 2
    left  = merge_sort(arr[:mid])   # sort left half
    right = merge_sort(arr[mid:])   # sort right half
    return merge(left, right)       # merge sorted halves

# Function 2: MERGE (the actual work happens here)
def merge(left, right):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:   # <= makes it STABLE
            result.append(left[i]); i += 1
        else:
            result.append(right[j]); j += 1
    result.extend(left[i:])    # add remaining
    result.extend(right[j:])
    return result

|------|------|-------|

Stable: YES | In-place: NO — needs O(n) extra memory

---

Quick Sort ⭐ EXAM PRIORITY

Idea: Choose a PIVOT element. Partition the array so all elements < pivot go LEFT, all > pivot go RIGHT. Pivot is now in its FINAL correct position! Recursively sort left and right sides.

Trace with [10, 7, 8, 9, 1, 5], pivot = 5 (last element):

Walk left to right, put elements <= 5 on left side:
1 ≤ 5 → left side
Result: [1, 5, 8, 9, 7, 10]
         ↑ ← 5 is in final position! → ↑
Sort [1] and [8, 9, 7, 10] separately → done!

The Partition function (memorize this):

def partition(arr, low, high):
    pivot = arr[high]     # choose last element as pivot
    i = low - 1           # i = boundary of smaller elements

    for j in range(low, high):
        if arr[j] <= pivot:         # if current <= pivot
            i += 1                  # expand smaller boundary
            arr[i], arr[j] = arr[j], arr[i]  # swap into smaller zone

    # Place pivot in its correct final position
    arr[i+1], arr[high] = arr[high], arr[i+1]
    return i + 1   # return pivot's final index

def quick_sort(arr, low, high):
    if low < high:
        pivot_idx = partition(arr, low, high)
        quick_sort(arr, low, pivot_idx - 1)   # sort left
        quick_sort(arr, pivot_idx + 1, high)  # sort right

|------|------|-------|

Stable: NO | In-place: YES | Fastest in practice

---

Heap Sort

Build a Max-Heap from array → repeatedly extract the max and place at end.

O(n log n) always | O(1) space | Unstable | In-place

---

Non-Comparison Sorts (Conceptual)

Counting Sort: Count frequency of each element. Works only for integers in a known range [0, k]. Time: O(n+k). Stable.

Radix Sort: Sort digit by digit (least to most significant). Uses Counting Sort internally. Time: O(d × (n+k)).

---

THE MASTER TABLE — Memorize This!

|-----------|------|---------|-------|-------|--------|----------|

---

Viva Quick-Fire

Q: What is a stable sort?

A: A sort where equal elements maintain their original relative order. Bubble, Merge, Insertion are stable.

Q: Which sort has guaranteed O(n log n) in ALL cases?

A: Merge Sort and Heap Sort.

Q: Why is Merge Sort O(n) space?

A: It needs an auxiliary array to merge two sorted halves — cannot merge in-place.

Q: When is Quick Sort worst case O(n²)?

A: When the pivot is always the smallest or largest element — happens with sorted/reverse sorted arrays and bad pivot choice.

Q: How does Bubble Sort work?

A: Repeatedly compares adjacent elements and swaps if arr[j] > arr[j+1]. After each pass, the largest unsorted element reaches its correct position at the end.

Q: What is a pivot in Quick Sort?

A: An element used to partition the array. All elements smaller than pivot go left, all larger go right. The pivot ends up in its final sorted position.

Q: Which sort is fastest in practice?

A: Quick Sort — excellent cache performance and low constant factors despite O(n²) worst case.

Q: Best sort for nearly-sorted data?

A: Insertion Sort — best case O(n).

Q: Best sort for linked lists?

A: Merge Sort — doesn't require random access.

Unit 4 — Non-Linear Data Structures

Trees

What is a Tree? A hierarchical data structure consisting of nodes connected by edges. It represents a parent-child relationship.

Terminology:

• Root: The topmost node.
• Child / Parent: Standard hierarchy.
• Leaf Node: A node with NO children.
• Internal Node: A node with at least one child.
• Height of Tree: Longest path from root to a leaf.
• Depth of Node: Path from root to that node.

Binary Tree

A tree where each node has AT MOST 2 children (Left and Right).

Binary Search Tree (BST) ⭐ EXAM PRIORITY

A Binary Tree with a strict rule:

1. All nodes in LEFT subtree are < (smaller than) the root.
2. All nodes in RIGHT subtree are > (greater than) the root.

Why use BST? It allows for extremely fast searching. Each comparison cuts the search space in half.

• Average Search Time: O(log n)
• Worst Case (Unbalanced like a linked list): O(n)

Tree Traversals (Printing the tree)

Traversing means visiting every node exactly once.

1. Pre-order (Root, Left, Right):

- Used to create a copy of the tree.

- Example: 5, 3, 2, 4, 7, 6, 8

1. In-order (Left, Root, Right): ⭐

- CRITICAL: Inorder traversal of a BST always prints elements in SORTED (ascending) order!

- Example: 2, 3, 4, 5, 6, 7, 8

1. Post-order (Left, Right, Root):

- Used to delete the tree (delete children before parent).

- Example: 2, 4, 3, 6, 8, 7, 5

---

Graphs

What is a Graph? A collection of Vertices (Nodes) and Edges (connections between them). Trees are a special type of graph (a graph with no cycles).

Types:

• Directed (Digraph): Edges have direction (A → B). Example: Twitter followers.
• Undirected: Edges have no direction (A — B). Example: Facebook friends.
• Weighted: Edges have weights/costs. Example: Distance between cities.
• Cyclic / Acyclic: Contains cycles (loops) or not.

Representations:

1. Adjacency Matrix: 2D array. matrix[i][j] = 1 if edge exists.

- Space: O(V²)

- Best for: Dense graphs (many edges).

1. Adjacency List: Array of lists. list[i] contains all neighbors of vertex i.

- Space: O(V + E)

- Best for: Sparse graphs (few edges). Most commonly used!

Graph Traversals

1. Breadth-First Search (BFS)

• Explores level by level (neighbors first).
• Uses a Queue data structure.
• Used for finding the shortest path in unweighted graphs.

2. Depth-First Search (DFS)

• Explores as deep as possible before backtracking.
• Uses a Stack (or recursion).
• Used for finding cycles, topological sorting, solving mazes.

---

Hashing

What is Hashing? A technique to map a large range of key values to a smaller range of array indices using a Hash Function.

Why? It allows for O(1) average time complexity for Search, Insert, and Delete!

Hash Table

An array that stores the values based on the index calculated by the Hash Function.

Hash Collision

What happens when the hash function maps two different keys to the SAME index? This is a collision.

Collision Resolution Techniques:

1. Chaining (Open Hashing):

- Each slot in the array is a Linked List.

- If collision occurs, just append the new element to the linked list at that index.

1. Open Addressing (Closed Hashing):

- All elements are stored in the array itself. If a collision happens, find the next empty slot.

- Linear Probing: Check next slot (index + 1), then next, until empty found. (Leads to clustering).

- Quadratic Probing: Check index + 1², index + 2², index + 3², etc.

- Double Hashing: Use a second hash function to determine the step size.

---

Tries (Prefix Tree)

What is a Trie? A tree-like structure used for storing strings.

• Each node represents a single character.
• Excellent for autocomplete, spell checkers, and searching prefixes.
• Search time depends on the length of the string, NOT the number of strings stored. O(L) where L is word length.

---

Viva Quick-Fire

Q: Difference between Tree and Graph?

A: A Tree is a hierarchical structure with a root and no cycles. A Graph is a network structure that can have cycles and disconnected components.

Q: Why use a Binary Search Tree (BST)?

A: Because it provides fast search, insertion, and deletion operations (O(log n) on average) by maintaining elements in a sorted structure.

Q: What is the worst-case time complexity of a BST?

A: O(n). This happens if the tree becomes skewed (e.g., inserting elements that are already sorted), turning it essentially into a linked list.

Q: Which traversal of a BST gives a sorted sequence?

A: In-order traversal (Left, Root, Right).

Q: What data structure does BFS use?

A: Queue.

Q: What data structure does DFS use?

A: Stack (or recursion, which uses the call stack).

Q: What is a Hash Collision?

A: When two distinct keys are mapped to the exact same index in a hash table by the hash function.

Q: Name two ways to handle Hash Collisions.

A: Chaining (using linked lists at each index) and Open Addressing (like Linear Probing, finding the next available slot).

Q: What is the main advantage of a Trie?

A: It provides extremely fast string searching based on prefixes, making it ideal for autocomplete features. Time complexity is proportional to word length, not dictionary size.

Master Viva Q&A — 61 Questions

This section contains rapid-fire questions covering all 4 units, specifically tailored for what an examiner will ask during your practical/viva.

General & Unit 1

Q1: What is a Data Structure?

A: A specialized format for organizing, processing, retrieving and storing data in memory.

Q2: What is an Algorithm?

A: A step-by-step procedure or set of rules to solve a specific problem.

Q3: What is Time Complexity?

A: The amount of time an algorithm takes to run, expressed as a function of the input size (n).

Q4: What is Space Complexity?

A: The amount of extra memory an algorithm requires to run, expressed as a function of input size (n).

Q5: What is Big O Notation?

A: It represents the UPPER BOUND or WORST-CASE scenario of an algorithm's time or space complexity.

Q6: What is Big Omega (Ω) and Big Theta (Θ)?

A: Omega is the lower bound (best case). Theta is the exact bound (average case).

Q7: Rank time complexities from fastest to slowest.

A: O(1) > O(log n) > O(n) > O(n log n) > O(n²) > O(2^n) > O(n!)

Q8: What is an ADT (Abstract Data Type)?

A: A theoretical model that specifies WHAT operations can be performed on a data structure, but not HOW they are implemented (e.g., List, Stack, Queue).

Q9: What is Recursion?

A: When a function calls itself to solve a smaller instance of the same problem.

Q10: What is a Base Case in recursion?

A: The condition that stops the recursive calls, preventing an infinite loop and stack overflow.

---

Unit 2 — Linear Data Structures

Q11: Difference between Array and Linked List?

A: Arrays use contiguous memory, sizes are fixed, access is O(1). Linked lists use non-contiguous memory connected by pointers, size is dynamic, access is O(n).

Q12: What is a Stack?

A: A linear data structure following LIFO (Last In First Out). Insertion (push) and deletion (pop) happen at the same end (top).

Q13: Name an application of Stack.

A: Undo mechanism in text editors, browser history, recursive function call stack, evaluating postfix expressions.

Q14: What is a Queue?

A: A linear data structure following FIFO (First In First Out). Insertion (enqueue) at the rear, deletion (dequeue) at the front.

Q15: Name an application of Queue.

A: Print queue, CPU task scheduling, breadth-first search in graphs.

Q16: Why use deque from collections for Queues in Python instead of lists?

A: In a normal Python list, pop(0) takes O(n) time because it shifts all elements. deque.popleft() takes O(1) time.

Q17: What is a Circular Queue?

A: A queue where the last position is connected back to the first position. It solves the problem of wasted space in standard array-based queues.

Q18: What is a Priority Queue?

A: A queue where each element has a priority. Elements with higher priority are dequeued before elements with lower priority, regardless of insertion order.

Q19: What is a Doubly Linked List?

A: A linked list where each node contains two pointers: one pointing to the next node and one pointing to the previous node.

Q20: Advantage of Doubly Linked List?

A: You can traverse the list in both forward and backward directions. Deletion is easier if you have a pointer to the node to be deleted.

Q21: What is a Circular Linked List?

A: A linked list where the last node points back to the head node instead of None.

Q22: How do you convert Infix to Postfix?

A: Use a stack for operators. Operands go directly to output. Operators are pushed to the stack based on precedence rules. Brackets control the flow.

Q23: Why do computers prefer Postfix notation?

A: Postfix eliminates the need for parentheses and precedence rules (BODMAS). It can be easily evaluated using a single stack.

Q24: What is the time complexity of inserting at the head of a Linked List?

A: O(1).

Q25: What is the time complexity of accessing the nth element in a Linked List?

A: O(n), because you must traverse from the head.

---

Unit 3 — Sorting

Q26: What is a stable sort?

A: A sorting algorithm that preserves the original relative order of equal elements.

Q27: Name some stable sorts.

A: Bubble Sort, Insertion Sort, Merge Sort.

Q28: What is an in-place sort?

A: An algorithm that requires a small, constant amount of extra memory space O(1) to sort the data.

Q29: Name an out-of-place sort.

A: Merge Sort. It requires O(n) auxiliary space to merge the arrays.

Q30: How does Bubble Sort work?

A: It repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. The largest elements "bubble" to the end.

Q31: Time complexity of Bubble Sort?

A: Worst and Average: O(n²). Best (if already sorted and optimized with a flag): O(n).

Q32: How does Merge Sort work?

A: Divide the array in half recursively until sub-arrays are size 1. Then repeatedly merge the sub-arrays to produce new sorted sub-arrays until one sorted array remains.

Q33: Time complexity of Merge Sort?

A: O(n log n) in Best, Average, and Worst cases.

Q34: How does Quick Sort work?

A: Pick a pivot element. Partition the array so elements smaller than the pivot are on the left, and larger elements are on the right. Recursively apply this to the left and right sub-arrays.

Q35: Time complexity of Quick Sort?

A: Average/Best: O(n log n). Worst: O(n²) (happens when the array is already sorted and the pivot is chosen poorly).

Q36: Which is faster in practice: Merge Sort or Quick Sort?

A: Quick Sort is generally faster in practice due to better cache locality and smaller constant factors, even though its worst-case is O(n²).

Q37: Best sorting algorithm for linked lists?

A: Merge Sort, because it does not require random access to elements.

Q38: What is Insertion Sort best used for?

A: Small datasets or arrays that are already mostly sorted.

Q39: How does Selection Sort work?

A: Repeatedly finds the minimum element from the unsorted part and puts it at the beginning.

Q40: Is Quick Sort stable?

A: No, Quick Sort is typically unstable.

---

Unit 4 — Non-Linear Data Structures

Q41: What is a Tree?

A: A hierarchical non-linear data structure consisting of nodes connected by edges, with a single root.

Q42: What is a Binary Tree?

A: A tree where every node has at most two children (left and right).

Q43: What is a Binary Search Tree (BST)?

A: A binary tree where for every node, all elements in the left subtree are smaller, and all elements in the right subtree are larger.

Q44: Time complexity of searching in a BST?

A: Average: O(log n). Worst: O(n) (if the tree becomes skewed like a linked list).

Q45: Name the three depth-first tree traversals.

A: In-order (Left, Root, Right), Pre-order (Root, Left, Right), Post-order (Left, Right, Root).

Q46: Which traversal gives elements in sorted order for a BST?

A: In-order traversal.

Q47: What is the height of a tree?

A: The length of the longest path from the root to a leaf node.

Q48: What is a Graph?

A: A non-linear data structure consisting of a set of vertices (nodes) and a set of edges connecting them.

Q49: Difference between Directed and Undirected Graph?

A: In a directed graph, edges have a direction (one-way). In an undirected graph, edges have no direction (two-way).

Q50: How do you represent a Graph in memory?

A: Adjacency Matrix (2D array) or Adjacency List (array of linked lists).

Q51: When to use Adjacency Matrix vs Adjacency List?

A: Use Matrix for dense graphs (many edges). Use List for sparse graphs (few edges) to save memory.

Q52: What is Breadth-First Search (BFS)?

A: A graph traversal algorithm that explores the neighbor nodes first, level by level. It uses a Queue.

Q53: What is Depth-First Search (DFS)?

A: A graph traversal algorithm that explores as far as possible along each branch before backtracking. It uses a Stack (or recursion).

Q54: What is Hashing?

A: A technique to convert a range of key values into a range of indexes of an array using a hash function.

Q55: What is the main benefit of a Hash Table?

A: Average O(1) time complexity for search, insertion, and deletion.

Q56: What is a Hash Collision?

A: When a hash function generates the same index for more than one key.

Q57: How do you resolve Hash Collisions?

A: Chaining (using linked lists at each index) or Open Addressing (finding the next empty slot using linear or quadratic probing).

Q58: What is a Trie?

A: A tree data structure used for efficient retrieval of a key in a large dataset of strings (Prefix tree).

Q59: Application of a Trie?

A: Autocomplete, spell checking, IP routing.

Q60: What is a Heap?

A: A specialized tree-based data structure that satisfies the heap property (e.g., in a Max Heap, parent is always >= children).

Q61: What data structure is used to implement a Priority Queue?

A: A Heap.

Last 10-Minute Exam Cheatsheet ⚡

---

⏱️ Time Complexity Cheat Codes

---

🧩 The "Explain Like I'm 5" Anchors

If your mind goes blank, remember these real-world objects:

• Linked List: A Train. Carriages connected by hooks. Easy to add a carriage, hard to find the 50th carriage.
• Stack: A Stack of Plates. Last plate put down is the first one picked up (LIFO).
• Queue: A Movie Ticket Line. First person in line gets the ticket first (FIFO).
• Bubble Sort: Bubbles rising. Largest items float to the end one by one.
• Merge Sort: Sorting a deck of cards by tearing it in half until you have single cards, then pairing them back up.
• Quick Sort: Picking a leader (pivot). Shorter people go left, taller people go right.
• BST: A family tree where left children are always smaller, right children always bigger.

---

💻 3-Line Code Skeletons

1. Linked List Traversal:

current = self.head
while current:
    print(current.data)
    current = current.next

2. Queue with Deque:

from collections import deque
q = deque()
q.append(x)     # Insert
q.popleft()     # Delete

3. BST Inorder Traversal (Always Sorted!):

def inorder(node):
    if node:
        inorder(node.left)
        print(node.data)
        inorder(node.right)

4. Bubble Sort Swap Logic:

if arr[j] > arr[j+1]:
    arr[j], arr[j+1] = arr[j+1], arr[j]

---

🗣️ Viva Survival Phrases

If you get stuck during the viva, use these phrases to show you know what you're talking about:

• "I used a deque instead of a list because list.pop(0) is O(n), but deque is O(1)."
• "Merge Sort guarantees O(n log n), but it requires extra memory, so it is not in-place."
• "Quick Sort's worst-case is O(n²), but in practice, it is the fastest because of cache locality."
• "In a Binary Search Tree, an In-Order Traversal will always return the elements in sorted order."
• "Postfix notation is better for computers because it doesn't require parentheses or BODMAS rules, so we can evaluate it linearly using a Stack."

Deep Breath. You've got this. Good luck! 🚀

"""
====================================================
QUEUE — Complete Implementation (Exam Ready)
====================================================
Covers:
  - Queue using Python list (simple)
  - Queue using collections.deque (proper/efficient)
  - Queue using Linked List (manual implementation)
  - Operations: enqueue, dequeue, peek, isEmpty, size

KEY VIVA POINTS:
  - FIFO: First In, First Out
  - Enqueue = add to REAR
  - Dequeue = remove from FRONT
  - Real use: BFS, scheduling, printer queue
"""

from collections import deque


# ======================================
# METHOD 1: Queue using Python list
# (Simple — but dequeue is O(n))
# ======================================
class QueueUsingList:
    def __init__(self):
        self.queue = []

    def enqueue(self, data):
        self.queue.append(data)           # add to rear — O(1)
        print(f"Enqueued: {data}")

    def dequeue(self):
        if self.is_empty():
            print("Queue is empty! Underflow.")
            return None
        removed = self.queue.pop(0)       # remove from front — O(n)!
        print(f"Dequeued: {removed}")
        return removed

    def peek(self):
        if self.is_empty():
            print("Queue is empty!")
            return None
        return self.queue[0]

    def is_empty(self):
        return len(self.queue) == 0

    def size(self):
        return len(self.queue)

    def display(self):
        print("Front ->", self.queue, "<- Rear")


# ======================================
# METHOD 2: Queue using deque (BEST)
# Both enqueue and dequeue are O(1)
# ======================================
class QueueUsingDeque:
    def __init__(self):
        self.queue = deque()

    def enqueue(self, data):
        self.queue.append(data)           # add to rear — O(1)
        print(f"Enqueued: {data}")

    def dequeue(self):
        if self.is_empty():
            print("Queue is empty! Underflow.")
            return None
        removed = self.queue.popleft()    # remove from front — O(1)!
        print(f"Dequeued: {removed}")
        return removed

    def peek(self):
        if self.is_empty():
            print("Queue is empty!")
            return None
        return self.queue[0]

    def is_empty(self):
        return len(self.queue) == 0

    def size(self):
        return len(self.queue)

    def display(self):
        print("Front ->", list(self.queue), "<- Rear")


# ======================================
# METHOD 3: Queue using Linked List
# (Manual — shows deep understanding)
# ======================================
class QNode:
    def __init__(self, data):
        self.data = data
        self.next = None


class QueueLinkedList:
    def __init__(self):
        self.front = None   # points to front node (for dequeue)
        self.rear = None    # points to rear node (for enqueue)
        self._size = 0

    def enqueue(self, data):
        new_node = QNode(data)
        if self.rear is None:           # empty queue
            self.front = self.rear = new_node
        else:
            self.rear.next = new_node   # link to end
            self.rear = new_node        # update rear
        self._size += 1
        print(f"Enqueued: {data}")

    def dequeue(self):
        if self.is_empty():
            print("Queue is empty! Underflow.")
            return None
        removed = self.front.data
        self.front = self.front.next    # move front forward
        if self.front is None:          # queue became empty
            self.rear = None
        self._size -= 1
        print(f"Dequeued: {removed}")
        return removed

    def peek(self):
        if self.is_empty():
            print("Queue is empty!")
            return None
        return self.front.data

    def is_empty(self):
        return self.front is None

    def size(self):
        return self._size

    def display(self):
        current = self.front
        elements = []
        while current:
            elements.append(str(current.data))
            current = current.next
        print("Front -> [" + " -> ".join(elements) + "] <- Rear")


# =======================
# MAIN — Demo & Test
# =======================
if __name__ == "__main__":
    print("=" * 50)
    print("QUEUE DEMO (using deque - recommended)")
    print("=" * 50)
    q = QueueUsingDeque()

    print("\n--- Enqueue operations ---")
    q.enqueue(10)
    q.enqueue(20)
    q.enqueue(30)
    q.enqueue(40)
    q.display()

    print(f"\nPeek (front): {q.peek()}")
    print(f"Size: {q.size()}")

    print("\n--- Dequeue operations ---")
    q.dequeue()
    q.dequeue()
    q.display()

    print(f"\nIs empty? {q.is_empty()}")
    q.dequeue()
    q.dequeue()
    q.dequeue()   # underflow check

    print("\n" + "=" * 50)
    print("QUEUE DEMO (using Linked List)")
    print("=" * 50)
    ql = QueueLinkedList()
    ql.enqueue("A")
    ql.enqueue("B")
    ql.enqueue("C")
    ql.display()
    ql.dequeue()
    ql.display()


"""
EXPECTED OUTPUT:

=== QUEUE DEMO (using deque) ===
Enqueued: 10
Enqueued: 20
Enqueued: 30
Enqueued: 40
Front → [10, 20, 30, 40] ← Rear

Peek (front): 10
Size: 4

--- Dequeue operations ---
Dequeued: 10
Dequeued: 20
Front → [30, 40] ← Rear

Is empty? False
Dequeued: 30
Dequeued: 40
Queue is empty! Underflow.

=== QUEUE DEMO (using Linked List) ===
Enqueued: A, B, C
Front → [A → B → C] ← Rear
Dequeued: A
Front → [B → C] ← Rear
"""

"""
====================================================
SORTING ALGORITHMS — Bubble, Merge, Quick Sort
====================================================

KEY VIVA COMPARISONS:
  Bubble: O(n²) stable, in-place, simple
  Merge:  O(n log n) stable, NOT in-place (O(n) space)
  Quick:  O(n log n) avg, unstable, in-place, fastest in practice
"""


# ============================================================
# 1. BUBBLE SORT — O(n²)
# ============================================================
def bubble_sort(arr):
    """
    Compare adjacent elements, swap if out of order.
    Largest element 'bubbles up' to end each pass.
    
    Stable: YES | In-place: YES
    Best: O(n) | Average: O(n²) | Worst: O(n²)
    """
    arr = arr.copy()  # don't modify original
    n = len(arr)
    
    for i in range(n - 1):            # n-1 passes
        swapped = False
        
        for j in range(n - 1 - i):   # -i because last i elements are sorted
            if arr[j] > arr[j + 1]:  # if out of order
                arr[j], arr[j + 1] = arr[j + 1], arr[j]  # SWAP
                swapped = True
        
        # OPTIMIZATION: if no swaps occurred, array is already sorted
        if not swapped:
            break
    
    return arr


# ============================================================
# 2. MERGE SORT — O(n log n)
# ============================================================
def merge_sort(arr):
    """
    Divide array in half → sort each half → merge them.
    
    Stable: YES | In-place: NO (O(n) extra space)
    Best/Average/Worst: O(n log n)
    """
    if len(arr) <= 1:       # BASE CASE: single element is already sorted
        return arr
    
    # DIVIDE: find midpoint
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])    # recursively sort left half
    right = merge_sort(arr[mid:])   # recursively sort right half
    
    # MERGE: combine sorted halves
    return merge(left, right)


def merge(left, right):
    """
    Merge two sorted arrays into one sorted array.
    The KEY step of merge sort — O(n) time.
    """
    result = []
    i = j = 0
    
    # Compare elements from both halves, pick smaller
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:     # <= keeps it STABLE
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    
    # Add remaining elements (one side will have leftovers)
    result.extend(left[i:])
    result.extend(right[j:])
    
    return result


# ============================================================
# 3. QUICK SORT — O(n log n) average
# ============================================================
def quick_sort(arr, low=None, high=None):
    """
    Choose pivot → partition (smaller left, larger right) → recurse.
    
    Stable: NO | In-place: YES
    Best/Average: O(n log n) | Worst: O(n²) (sorted input, bad pivot)
    """
    arr = arr if low is not None else arr.copy()
    if low is None:
        low = 0
    if high is None:
        high = len(arr) - 1
    
    if low < high:
        # Partition: put pivot in correct position
        pivot_index = partition(arr, low, high)
        
        # Recursively sort elements before and after pivot
        quick_sort(arr, low, pivot_index - 1)
        quick_sort(arr, pivot_index + 1, high)
    
    return arr


def partition(arr, low, high):
    """
    Lomuto Partition Scheme:
    - Choose last element as pivot
    - Place all elements < pivot to the LEFT
    - Place all elements > pivot to the RIGHT
    - Put pivot in its CORRECT final position
    
    Returns the pivot's final index.
    """
    pivot = arr[high]   # choose last element as pivot
    i = low - 1         # i tracks boundary of smaller elements
    
    for j in range(low, high):
        if arr[j] <= pivot:         # if current < pivot
            i += 1                  # expand boundary
            arr[i], arr[j] = arr[j], arr[i]  # swap into smaller region
    
    # Place pivot in correct position
    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    return i + 1  # return pivot's final index


# ============================================================
# HELPER: Print array with step details
# ============================================================
def print_array(arr, label=""):
    print(f"{label}: {arr}")


# ============================================================
# MAIN — Demo & Test All Three
# ============================================================
if __name__ == "__main__":
    
    original = [64, 34, 25, 12, 22, 11, 90]
    
    print("=" * 55)
    print(f"Original Array: {original}")
    print("=" * 55)

    # ---- BUBBLE SORT ----
    print("\n[BUBBLE SORT]")
    print("Logic: Compare adjacent pairs, swap if needed. Repeat.")

    arr = original.copy()
    n = len(arr)
    for i in range(n - 1):
        swapped = False
        for j in range(n - 1 - i):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True
        print(f"  After pass {i+1}: {arr}")
        if not swapped:
            break
    print(f"Sorted: {arr}")

    # ---- MERGE SORT ----
    print("\n[MERGE SORT]")
    print("Logic: Split -> sort halves -> merge")
    result = merge_sort(original)
    print(f"Sorted: {result}")

    # ---- QUICK SORT ----
    print("\n[QUICK SORT]")
    print("Logic: Pick pivot -> partition -> recurse on both sides")
    arr = original.copy()
    result = quick_sort(arr)
    print(f"Sorted: {result}")

    # ---- COMPARISON SUMMARY ----
    print("\n" + "=" * 55)
    print("COMPLEXITY SUMMARY")
    print("=" * 55)
    print(f"{'Algorithm':<15} {'Best':<15} {'Average':<15} {'Worst':<15} {'Space':<10} {'Stable'}")
    print("-" * 85)
    print(f"{'Bubble':<15} {'O(n)':<15} {'O(n²)':<15} {'O(n²)':<15} {'O(1)':<10} {'YES'}")
    print(f"{'Merge':<15} {'O(n log n)':<15} {'O(n log n)':<15} {'O(n log n)':<15} {'O(n)':<10} {'YES'}")
    print(f"{'Quick':<15} {'O(n log n)':<15} {'O(n log n)':<15} {'O(n²)':<15} {'O(log n)':<10} {'NO'}")


"""
VIVA QUICK-FIRE:

Q: How does Bubble Sort work?
A: Compare adjacent elements, swap if arr[j] > arr[j+1]. After each pass,
   the largest element is in its correct position.

Q: Why Bubble Sort O(n²)?
A: Two nested loops: outer (n-1 passes) × inner (n-1-i comparisons) = O(n²)

Q: How does Merge Sort work?
A: Divide array to halves recursively until 1 element, then merge sorted halves.

Q: Why is Merge Sort O(n log n)?
A: log n levels of division × O(n) to merge each level = O(n log n)

Q: Why is Merge Sort NOT in-place?
A: The merge step needs a temporary array to store merged result.

Q: How does Quick Sort work?
A: Pick pivot (usually last element), partition so smaller elements are left
   of pivot and larger are right, then recursively sort both partitions.

Q: When is Quick Sort O(n²)?
A: When pivot is always the smallest/largest (e.g., already sorted array).
   Fix: random pivot selection.

Q: Which sort is fastest in practice?
A: Quick Sort — great cache performance and small constant factors.
"""

"""
====================================================
BINARY SEARCH TREE (BST) — Complete Implementation
====================================================

BST PROPERTY:
  For every node:
    LEFT subtree values < node value
    RIGHT subtree values > node value

OPERATIONS:
  Insert    → O(log n) avg, O(n) worst
  Search    → O(log n) avg, O(n) worst
  Delete    → O(log n) avg, O(n) worst
  Traversal → O(n) always

KEY VIVA: Inorder traversal of BST = SORTED output!
"""


# ============================
# NODE CLASS
# ============================
class BSTNode:
    def __init__(self, data):
        self.data = data
        self.left = None    # left child (smaller values)
        self.right = None   # right child (larger values)


# ============================
# BST CLASS
# ============================
class BST:
    def __init__(self):
        self.root = None

    # --------------------------------------------------
    # INSERT — O(log n) average
    # --------------------------------------------------
    def insert(self, data):
        """Insert data maintaining BST property."""
        if self.root is None:
            self.root = BSTNode(data)
        else:
            self._insert_recursive(self.root, data)
        print(f"Inserted: {data}")

    def _insert_recursive(self, node, data):
        if data < node.data:            # go LEFT for smaller values
            if node.left is None:
                node.left = BSTNode(data)
            else:
                self._insert_recursive(node.left, data)
        elif data > node.data:          # go RIGHT for larger values
            if node.right is None:
                node.right = BSTNode(data)
            else:
                self._insert_recursive(node.right, data)
        else:
            print(f"{data} already exists in BST")

    # --------------------------------------------------
    # SEARCH — O(log n) average
    # --------------------------------------------------
    def search(self, data):
        """Search for data in BST."""
        result = self._search_recursive(self.root, data)
        if result:
            print(f"FOUND: {data}")
        else:
            print(f"NOT FOUND: {data}")
        return result

    def _search_recursive(self, node, data):
        if node is None:                # not found
            return False
        if node.data == data:           # found!
            return True
        elif data < node.data:          # search LEFT subtree
            return self._search_recursive(node.left, data)
        else:                           # search RIGHT subtree
            return self._search_recursive(node.right, data)

    # --------------------------------------------------
    # DELETE — O(log n) average
    # 3 Cases:
    #   1. Leaf node → just delete
    #   2. One child → replace with child
    #   3. Two children → replace with inorder successor
    # --------------------------------------------------
    def delete(self, data):
        """Delete node with given data from BST."""
        self.root = self._delete_recursive(self.root, data)
        print(f"Deleted: {data}")

    def _delete_recursive(self, node, data):
        if node is None:
            return node

        if data < node.data:
            node.left = self._delete_recursive(node.left, data)
        elif data > node.data:
            node.right = self._delete_recursive(node.right, data)
        else:
            # CASE 1: Leaf node (no children)
            if node.left is None and node.right is None:
                return None

            # CASE 2: One child
            elif node.left is None:
                return node.right
            elif node.right is None:
                return node.left

            # CASE 3: Two children
            # Find inorder successor (smallest in right subtree)
            successor = self._find_min(node.right)
            node.data = successor.data          # copy successor value
            node.right = self._delete_recursive(node.right, successor.data)  # delete successor

        return node

    def _find_min(self, node):
        """Find minimum node (leftmost node)."""
        while node.left:
            node = node.left
        return node

    def _find_max(self, node):
        """Find maximum node (rightmost node)."""
        while node.right:
            node = node.right
        return node

    # --------------------------------------------------
    # TRAVERSALS — O(n) all
    # --------------------------------------------------
    def inorder(self):
        """Left → Root → Right. Gives SORTED output for BST!"""
        result = []
        self._inorder_recursive(self.root, result)
        print(f"Inorder  (sorted): {result}")
        return result

    def _inorder_recursive(self, node, result):
        if node:
            self._inorder_recursive(node.left, result)   # left
            result.append(node.data)                      # root
            self._inorder_recursive(node.right, result)  # right

    def preorder(self):
        """Root → Left → Right. Used for copying tree."""
        result = []
        self._preorder_recursive(self.root, result)
        print(f"Preorder  (copy):  {result}")
        return result

    def _preorder_recursive(self, node, result):
        if node:
            result.append(node.data)                       # root FIRST
            self._preorder_recursive(node.left, result)    # left
            self._preorder_recursive(node.right, result)   # right

    def postorder(self):
        """Left → Right → Root. Used for deletion."""
        result = []
        self._postorder_recursive(self.root, result)
        print(f"Postorder (delete):{result}")
        return result

    def _postorder_recursive(self, node, result):
        if node:
            self._postorder_recursive(node.left, result)   # left
            self._postorder_recursive(node.right, result)  # right
            result.append(node.data)                       # root LAST

    # --------------------------------------------------
    # LEVEL ORDER (BFS) — uses a Queue
    # --------------------------------------------------
    def level_order(self):
        """Level by level traversal using a Queue (BFS)."""
        if not self.root:
            return
        from collections import deque
        queue = deque([self.root])
        result = []
        while queue:
            node = queue.popleft()
            result.append(node.data)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        print(f"Level Order (BFS): {result}")
        return result

    # --------------------------------------------------
    # UTILITY: Height of tree
    # --------------------------------------------------
    def height(self):
        return self._height(self.root)

    def _height(self, node):
        if node is None:
            return 0
        return 1 + max(self._height(node.left), self._height(node.right))

    # --------------------------------------------------
    # UTILITY: Print tree visually
    # --------------------------------------------------
    def display(self):
        print("\nBST Structure:")
        self._print_tree(self.root, "", True)
        print()

    def _print_tree(self, node, indent, is_right):
        if node is not None:
            self._print_tree(node.right, indent + ("   " if is_right else "|  "), True)
            print(indent + ("+-- " if is_right else "+-- ") + str(node.data))
            self._print_tree(node.left, indent + ("   " if is_right else "|  "), False)


# =======================
# MAIN — Demo & Test
# =======================
if __name__ == "__main__":
    bst = BST()

    print("=" * 50)
    print("BST DEMO")
    print("=" * 50)

    # Insert elements
    print("\n--- Insertions ---")
    for val in [50, 30, 70, 20, 40, 60, 80, 35, 45]:
        bst.insert(val)

    """
    BST after insertions:
            50
           /  \
          30   70
         / \   / \
        20  40 60  80
           / \
          35  45
    """

    bst.display()
    print(f"Tree Height: {bst.height()}")

    # Traversals
    print("\n--- Traversals ---")
    bst.inorder()      # Should be sorted: 20,30,35,40,45,50,60,70,80
    bst.preorder()
    bst.postorder()
    bst.level_order()

    # Search
    print("\n--- Search ---")
    bst.search(40)     # Found
    bst.search(99)     # Not found

    # Delete
    print("\n--- Deletions ---")
    bst.delete(20)     # Delete leaf
    bst.inorder()

    bst.delete(30)     # Delete node with two children
    bst.inorder()

    bst.display()


"""
VIVA QUICK-FIRE:

Q: What is BST property?
A: Left child < parent < right child, for every node.

Q: Inorder traversal of BST gives?
A: Sorted (ascending) output — this is how BST sort works!

Q: Time complexity of BST operations?
A: Average O(log n), Worst O(n) when unbalanced (like a linked list).

Q: What is the inorder successor?
A: The smallest node in the right subtree — used when deleting a node with 2 children.

Q: Difference between BST and Binary Tree?
A: BST has the ordering property (left < root < right). Binary Tree has no such constraint.

Q: When does BST become O(n)?
A: When all elements inserted in sorted order → tree becomes a linked list.
   Solution: Use balanced trees (AVL, Red-Black).

Q: Three deletion cases in BST?
A: 1) Leaf: just delete. 2) One child: replace with child. 
   3) Two children: replace with inorder successor.

Q: What is the height of a balanced BST with n nodes?
A: O(log n)
"""

Generated for exam victory. You've got this! 🚀