৪৯তম বিসিএস ⎯ কম্পিউটার সায়েন্স (CSE) [৯৭১]

Answer: C
Explanation: In a binary tree, a node can have atmost 2 nodes (i.e.) 0,1 or 2 left and right child.

A binary tree is a hierarchical data structure in which each node has at most two children: a left child and a right child. The topmost node is called the root.
A node with no children is called a leaf.
The height of a tree is the number of edges on the longest path from the root to a leaf.

Binary trees can be:
Full Binary Tree: Every node has 0 or 2 children.
Complete Binary Tree: All levels are filled except possibly the last, which is filled from left to right.
Perfect Binary Tree: All internal nodes have 2 children, and all leaves are at the same depth.
Balanced Binary Tree: The height difference between left and right subtrees of every node is at most 1

Answer: C

Explanation:
Convention: height of Single node tree = height 0 
Empty tree = height -1.

Full Binary Tree: is a special type of binary tree in which every parent node/internal node has either 2 or 0 children.

Perfect Binary Tree is a type of binary tree in which every internal node has exactly two child nodes and all the leaf nodes are at the same level.
A complete binary tree is just like a full binary tree, but with two major differences
Every level must be completely filled
All the leaf elements must lean towards the left.
The last leaf element might not have a right sibling i.e. a complete binary tree doesn't have to be a full binary tree.

Properties of a BST:
For every node:
All values in the left subtree are less than the node’s value.
All values in the right subtree are greater than the node’s value.
Both the left and right subtrees of a node are also BSTs.
Example:
        10
       /  \
      5    15
     / \     \
    2   7     20

Left of 10 → {5, 2, 7} are all less than 10.
Right of 10 → {15, 20} are all greater than 10.

A binary tree is a tree data structure in which each parent node can have at most two children. Each node of a binary tree consists of three items:
1.data item
2.address of left child
3.address of right child

Binary Tree Applications

1. For easy and quick access to data
2. In router algorithms
3. To implement heap data structure
4. Syntax tree

Properties of a BST:
For every node:
All values in the left subtree are less than the node’s value.
All values in the right subtree are greater than the node’s value.
Both the left and right subtrees of a node are also BSTs.
No duplicate value

Example:
        10
       /  \
      5    15
     / \     \
    2   7     20

Left of 10 → {5, 2, 7} are all less than 10.
Right of 10 → {15, 20} are all greater than 10.

In BST, left subtree values are strictly less than the node, and right subtree values are greater → (B).
An inorder traversal (Left → Root → Right) always produces a sorted sequence → (C).

Example:
        10
       /  \
      5    15
     / \     \
    2   7     20

Left of 10 → {5, 2, 7} are all less than 10.
Right of 10 → {15, 20} are all greater than 10.

Answer: B

In a balanced BST, search complexity is O(log n) (like binary search).
In a skewed BST (all nodes in a line), search degrades to O(n).

Answer: C
Inorder traversal (Left → Root → Right) visits nodes in increasing order of keys in a BST.Example:
        10
       /  \
      5    15
     / \     \
    2   7     20
2→ 5→ 7→ 10→ 15→ 20

In a pre-order traversal, the very first node visited is always the root. 
 pre-order sequence is: A, B, C, D, E, F, G, H, I
So the root must be A.

Here,
In-Order Traversal: C, D, B, F, E, A, H, I, G
Pre-Order Traversal: A, B, C, D, E, F, G, H, I

In a pre-order traversal, the very first node visited is always the root. So the root must be A.
In-Order Traversal sequence is Left→ Root→ Right
hence A is the root then nodes of Left subtree will be→C, D, B, F, E

So answer is D

Answer: B
If we insert: 1, 2, 3, 4, 5

A skewed binary tree is a pathological/degenerate tree in which the tree is either dominated by the left nodes or the right nodes. Thus, there are two types of skewed binary tree: left-skewed binary tree and right-skewed binary tree.

Answer: A 
Explanation: Inorder traversal gives elements in sorted order.
Inorder traversal (Left → Root → Right) visits nodes in increasing order of keys in a BST.Example:
        10
       /  \
      5    15
     / \     \
    2   7     20
2→ 5→ 7→ 10→ 15→ 20

Answer: B ) 3
In a full binary tree, each non-leaf node has exactly 2 children.
A tree with height h can have at most 2^h leaf nodes.
For L leaves, the minimum possible height is:
h_min⁡=⌈log⁡₂(L)⌉
Here, L=7 then h_min⁡=⌈log_⁡2(7)⌉=2.807=3
So, the tree must have height = 3 (i.e., 4 levels including the root ,Level=h+1).

