⚡ CCSU Meerut · BCA 3rd Semester · Exam Preparation
Data Structure Using C & C++ BCA-302 Most Important Questions & Solved Exam Notebook
Master chapter-wise solved notebook of recurring CCSU examination questions (2018–2021) for Data Structure Using C & C++ (BCA-302) with complete working C/C++ code, visual SVG diagrams (B-Tree, BST, Heap, Traversals), stack trace tables, and Big-O complexity analysis.
Very Short Answer Questions & Core Definitions
CCSU Examination Blueprint: 5 Questions Compulsory • Total 15 Marks
Q1. What do you understand by Data Structure? State its classification.
A Data Structure is a programmatic way of storing, organizing, and managing data in computer memory so that operations (such as search, insertion, and deletion) can be performed efficiently.
Classification:
- Primitive: Fundamental data types supported directly by hardware and compilers (e.g.,
int,char,float,pointer). - Non-Primitive: Structured data collections derived from primitive types:
- Linear: Elements arranged sequentially in a 1-to-1 relationship (e.g., Arrays, Stacks, Queues, Linked Lists).
- Non-Linear: Elements arranged hierarchically or arbitrarily in a 1-to-many or many-to-many relationship (e.g., Trees, Graphs).
Q2. What are AVL Trees? State the Balance Factor condition.
An AVL Tree (named after inventors G.M. Adelson-Velsky and E.M. Landis) is a height-balanced Binary Search Tree (BST) wherein the heights of the two child subtrees of any node differ by at most one.
$$ ext{Balance Factor (BF)} = ext{Height}( ext{Left Subtree}) - ext{Height}( ext{Right Subtree})$$For an AVL tree to remain valid, every node must satisfy \( ext{BF} \in \{-1, 0, +1\}\). If insertion or deletion causes \( ext{BF} = \pm 2\), the tree is re-balanced via single rotations (LL, RR) or double rotations (LR, RL) to guarantee strictly \(O(\log n)\) search, insertion, and deletion times.
Q3. What is an Array? Explain its major practical limitations.
An Array is a linear, sequential collection of homogeneous data elements stored in contiguous memory locations, allowing instant direct access using index arithmetic: \( ext{Address}(A[i]) = ext{Base} + i imes w\).
Limitations:
- Fixed Static Size: Array dimension must be fixed at compile-time and cannot dynamically expand or shrink according to runtime demand.
- Costly Insertion & Deletion: Inserting or removing an element at position \(K\) requires shifting elements left or right, resulting in \(O(n)\) time overhead.
- Memory Fragmentation: Requires a single contiguous block of RAM, which may fail even if total free memory across fragments exceeds array size.
Q4. State four prominent real-world applications of Stacks.
- Expression Parsing & Evaluation: Converting Infix expressions to Postfix/Prefix and computing arithmetic expressions using a single-pass operand stack.
- Subroutine / Function Call Management: CPU call stack stores activation records (return address, local variables, parameters) for nested and recursive functions.
- Delimiters & Parenthesis Matching: Compilers check balanced brackets
(),{},[]in programming source code. - Undo / Redo & Backtracking: Text editors use two stacks for Undo/Redo; web browsers maintain back/forward URL navigation stacks.
Q5. Define Circular Linked List and Chain.
- Circular Linked List: A variation of a linked list in which the last node does not contain a
NULLpointer; instead, its link field points back to the first node (head), forming a continuous circular loop. Traversal can begin from any node and loop infinitely. - Chain: A formal term used in data structures for a singly linked linear list where each node consists of a data field and a pointer pointing strictly to its linear successor, with the terminal node pointing to
NULL.
Q6. What is the advantage of a Header Node in a Linked List?
A Header Node (or sentinel node) is a dummy node placed at the beginning of a linked list before the first actual data node.
- Eliminates Edge Case Code: In standard lists, inserting or deleting the first node requires modifying the external
headpointer. With a header node, the head pointer remains permanent, so insertion/deletion code at the beginning uses the exact same logic as at the middle. - Metadata Storage: The header node's data field can store list-wide attributes, such as total count of nodes, sum of elements, or creation date.
Q7. Define Stacks and Queues with an example of each.
- Stack: A linear data structure that adheres to the LIFO (Last In First Out) principle. Insertion and deletion occur only at a single end termed
TOP. Real-world example: A stack of dinner plates in a cafeteria; the plate placed last is washed first. - Queue: A linear data structure that follows the FIFO (First In First Out) rule. Elements are inserted at the
REARand deleted from theFRONT. Real-world example: People standing in line at a cinema ticket counter; the first person to arrive gets the ticket first.
Q8. How is a Binary Tree traversed in C language? State the three orders.
Binary tree traversal visits every node in the tree exactly once. In C, it is implemented cleanly via recursive pointer calls:
- Inorder (LNR): Traverse Left Subtree → Visit Root Node → Traverse Right Subtree. (Produces elements in sorted order for a BST).
- Preorder (NLR): Visit Root Node → Traverse Left Subtree → Traverse Right Subtree. (Used to create copies or prefix expressions).
- Postorder (LRN): Traverse Left Subtree → Traverse Right Subtree → Visit Root Node. (Used to delete trees or evaluate postfix expressions).
Q9. What is the basic concept of Insertion Sorting?
Insertion Sort works similarly to sorting playing cards in our hands. The array is virtually split into a sorted part and an unsorted part.
In each pass \(i\) (from \(1\) to \(n-1\)), the next element from the unsorted subarray is picked as key and compared backwards with elements in the sorted subarray. All elements greater than key are shifted right by one position, and key is placed into its correct sorted slot. Time Complexity: Best case \(O(n)\) (already sorted), Worst/Average case \(O(n^2)\).
Q10. Explain the primary operations performed on Data Structures.
- Traversing: Accessing each data element in the structure exactly once to process or display it.
- Insertion: Adding a new data element at a designated position in the structure.
- Deletion: Removing an existing element from the structure and freeing memory.
- Searching: Finding the location of a target element with a specified key value.
- Sorting: Arranging all elements in a logical ascending or descending sequence.
- Merging: Combining elements of two sorted structures into a single consolidated sorted structure.
Q11. How can we minimize Stack Overflow?
Stack Overflow occurs when an attempt is made to push an element onto a stack that has exhausted its memory capacity.
Techniques to Minimize Overflow:
- Dynamic Linked List Implementation: Implement the stack using a linked list instead of a fixed array, allowing the stack to grow dynamically as long as system heap memory is available.
- Dynamic Array Resizing: In array implementations, dynamically double the array size (using
reallocin C orstd::vectorin C++) whenever the stack becomes full. - Avoid Unbounded Recursion: Convert deep recursion into iterative loops using explicit loops or guarantee strict termination base cases.
- Two Stacks in One Array: Grow two stacks from opposite ends (0 and \(N-1\)) of a single shared array, avoiding overflow until the total memory is exhausted.
Q12. Write Prefix and Postfix form for: \(A + B imes (C - D) / (E - F)\)
1. Parentheses first: \((C - D)\) and \((E - F)\):
- Postfix: \(CD-\) • Prefix: \(-CD\)
- Postfix: \(EF-\) • Prefix: \(-EF\)
2. Multiplication: \(B imes (C - D)\):
- Postfix: \(B(CD-)* \implies BCD-*\) • Prefix: \(*B(-CD) \implies *B-CD\)
3. Division: \([B imes (C - D)] / (E - F)\):
- Postfix: \((BCD-*)(EF-)/ \implies BCD-*EF-/\) • Prefix: \(/*B-CD-EF\)
4. Addition: \(A + ext{Result}\):
Final Postfix: ABCD-*EF-/+
Final Prefix: +A/*B-CD-EF
Q13. Design a recursive factorial function using C/C++ language.
// Recursive Factorial Function
long long factorial(int n) {
// Base Case: 0! = 1 and 1! = 1
if (n <= 1) {
return 1;
}
// Recursive Step: n! = n * (n-1)!
return n * factorial(n - 1);
}
Time Complexity: \(O(n)\), Space Complexity: \(O(n)\) for call stack frames.
Q14. Explain the term Hashing and state common Hash Functions.
Hashing is a technique to map key values to specific slots in an array (Hash Table) to achieve average \(O(1)\) search, insertion, and deletion time without comparison.
Common Hash Functions:
- Division Method: \(h(k) = k \bmod m\), where \(m\) is table size (preferably prime).
- Mid-Square Method: Square the key \(k^2\) and extract the middle \(r\) digits.
- Folding Method: Divide the key into equal-sized pieces and sum them up.
Q15. What is a Deque? Distinguish Input-Restricted and Output-Restricted Deque.
A Deque (Double-Ended Queue) is a linear list allowing insertion and deletion at both ends (Front and Rear).
| Feature | Input-Restricted Deque | Output-Restricted Deque |
|---|---|---|
| Insertion | Only at one end (Rear) | At both ends (Front and Rear) |
| Deletion | At both ends (Front and Rear) | Only at one end (Front) |
Q16. What is Analysis of Algorithm? Explain Time and Space Complexity.
Analysis of Algorithm is the process of determining the amount of computational resources (time and storage) required by an algorithm to execute as a function of the input size \(n\).
- Time Complexity: The total number of elementary operations or CPU cycles executed by the algorithm as input size increases, expressed using Asymptotic Notations: Big-O (\(O\)), Omega (\(\Omega\)), and Theta (\(\Theta\)).
- Space Complexity: The amount of primary memory (RAM) consumed by the program during execution, consisting of: $$ ext{Total Space} = ext{Fixed Space (code + constants)} + ext{Variable Space (dynamic data + recursion stack)}$$
Q17. Explain the Principle of Recursion with its two essential components.
Recursion is a problem-solving technique wherein a function calls itself directly or indirectly to solve a smaller instance of the same problem.
Two Mandatory Components:
- Base Case (Anchor Condition): A terminating condition for which the function produces a direct result without making any further recursive calls. Without this, the program encounters an infinite recursion loop and crashes with Stack Overflow.
- Recursive Step (Inductive Step): The instruction that breaks down the original input and invokes the function with a strictly smaller or simpler parameter (e.g., \(n-1\)), ensuring the execution moves closer to the base case at every step.
Algorithmic Procedures & Code Implementations
CCSU Examination Blueprint: Attempt Any 2 Out of 3 Questions • Total 15 Marks
Q1. Write the step-by-step algorithm to delete an element from a linear array at index \(K\).
Algorithm: DELETE_ARRAY(LA, N, K, ITEM)
- [Check Underflow]: If \(N == 0\), Print "Array Underflow: No element to delete" and Exit.
- [Validate Range]: If \(K \lt 0\) or \(K \ge N\), Print "Error: Index out of range" and Exit.
- [Store Target Item]: Set
ITEM = LA[K]. - [Shift Leftward]: Repeat for \(I = K\) to \(N - 2\):
SetLA[I] = LA[I + 1].
[End of loop] - [Update Size]: Set \(N = N - 1\).
- [Exit]: Return
ITEM.
Complexity: Best case \(O(1)\) when deleting last element (\(K = N-1\)). Worst case \(O(n)\) when deleting first element (\(K = 0\)).
Q2. Write an algorithm and its C syntax to insert an element at the \(K\)th position into a linear array.
Algorithm: INSERT_ARRAY(LA, N, MAX, K, ITEM)
- [Check Overflow]: If \(N \ge \text{MAX}\), Print "Array Overflow" and Exit.
- [Shift Rightward]: Repeat for \(I = N - 1\) down to \(K\):
SetLA[I + 1] = LA[I].
[End of loop] - [Insert]: Set
LA[K] = ITEM. - [Increment]: Set \(N = N + 1\).
// C Implementation
void insertAtK(int arr[], int *n, int max_size, int k, int item) {
if (*n >= max_size) {
printf("Overflow!\\n");
return;
}
for (int i = *n - 1; i >= k; i--) {
arr[i + 1] = arr[i];
}
arr[k] = item;
(*n)++;
}
Q3. Write a recursive C/C++ function to count the number of leaves in a Binary Tree.
struct Node {
int data;
Node* left;
Node* right;
};
// Returns total leaf nodes in binary tree
int countLeaves(Node* root) {
// Base Case 1: Empty tree
if (root == nullptr)
return 0;
// Base Case 2: Node is a leaf
if (root->left == nullptr && root->right == nullptr)
return 1;
// Recursive Step
return countLeaves(root->left) + countLeaves(root->right);
}
Time Complexity: \(O(n)\) visiting all nodes. Space Complexity: \(O(h)\) where \(h\) is tree height.
Q4. Write a function to reverse a stack using only standard Push and Pop operations (without auxiliary stack).
#include <stack>
using namespace std;
// Helper: Inserts an element at the bottom of a stack
void insertAtBottom(stack<int>& s, int item) {
if (s.empty()) {
s.push(item);
return;
}
int topItem = s.top();
s.pop();
insertAtBottom(s, item);
s.push(topItem);
}
// Function to reverse the stack recursively
void reverseStack(stack<int>& s) {
if (s.empty())
return;
int item = s.top();
s.pop();
reverseStack(s);
insertAtBottom(s, item);
}
This utilizes the implicit call stack to store popped elements and places them sequentially at the bottom.
Q5. What is a Sparse Matrix? Explain its memory representation and derive the Lower Triangular 1D address formula.
A matrix is Sparse if the number of zero elements is substantially greater than the number of non-zero elements. Storing it as a standard 2D array \(A[N][N]\) wastes memory.
1. 3-Tuple Representation: Stored as a list of triplets: [Row, Col, Value].
2. Lower Triangular Matrix (LTM): \(A[i][j] = 0\) for \(i \lt j\). Total non-zero elements = \(\frac{N(N+1)}{2}\).
In Row-Major storage in a 1D array:
- Number of elements in rows preceding row \(i\): \(1 + 2 + 3 + \dots + i = \frac{i(i+1)}{2}\).
- Within row \(i\), column offset is \(j\) (for \(0 \le j \le i\)).
Q6. Explain Double-Ended Queue (Deque) operations with a suitable example.
Implemented circularly using an array of capacity \(M\):
insertFront(item):front = (front - 1 + M) % M;arr[front] = item;insertRear(item):rear = (rear + 1) % M;arr[rear] = item;deleteFront(): Retrievearr[front];front = (front + 1) % M;deleteRear(): Retrievearr[rear];rear = (rear - 1 + M) % M;
All operations take strictly \(O(1)\) time without shifting elements.
Q7. Write an algorithm to delete the last node from a Singly Linked List.
- If
HEAD == NULL, Print "Underflow: List Empty" and Return. - If
HEAD->next == NULL, SetTEMP = HEAD,HEAD = NULL,free(TEMP), and Return. - Set
PTR = HEAD. - While
PTR->next->next != NULLdo:
SetPTR = PTR->next.
[End While] - Set
TEMP = PTR->next. - Set
PTR->next = NULL. - Call
free(TEMP)to release memory.
Q8. Write a C/C++ program to multiply two matrices \(A\) and \(B\).
#include <iostream>
using namespace std;
void multiplyMatrices(int A[10][10], int B[10][10], int C[10][10], int r1, int c1, int r2, int c2) {
if (c1 != r2) {
cout << "Matrix multiplication not possible! Columns of A must equal rows of B.\\n";
return;
}
// Initialize resultant matrix to 0
for (int i = 0; i < r1; i++) {
for (int j = 0; j < c2; j++) {
C[i][j] = 0;
for (int k = 0; k < c1; k++) {
C[i][j] += A[i][k] * B[k][j];
}
}
}
}
Three nested loops yield Time Complexity \(O(r_1 \times c_1 \times c_2) \implies O(n^3)\) for square matrices.
Q9. Explain Priority Queue with an example of real-life application.
A Priority Queue is an abstract data type where each element has an associated priority. Elements are served based on priority: an element with higher priority is processed before an element with lower priority, regardless of arrival order.
- Ascending Priority Queue: Smallest key has the highest priority (e.g., Shortest Job First).
- Descending Priority Queue: Largest key has the highest priority.
Real-Life Applications: OS CPU Process Scheduling (higher priority system processes pre-empt lower priority background tasks), Hospital Emergency Rooms (triage priority for critical patients), Dijkstra's Shortest Path Algorithm, and Huffman Data Compression.
Q10. Write the procedure to delete an element from a Linked Queue.
- [Check Underflow]: If
FRONT == NULL, Print "Queue Underflow" and Return. - [Point to Front Node]: Set
TEMP = FRONT. - [Retrieve Data]: Set
ITEM = TEMP->data. - [Advance Front]: Set
FRONT = FRONT->next. - [Check for Empty Queue]: If
FRONT == NULL, then setREAR = NULL. - [Free Memory]: Call
free(TEMP). - [Return]: Return
ITEM. Time Complexity is \(O(1)\).
Comprehensive Long Answer Solutions & Visual Diagrams
CCSU Examination Blueprint: Attempt Any 3 Out of 5 Questions • Total 45 Marks
Q1. Explain the Stack Evaluation Algorithm for Postfix expressions. Show the complete step-by-step stack status trace table for: 3, 1, +, 2, ^, 7, 4, -, 2, *, +, 5, - and ABC*DEF$/-G+H*-
Evaluation Algorithm:
- Scan the Postfix string from left to right, one token at a time.
- If the scanned token is an operand (number or letter),
PUSHit onto the stack. - If the token is an operator \(\odot\):
POPthe top element \( o ext{Operand}_2\).POPthe next top element \( o ext{Operand}_1\).- Evaluate \( ext{Result} = ext{Operand}_1 \odot ext{Operand}_2\).
PUSHthe \( ext{Result}\) back onto the stack.
- When scanning completes, the value remaining in the stack is the final result.
Trace Table for: 3, 1, +, 2, ^, 7, 4, -, 2, *, +, 5, -
| Step | Token | Operation / Computation | Stack Status [Bottom → Top] |
|---|---|---|---|
| 1 | 3 | Push 3 | [3] |
| 2 | 1 | Push 1 | [3, 1] |
| 3 | + | Pop 1, 3 → 3 + 1 = 4 → Push 4 | [4] |
| 4 | 2 | Push 2 | [4, 2] |
| 5 | ^ | Pop 2, 4 → 4^2 = 16 → Push 16 | [16] |
| 6 | 7 | Push 7 | [16, 7] |
| 7 | 4 | Push 4 | [16, 7, 4] |
| 8 | - | Pop 4, 7 → 7 - 4 = 3 → Push 3 | [16, 3] |
| 9 | 2 | Push 2 | [16, 3, 2] |
| 10 | * | Pop 2, 3 → 3 * 2 = 6 → Push 6 | [16, 6] |
| 11 | + | Pop 6, 16 → 16 + 6 = 22 → Push 22 | [22] |
| 12 | 5 | Push 5 | [22, 5] |
| 13 | - | Pop 5, 22 → 22 - 5 = 17 → Push 17 | [17] (Final Result) |
Final Computed Value: \(\mathbf{17}\)
Q2. Write programming code in C/C++ to create, insert, delete, and print in reverse order for a Singly Linked List. Distinguish Singly vs Doubly Linked List with diagram.
Visual Diagram 1: Singly Linked List vs Doubly Linked List Architecture
#include <iostream>
using namespace std;
struct Node {
int data;
Node* next;
Node(int val) : data(val), next(nullptr) {}
};
// Function to print a linked list in reverse order (Dec 2018 Q12)
void printReverse(Node* head) {
if (head == nullptr) return;
printReverse(head->next); // Recurse on remaining list first
cout << head->data << " "; // Print node after returning
}
Q3. Given Inorder = ABCEDFGHI and Preorder = ICBADEFGH. Reconstruct the unique Binary Tree, derive its Postorder Traversal, and state the algorithm.
Subtree Derivation:
- Preorder[0] =
Iis the Root. - In Inorder
ABCEDFGHI,Iis at index 8 (the very end). Hence, the Right Subtree is EMPTY, and all 8 nodesABCEDFGHform the Left Subtree. - Next Preorder symbol is
C→ Root of the left subtree. In Inorder, nodes left ofCareAB, and right ofCareEDFGH. - For
AB: Preorder isB, A→Bis root,Ais its left child. - For
EDFGH: Preorder isD, E, F, G, H→Dis root,Eis left child,Fis right child;Gis right child ofF, andHis right child ofG.
Visual Diagram 2: Reconstructed Binary Tree from Preorder & Inorder
Derived Postorder Traversal (LRN):
A → B → E → H → G → F → D → C → I
Q4. Explain BST Insertion and Deletion algorithms. Construct a Binary Search Tree (BST) for the numbers: 14, 15, 4, 9, 7, 18, 3, 5, 16, 20, 17
BST Property: For every node \(X\), all values in its left subtree are \(\lt X\), and all values in its right subtree are \(\gt X\).
Visual Diagram 3: Constructed Binary Search Tree
Q5. State properties of B-Trees. Construct a B-Tree of order 3 for following data: Jan, Feb, Mar, Apr, May, Jun, Jul, Aug, Sep, Oct, Nov, Dec
B-Tree of Order \(m = 3\) Rules:
- Maximum keys per node = \(m - 1 = 2\). Maximum children = \(m = 3\).
- Minimum keys per non-root node = \(\lceil m/2 ceil - 1 = 1\).
- All leaves must be at the exact same level.
- When inserting into a full 2-key node, it splits: the median (middle) key is promoted to the parent.
Visual Diagram 4: Final B-Tree of Order 3 for 12 Months
Q6. Construct a Max-Heap for the given data: 95, 13, 12, 71, 96, 10, 62, 43, 35, 38. Show its 1D array representation and Heap Sort mechanism.
Max-Heap Property: \( ext{A}[ ext{parent}(i)] \ge ext{A}[i]\) for all nodes \(i\).
Visual Diagram 5: Final Max-Heap Tree & 1D Sequential Array Mapping
Q7. Design a function CINSERT and CDELETE for static implementation of a Circular Queue. Illustrate with a circular ring diagram.
Visual Diagram 6: Circular Queue Ring Architecture (Capacity = 8)
#define MAX 8
int cqueue[MAX];
int front = -1, rear = -1;
// Function CINSERT
void cinsert(int val) {
if ((front == 0 && rear == MAX - 1) || (front == (rear + 1) % MAX)) {
cout << "Circular Queue Overflow!\n";
return;
}
if (front == -1) { // First element
front = rear = 0;
} else {
rear = (rear + 1) % MAX;
}
cqueue[rear] = val;
}
// Function CDELETE
int cdelete() {
if (front == -1) {
cout << "Circular Queue Underflow!\n";
return -1;
}
int item = cqueue[front];
if (front == rear) { // Last remaining element
front = rear = -1;
} else {
front = (front + 1) % MAX;
}
return item;
}
Q8. Describe Hashing and various Hashing techniques in detail. Explain Open Addressing (Linear Probing) vs Separate Chaining with numeric example.
Collision: Occurs when two distinct keys \(k_1 eq k_2\) produce the same hash index: \(h(k_1) = h(k_2)\).
1. Open Addressing (Closed Hashing): All elements are stored directly inside the hash table array slots. When a collision occurs, alternative slots are probed systematically:
- Linear Probing: \(h(k, i) = (h'(k) + i) \bmod m\). Simple but suffers from Primary Clustering.
- Quadratic Probing: \(h(k, i) = (h'(k) + c_1 i + c_2 i^2) \bmod m\). Eliminates primary clustering.
- Double Hashing: \(h(k, i) = (h_1(k) + i \cdot h_2(k)) \bmod m\). Best open addressing scheme.
2. Separate Chaining (Open Hashing): Each table slot is a header pointer to a linked list of records that hash to the same index. Infinite keys can be accommodated as long as RAM allows, completely eliminating primary clustering.
Q9. (a) Perform Quick Sort on: 66, 35, 48, 55, 62, 77, 25, 38, 18, 40, 30, 20 (b) Derive Time Complexity of Bubble Sort.
(a) Quick Sort Partition Trace: Pivot chosen as first element \( ext{Pivot} = 66\). Pointers low scans right for element \(> 66\) (finds 77), and high scans left for element \(\le 66\) (finds 20). Swap 77 and 20. Continue until pointers cross, then swap pivot into place. Partition divides array into: \(\{ ext{Elements } \le 66\}\) • \(\mathbf{66}\) • \(\{ ext{Elements } > 66\}\).
(b) Bubble Sort Time Complexity Derivation:
- Pass 1: \(n - 1\) comparisons
- Pass 2: \(n - 2\) comparisons
- Pass \(n-1\): \(1\) comparison
With an early termination flag checking if any swap occurred, Best-Case time complexity drops to \(\mathbf{O(n)}\).
Q10. Differentiate between Linear Search and Binary Search. Give complete code and comparative analysis.
| Parameter | Linear Search | Binary Search |
|---|---|---|
| Pre-condition | None; works on unsorted arrays | Array MUST be sorted |
| Worst Time Complexity | \(O(n)\) | \(O(\log n)\) |
| Approach | Sequential element-by-element scan | Divide & conquer (halving search interval) |
| Data Structure Support | Arrays and Linked Lists | Arrays only (requires \(O(1)\) random access) |
Q11. What is a Threaded Binary Tree? Explain with a diagram how NULL pointers are utilized. Why is Doubly Linked List better than Singly Linked List?
In a standard binary tree with \(n\) nodes, exactly \(n + 1\) child pointers are NULL, wasting more than half of the pointer storage. A Threaded Binary Tree reclaims these wasted NULL pointers to store direct links (threads) to the node's Inorder Predecessor and Inorder Successor, allowing stack-free, non-recursive tree traversals.
Visual Diagram 7: Two-Way Threaded Binary Tree (Dashed Arrows = Threads)
Why Doubly Linked List is Superior to Singly Linked List:
- Bi-directional Traversal: Nodes can be traversed in both forward (Next) and backward (Prev) directions.
- Constant Time Deletion \(O(1)\): To delete a node given its pointer, a doubly linked list can immediately access its predecessor via
node->prevwithout scanning fromhead, completing deletion in \(O(1)\) instead of \(O(n)\). - Easier Node Insertion: Inserting before a given node is straightforward with
prevpointer.