Answer: B 
Explanation: Max element is always at the rightmost leaf in a BST.

Answer: A) 

To reconstruct a tree uniquely, we need in-order plus either pre-order or post-order.
Pre-order gives the root first, and in-order divides nodes into left and right subtrees.
In-order + Post-order also works, but in-order + Pre-order is the most common.
Pre-order + Post-order cannot uniquely reconstruct (example: skewed trees).

Answer B

A complete binary tree is filled level by level, left to right.
Height = 3 → number of levels =h+1= 3+1= 4.
Maximum nodes in height h = 2^h+1−1=2⁴−1=15
Minimum nodes = last level has at least 1 node →2^h= 2³=8
So, Min = 8, Max = 15.

Answer: B

In a BST:
In-order traversal → always sorted ascending. ( left→ root → right)
Given sequence is not sorted.
Check pre-order:
Root = 10, then left subtree = {5, 1, 7}, right subtree = {40, 50}.
Sequence fits pre-order pattern (root → left → right).
Post-order traversal (left → right→ root).

Answer:  B
here, Pre-order: A, B, D, E, C, F  that means Root=A
         In-order: D, B, E, A, C, F that means left sub tree is( D, B, E) and  right sub tree is( C, F)
Construct tree →

 Leaves are D, E, F → 3 leaves (having no child)

Answer: C

A perfect binary tree is a type of binary tree in which every internal node has exactly two child nodes and all the leaf nodes are at the same level. Perfect tree → half the nodes are leaves.
Formula:
Leaves = (n + 1)/2 = (31+1)/2 = 16.

Answer:  A 

Post-order traversal (left → right→ root ) it ends with root → A.
Left subtree (D, E, B), Right subtree (F, C).
Pre-order is (root → left → right) = A, B, D, E, C, F.

Answer: C) 60
Deletion of node with 2 children → replace with in-order successor (smallest in right subtree).
Right subtree root = 70, smallest node = 60.

Answer: B

Perfect binary tree = all internal nodes have 2 children & all leaves are at same level.
Hence both full (every node has 0/2 children) and complete (all levels filled). 

Answer: B

A binary heap is a complete binary tree (all levels filled except possibly the last, filled from left to right).

Answer: D

In Max-Heap, each parent’s value is greater than or equal to its children.
Conversely, Min-Heap → Parent ≤ Children.

Answer: C

Heap Sort:
1.Build Max-Heap.
2.Extract max repeatedly.
3. O(n log n).

Answer: C

Heaps are primarily used for priority queues.
Efficient insert O(log n) and extract max/min O(log n).

Answer: B

Dijkstra’s Algorithm repeatedly extracts the minimum distance vertex → requires Extract-Min operation from a Min-Heap / Priority Queue.

for a node at index i:(first element at index 0)

Left child is at index 2i + 1
Right child is at index 2i + 2
Parent is at index (i − 1) / 2 (integer division)
Example:
Array = [10, 20, 30, 40, 50] (heap structure)

Root 10 at i = 0

Left child → 2*0 + 1 = 1 → element = 20
Right child → 2*0 + 2 = 2 → element = 30
Node 20 at i = 1

Left child → 2*1 + 1 = 3 → element = 40
Right child → 2*1 + 2 = 4 → element = 50
So, Answer = 2i + 1 → Option D

Answer: C

 Huffman coding is an algorithm used for lossless data compression.
It assigns shorter binary codes to more frequent symbols and longer binary codes to less frequent symbols.
This reduces the overall size of data without losing any information.

Huffman coding = lossless data compression.
Used in ZIP files, JPEG, MP3.

Answer: D

Explanation:

Graphs are usually stored as Adjacency Matrix, Adjacency List, or Incidence Matrix.
Binary Heap is unrelated (used in priority queues).

Answer: A

A Spanning Tree of a graph is a subgraph that:
1. Includes all the vertices of the graph.
2. Is a tree (i.e., no cycles, connected).
3. Uses the minimum number of edges needed to connect all vertices.
If the original graph has V vertices, then any spanning tree will always have (V − 1) edges.

Answer: D

Minimum Spanning Tree (MST):
A spanning tree with the minimum total edge weight (when edges have weights).
Famous algorithms:
Prim’s Algorithm
Kruskal’s (greedy)  Algorithm

Answer: C
Insertion Sort 
Insertion sort builds the sorted list one element at a time.
For each element, it compares backward with already sorted elements and inserts it in the right place.
 
Why the Best Case is O(n)?
When array is already sorted:
For each element, insertion sort checks just once and sees it’s already in order.
So, only n comparisons (no swaps).
Hence time = linear (O(n)).
 Best Case: O(n)
Worst Case: O(n²)
Average Case: O(n²)

Answer: A
Selection sort Repeatedly select the smallest element from the unsorted portion and put it at the correct position in the sorted portion.
Process:
1. Find the minimum element in the array.
2. Swap it with the element at the beginning.
3. Repeat for the next unsorted part until the whole array is sorted.
That’s why it’s called Selection Sort — it selects the minimum (or maximum) each time.

Example: Array = [29, 10, 14, 37, 13]
Pass 1: Smallest = 10, swap with 29 → [10, 29, 14, 37, 13]
Pass 2: Smallest in remaining = 13, swap with 29 → [10, 13, 14, 37, 29]
Pass 3: Smallest in remaining = 14 (already in place).
Pass 4: Smallest in remaining = 29, swap with 37 → [10, 13, 14, 29, 37]

Time Complexity
Best case, worst case, average case: O(n²).

Answer: B

Merge Sort → Divide and Conquer: 
Merge Sort is a recursive sorting algorithm.
It works by the Divide and Conquer paradigm.
 
Divide and Conquer Paradigm:
Divide: Split the array into two halves.
Conquer: Recursively sort each half.
Combine: Merge the two sorted halves into one sorted array.

Answer: C
Radix Sort is a non-comparative sorting algorithm.
It works by sorting numbers digit by digit, starting from the least significant digit (LSD) to the most significant digit (MSD) (or vice versa).
Unlike comparison-based algorithms (Merge, Quick, Heap, etc.), Radix Sort does not compare elements directly.

 How Radix Sort Works (LSD Method)
Let’s say we want to sort:
[170, 45, 75, 90, 802, 24, 2, 66]

Step 1: Sort by least significant digit (1’s place)
→ [170, 90, 802, 2, 24, 45, 75, 66]

Step 2: Sort by 10’s place
→ [802, 2, 24, 45, 66, 170, 75, 90]

Step 3: Sort by 100’s place
→ [2, 24, 45, 66, 75, 90, 170, 802]

Answer: C
Insertion sort works by inserting each element into its correct position in the already “sorted part” of the array.
If the array is already sorted or nearly sorted, each element is already close to where it should be.
That means very few comparisons and shifts are needed.
Best-case time complexity: O(n) → excellent for nearly sorted arrays.

Answer: B
Hashing is used for fast searching in O(1) average time.

Answer: D
Hash tables use arrays for direct access, but chaining with linked lists for collisions.

Answer: B

Collision: When two keys hash to the same location.

Answer: B

Double hashing avoids secondary clustering (keys with same initial position).

Answer: B

Huffman Coding
Huffman coding builds an optimal prefix-free binary tree based on character frequencies.
Process:

1.Pick two lowest-frequency nodes.
2.Merge them into a new node (sum of frequencies).
3.Repeat until only one root remains.
 
Step 2: What if all frequencies are equal
Suppose we have characters {A, B, C, D} with equal frequency (say frequency = 5 each).
Huffman algorithm doesn’t “favor” any one character.
It will combine them in pairs evenly, so the resulting tree is balanced.

Answer: C 
A complete graph is definitely connected.
Removing up to n − 2 edges can still leave it connected.
Here we remove exactly n − 1 edges, so we need to check connectivity. Even after removing n−1n-1n−1 edges, the graph is still connected (not necessarily complete, not necessarily a tree).

Answer: D

Kruskal’s → Greedy 
Prim’s → Greedy 
Dijkstra’s → Greedy 
Floyd–Warshall → Dynamic Programming (NOT Greedy).

External Sorting:
External sorting is used when the data is too large to fit into main memory (RAM) and must be sorted using secondary storage (like disk/SSD).
Example: Sorting terabytes of data (like database queries, search engine indexing).
External sorting must minimize disk I/O operations (since disk access is slow compared to RAM).
 
Data can be divided into chunks that fit into memory.
Each chunk is sorted internally (using normal sort).
Sorted chunks are merged efficiently using multi-way merging.
Merge operation is sequential → very efficient for disk access.
This method is called External Merge Sort.

Answer B
Topological Sorting
Topological Sort is an ordering of vertices in a directed graph such that for every directed edge u→vu \to vu→v, u comes before v in the ordering.
Example use case:

Task scheduling (where some tasks must be done before others).
Step 2: Conditions for Topological Sorting
It works only on a Directed Acyclic Graph (DAG) because:

Directed: The order matters (must respect edge direction).
Acyclic: If there’s a cycle, no valid ordering exists.

Example: In a cycle A → B → C → A, who comes first? Impossible.