CS Free MCQ Bank

[ Option C ]

A Binary Search Tree (BST) is a binary tree where:

• Left subtree contains values less than root.
• Right subtree contains values greater than root.

The first element 47 becomes the root of the Binary Search Tree, and the remaining elements are inserted according to BST rules. 
However, it is not always necessary to draw the complete tree, we can simply count the elements such that all values less than the root belong to the left subtree, and all values greater than the root belong to the right subtree.

Left Subtree (< 47):

• 19, 5, 23, 39, 4, 6, 27, 14
• Total = 8 nodes.

Right Subtree (> 47):

• 68, 58, 50
• Total = 3 nodes.

[ Option B ]

A Max-Heap is a complete binary tree in which every parent node is greater than or equal to its children.
So, if a parent has children, then:

• Parent ≥ Left Child.
• Parent ≥ Right Child.

Heaps are usually stored in an array.
For index i:

• Left child = 2i+1
• Right child = 2i+2
• Parent = (i−1)/2

So, the given array A = [4, 1, 3, 2, 16, 9, 10, 14, 8, 7] is treated like this tree structure:

• 4 is the root and 1 and 3 are its children.
• 2 and 16 are children of 1.
• 9 and 10 are children of 3 and so on.

“Convert to Max-Heap” means rearranging the given array elements so that they satisfy the properties of a max-heap. In a max-heap, the largest element is always placed at the root (top), and every parent node has a value greater than or equal to its child nodes.

The Build-Max-Heap Algorithm uses a Bottom-Up approach to convert an array into a max-heap. Instead of starting from the root, it begins from the last non-leaf node and moves upward to the root, applying heapify at each step. This approach ensures that smaller subtrees are fixed first before handling their parent nodes.
Leaf Nodes are not processed because they already satisfy the heap property. Only internal nodes may violate the max-heap condition, so they are adjusted.
In an array representation of a max-heap (0-based indexing), the last non-leaf node is found using the formula: ⌊n/2⌋-1, where n is the total number of elements in the heap.

• Index Range of all Non-Leaf nodes (Internal Nodes) : 0 to ⌊n/2⌋-1
• Index Range of all Leaf Nodes (External Node) : ⌊n/2⌋ to n-1

Step-by-Step Process:
Given Array A=[4, 1, 3, 2, 16, 9, 10, 14, 8, 7]
There are 10 elements, so the last non-leaf node is at index: ⌊10/2⌋-1 = 4. So we heapify from index 4 down to 0. Heapify from bottom to top.
Heapify at Index 4 : Value 16

• Children: A[9]=7 only
• 16>7, so no interchange is needed.
• Swaps (Interchanges): 0 (Total : 0)

Heapify at Index 3 : Value 2

• Children: A[7]=14, A[8]=8
• Largest child is 14, so swap 2 and 14.
• Swaps (Interchanges): 1 (Total : 1)
• Now, Array Becomes: [4, 1, 3, 14, 16, 9, 10, 2, 8, 7]
• Now 2 is moved down. It has no problem further, so stop.

Heapify at Index 2 : Value 3

• Children: A[5]=9 and A[6]=10
• Largest is 10, so swap 3 and 10.
• Swaps (Interchanges): 1 (Total : 2)
• Now, Array Becomes: [4, 1, 10, 14, 16, 9, 3, 2, 8, 7]

Heapify at Index 1 : Value 1

• Children: A[3]=14 and A[4]=16
• Largest is 16, so swap 1 and 16.
• Swaps (Interchanges): 1 (Total : 3)
• Now, Array Becomes: [4, 16, 10, 14, 1, 9, 3, 2, 8, 7]
• Now 1 is at index 4, and its child 7 is bigger, so swap 1 and 7.
• Swaps (Interchanges): 1 (Total : 4)
• Now, Array Becomes: [4, 16, 10, 14, 7, 9, 3, 2, 8, 1]

Heapify at Index 0 : Value 4

• Children: A[1]=16 and A[2]=10
• Largest is 16, so swap 4 and 16.
• Swaps (Interchanges): 1 (Total : 5)
• Now, Array Becomes: [16, 4, 10, 14, 7, 9, 3, 2, 8, 1]
• New Child check at index 1: Children : A[3]=14 and A[4]=7.
• Largest is 14, so swap 4 and 14.
• Swaps (Interchanges): 1 (Total : 6)
• Now, Array Becomes: [16, 14, 10, 4, 7, 9, 3, 2, 8, 1]
• New Child check at index 3: Children : A[7]=2 and A[8]=8.
• Largest is 8, so swap 4 and 8.
• Swaps (Interchanges): 1 (Total : 7)
• Now, Array Becomes: [16, 14, 10, 8, 7, 9, 3, 2, 4, 1]. This is final Max-Heap.

The total number of interchanges necessary to convert the array into a Max-Heap is 7.

[ Option B ]

Statement S1: Ternary search divides the array into three parts, while binary search divides it into two parts. Although ternary search reduces the search space into more parts, it requires more comparisons per step than binary search. As a result, binary search is generally more efficient for finding an element in a sorted array. Hence, S1 is incorrect.

Statement S2: In an AVL tree, both insertion and deletion operations may require rebalancing the tree. In the worst case, both operations take O(log n) time because the height of an AVL tree is always logarithmic. Hence, S2 is correct.

[ Option B ]

A spanning tree is a subgraph of a connected graph that includes all the vertices but only enough edges to keep the graph connected without forming any cycles.

• The spanning tree does not have any cycle.
• A complete undirected graph can have maximum N^N-2 number of spanning trees, where N is the number of vertices.
• Spanning tree has N-1 edges, where N is the number of vertices.

[ Option B ]

A Binary Search Tree (BST) is a special type of binary tree where the arrangement of elements follows a strict rule:

• Left Subtree contains elements smaller than the node’s value.
• Right Subtree contains elements greater than the node’s value.

This property allows fast searching, because at each step, the tree decides whether to go left (for smaller values) or right (for larger values).

[ Option C ]

In inorder traversal, nodes are visited in the order Left Subtree → Root → Right Subtree.
Left subtree of a (rooted at b):

• h, d, b, i, e, j

Then visit root:

• a

Right subtree of a (rooted at c):

• f, c, k, g

Final inorder traversal:
h, d, b, i, e, j, a, f, c, k, g

[ Option D ]

The Huffman Coding Algorithm is a lossless data compression technique and a classic example of a Greedy Algorithm. It assigns variable-length binary codes to symbols based on their frequency of occurrence, where more frequent symbols get shorter codes and less frequent symbols get longer codes, reducing the overall size of the encoded data.
Since the algorithm generates codes according to the frequency of input symbols, Huffman coding works on the principle of symbol frequencies.

[ Option A ]

[ Option B ]

A Binary Search Tree (BST) is a special type of binary tree that is designed to allow fast searching, insertion, and deletion of data. In BST:

• All values in the left child and its subtree must be less than the value of the node.
• All values in the right child and its subtree must be greater than the value of the node.

The preorder traversal sequence is given and in case of BST, the inorder traversal always sorts the tree nodes into ascending order.
Preorder : 15, 10, 12, 11, 20, 18, 16, 19
Inorder : 10, 11, 12, 15, 16, 18, 19, 20
WHEN PREORDER AND INORDER TRAVERSAL GIVEN:

• First of all, we decide the root node of the tree using Preorder sequence because in Preorder sequence the leftmost element is root node.
• Now by searching root node in Inorder sequence, we can find out all elements on left side of root node are in left subtree and elements on right are in right subtree.
• This procedure is recursively defined.

So, the resultant BST is:
             15
           /       \
        10        20
          \         /
          12    18
         /        /  \
       11    16   19
Final Postorder traversal sequence is 11, 12, 10, 16, 19, 18, 20, 15

[ Option B ]

A binary tree is a hierarchical data structure in which each node can have at most two children, called the left child and the right child.
Now, some binary trees can grow in an uneven manner. For example, all nodes may keep inserting to the left side only. This makes the tree skewed, and searching becomes slow. To avoid this, we use a balanced binary tree.
A Balanced Binary Tree is a special type of binary tree in which the height (depth) of the left and right subtrees of every node is kept nearly equal.
Height of left subtree and right subtree differ by 0 or 1 only.
This condition must hold at every node in the tree, not just the root.
So, in a balanced binary tree (AVL Tree), the difference between the heights of the left and right subtree of any node is allowed to be at most 1.

[ Option D ]

A Binary Search Tree (BST) is a tree where:

• All elements in the left subtree are smaller than the node.
• All elements in the right subtree are greater than the node.

The given sequences like 27, 87, 37, 76, 28, 53 represent the path followed while searching the key 53 in a BST. That means:

• We start from the root.
• Move left or right based on comparison.
• The sequence shows all visited nodes in order.

While searching in a BST:
Every step creates a valid range (Minimum, Maximum), Initially: (-∞, +∞). The next node in the sequence must lie within this range.
Rule:

• If we go right then update minimum (lower bound) with current node.
• If we go left then update maximum (upper bound) with current node.
• Next value must lie within (Minimum, Maximum).

This concept comes from the basic property of a Binary Search Tree (BST), where all elements on the left side of a node are smaller, and all elements on the right side are greater. 
While searching for a value (like 53), we move left or right based on comparison, and this movement automatically creates restrictions.
When we move to the right of a node, it means the searched value is greater than that node. So, all future nodes we visit must also be greater than that value. In this way, the Minimum Limit (Lower Bound) gets updated.
Similarly, when we move to the left of a node, it means the searched value is smaller than that node. So, all future nodes must be smaller than that value. This updates the Maximum Limit (Upper Bound).
For example, if we first move right from 27 and then left from 87, the valid range becomes (27, 87). Now, every next node must lie within this range, otherwise, the sequence becomes invalid.

Now check given sequence one by one.

(i)    27 → 87 → 37 → 76 → 28 → 53

Problem: 28 is not in (37, 76). Therefore, this sequence is NOT possible.

(ii)    12 → 13 → 60 → 50 → 70 → 53

Problem: 70 is not in (50, 60). Therefore, this sequence is NOT possible.

(iii)    20 → 75 → 41 → 58 → 47 → 53

(iv)    71 → 62 → 24 → 27 → 50 → 53

[ Option A ]

A binary tree is commonly traversed using three standard tree traversal techniques:

• Preorder Traversal (Root → Left → Right).
• Inorder Traversal (Left → Root → Right).
• Postorder Traversal (Left → Right → Root).

These methods are systematic and widely used in all tree-related algorithms.

[ Option C ]

As we know, inorder traversal of BST is in sorted order. So,
Inorder Traversal : 20, 30, 50, 55, 60, 100, 130, 140, 150, 170, 180
Preorder Traversal : 100, 50, 20, 30, 60, 55, 150, 130, 140, 180, 170
With Inorder and Preorder, unique BST can be determined.

Using the above constructed BST, the postorder traversal sequence is:
Postorder Traversal : 30, 20, 55, 60, 50, 140, 130, 170, 180, 150, 100

[ Option B ]

A Max-Heap is a complete binary tree in which every parent node is greater than or equal to its children. When a heap is constructed from an array (Using Heapify), the largest element becomes the root, and smaller elements move toward the lower levels.
After inserting all the nodes in the max-heap there are total 3-level and right child of root node is 10.

[ Option C ]

In a complete (full) n-ary tree, every internal node has exactly n children. A standard relation between internal nodes (I) and leaves (L) is: L = (n-1)*I+1
This formula comes from the fact that each internal node contributes n children, but overlaps create this final relation.
Given:
L = 41, I = 10
L = (n-1)*I+1
41 = (n-1)*10+1
41 = 10n-10+1
10n=41+10-1
10n=50
n=50/10
n=5

[ Option D ]

[ Option D ]

A Binary Search Tree (BST) is a binary tree where nodes follow a strict ordering rule for efficient searching, insertion, and deletion. Each node has at most two children.
BST Rule:

• Left child < Root node.
• Right child > Root node.
• Both left and right subtrees must themselves follow all BST rules.

[ Option D ]

A forest is an acyclic undirected graph, that is, a collection of disjoint trees. Each tree with m vertices has m-1 edges, so the total edges in the forest are:
n1 - 1 + n2 - 1 + ... + nk - 1 = (n1 + n2 + ... + nk) - k = n-k
So the number of edges is n-k.

[ Option B ]

      33
     /  
    2    45
             
             91
            /  
          47    95

[ Option A ]

Here,
(a) and (b) are trees.
(c) is not a tree because adeb form a graph
(d) It is not hierarchical so that is why not a tree.

[ Option A ]

The Level Order Traversal also known as Breadth First Search (BFS) while other three are DFS.

[ Option B ]

A Minimum Spanning Tree (MST) is a subset of the edges of a connected, weighted graph that:

• Connects all the vertices together without any cycle.
• Has the minimum possible total edge weight.

Algorithms for MST:

1. Kruskal’s Algorithm:
   • Sorts all edges in ascending order of weight.
   • Picks the smallest edge that does not form a cycle.
   • Uses a greedy strategy by always choosing the cheapest available edge.
2. Prim’s Algorithm:
   • Starts from any node.
   • At each step, adds the lowest-weight edge that connects a new vertex to the growing MST.
   • Also, a greedy approach — chooses the best local option at every step.

Bonus:

1. Bellman-Ford Algorithm:
   • Solves single-source shortest path problem.
   • It can handle negative weights and uses dynamic programming.
   • It is more flexible (handles negative weights), but slower than Dijkstra’s.
2. Floyd-Warshall Algorithm:
   • Solves all-pairs shortest path problem.
   • It uses dynamic programming.
3. Dijkstra’s Algorithm:
   • Solves single-source shortest path problem.
   • It fails with negative weights and uses greedy approach, but not for MST.

[ Option B ]

[ Option C ]

When number of node N is given then how many total numbers of possible binary trees can be drawn. This can be calculated using Catalan number. C_n=(2n)!/(n+1)!n!, where, n is number of nodes.
When n=4.
C₄ = (2*4)!/(4+1)!*4!
C₄ = 8!/5!*4!
C₄ = 8*7*6*5!/5!*4*3*2*1
C₄ = 336/24
C₄ = 14

[ Option D ]

A Binary Search Tree (BST) is a special type of binary tree that is designed to allow fast searching, insertion, and deletion of data. In BST:

• All values in the left child and its subtree must be less than the value of the node.
• All values in the right child and its subtree must be greater than the value of the node.

The preorder traversal sequence is given and in case of BST, the inorder traversal always sorts the tree nodes into ascending order.
Preorder : 22, 9, 8, 1, 6, 19, 18, 17, 20, 23, 29, 33
Inorder : 1, 6, 8, 9, 17, 18, 19, 20, 22, 23, 29, 33
WHEN PREORDER AND INORDER TRAVERSAL GIVEN:

• First of all, we decide the root node of the tree using Preorder sequence because in Preorder sequence the leftmost element is root node.
• Now by searching root node in Inorder sequence, we can find out all elements on left side of root node are in left subtree and elements on right are in right subtree.
• This procedure is recursively defined.

So, the resultant BST is:

Final Postorder traversal sequence is 6,1,8,17,18,20,19,9,33,29,23,22

[ Option A ]

A Minimum Spanning Tree (MST) is a subset of edges in a connected weighted graph that connects all vertices with the minimum total edge weight and without forming any cycles.
Kruskal’s Algorithm is a well-known greedy algorithm that builds the MST by selecting the smallest weight edges one by one, ensuring no cycle is formed.

• Binary Search is used for searching in sorted data.
• BFS and DFS are graph traversal algorithms.

[ Option C ]

Insertion performance depends on how much rearrangement or shifting is required after adding a new element.
A heap is a complete binary tree (usually implemented as an array) where insertion is done by placing the element at the end and then adjusting it using heapify (upward movement). This takes O(log n) time and involves minimal shifting compared to other structures.

Ordered Array:

• Insertion requires finding the correct position and then shifting many elements to make space, so it becomes slow and takes O(n) time.

Ordered Linked List:

• You must traverse the list to find the correct position, which also takes O(n) time because you cannot jump directly.

Binary Search Tree (BST):

• Insertion is fast on average (O(log n)), but if the tree becomes skewed (unbalanced), it can become slow (O(n)).

Heap:

• Insertion is done at the end and then heapify, which usually takes O(log n) time and is efficient in practice.

[ Option A ]

In a Binary Search Tree (BST), different traversals follow specific patterns:

• Inorder traversal always produces elements in sorted (ascending) order.
• Preorder traversal depends on the order of insertion, i.e., Root → Left → Right.

For both inorder and preorder to be the same, the BST must have a special structure:

• The tree should be Right-Skewed.
• Every new element is inserted as the right child.
• This happens when elements are inserted in increasing (sorted) order.

In option (a), the insertion order is 1 → 4 → 9 → 13 → 15 → 20 → 27, which creates a right-skewed BST where there are no left children, and as a result, both inorder and preorder traversals become identical, i.e., 1, 4, 9, 13, 15, 20, 27.

Note:

A Right-Skewed Binary Search Tree is a special type of BST in which every node has only a right child and no left child. This structure looks like a straight line leaning towards the right side.
In such a tree, elements are inserted in increasing order, so each new element becomes the right child of the previous node. Because there are no left children, both Inorder and Preorder traversals produce the same sequence.

[ Option D ]

A binary tree is a hierarchical data structure in which each node has at most two children. To process or visit all nodes of a binary tree, several traversal techniques are used:

• Preorder Traversal: Visit Root → Left Subtree → Right Subtree.
• Inorder Traversal: Visit Left Subtree → Root → Right Subtree.
• Postorder Traversal: Visit Left Subtree → Right Subtree → Root.

All three are standard and commonly used techniques for binary tree traversal.

[ Option C ]

Level Order Traversal means visiting nodes level by level from top to bottom, starting from the root. In this traversal, all nodes at one level are visited before moving to the next level.
This behavior is exactly followed by Breadth First Search (BFS). BFS uses a Queue to process nodes level-wise, making it the correct method for level order traversal.

[ Option D ]

A max-heap is a complete binary tree in which every parent node is greater than or equal to its children. When a heap is constructed from an array (Using Heapify), the largest element becomes the root, and smaller elements move toward the lower levels.
After inserting all the nodes in the max-heap, the last element is 2.

[ Option C ]

[ Option A ]

In a tree data structure, there are three primary types of traversal sequences used to visit all the nodes systematically: Preorder, Inorder, and Postorder traversal.

1. Preorder traversal visits nodes in the order: root first, then the left subtree, followed by the right subtree. This means the current node is processed before its child nodes.
2. Inorder traversal visits nodes by first traversing the left subtree, then the root node, and finally the right subtree. This order is commonly used in binary search trees because it visits nodes in ascending sorted order.
3. Postorder traversal visits the nodes by first traversing the left subtree, then the right subtree, and finally the root node. This traversal is especially useful when deleting trees or evaluating postfix expressions.

So,

(1) Preorder Traversal: Root → Left → Right
(2) Inorder Traversal: Left → Root → Right
(3) Postorder Traversal: Left → Right → Root

The preorder traversal of the tree is ABCDEF, which means the root of the tree is A. Looking at the inorder traversal BADCFE, we see that A splits the tree into a left subtree (B) and a right subtree (DCFE). Thus, B is the left child of A, and the rest of the nodes (DCFE) belong to the right subtree.

In the right subtree, the preorder sequence is CDEF, so the root here is C. From the inorder sequence DCFE, the node C splits the subtree into D on the left and FE on the right. For the FE part, preorder tells us the root is E, and inorder (FE) shows that F is on the left of E. This gives the right subtree structure: C has left child D and right child E, with E having left child F.

Now, constructing the postorder traversal: start with the left subtree of A which is B, then the right subtree rooted at C. For C, its left subtree gives D, and its right subtree rooted at E gives F followed by E. After these, we add the root C. Finally, we append the overall root A. Putting this together, the Postorder is B D F E C A.

[ Option A ]

Kruskal’s algorithm is a greedy algorithm used to find the Minimum Spanning Tree (MST) of a connected, weighted graph. It works by sorting all the edges of the graph in non-decreasing order of their weights. Then, it iteratively adds the smallest edge to the MST, provided that adding the edge does not create a cycle in the growing tree.

The algorithm continues until the MST has exactly V−1 edges, where V is the number of vertices. 

Unlike Prim’s algorithm, which grows the MST from a starting vertex, Kruskal’s algorithm builds the MST by focusing on edges first, ensuring the final tree has the minimum total weight.

Must Know:
Non-decreasing order of their weight means the edges are arranged from smallest weight to largest weight, but equal weights are allowed to appear next to each other. For example, if the edge weights are [6, 2, 9, 4, 2], then sorted in non-decreasing order they become [2, 2, 4, 6, 9].

[ Option D ]

When the numbers 1, 2, …, n are inserted into a Binary Search Tree in increasing order, the first inserted element becomes the root (k). In a BST, all elements greater than the root are placed in the right subtree, while smaller elements go to the left subtree.
The number of nodes in the right subtree will be the count of elements greater than the root, which is given by n-k. According to the question, the right subtree contains p nodes, so we can write the relation as n-k = p.
Solving this equation, we get k = n-p, which represents the first inserted number (root). Hence, the required answer is n-p.

[ Option D ]

In a Binary Search Tree (BST), elements are inserted one by one, and the structure of the tree depends on the insertion order. 
However, once the tree is constructed, the traversal order depends on the structure of the tree, not on the original sequence of insertion.
Inorder traversal always gives a sorted sequence, preorder and postorder depend on the tree shape, and none of these traversals can consistently reproduce the original list. Therefore, no traversal guarantees the same order as the input list in all cases.

[ Option A ]

In an array representation of a Binary Tree (1-Based Indexing), the position of children is determined using formulas:

• Left Child : 2*i
• Right Child : 2*i+1

In 0-Based Indexing:

• Left Child : 2*i+1
• Right Child : 2*i+2

Where i is index of parent node.
Here, node 17 is at index 5.
So,

• Left Child : 2*5 = 10 (this position is empty)
• Right Child : 2*5+1 = 11 (Value is18)

Thus, node 17 has only one child, which is 18.

[ Option B ]

A Binary Search Tree (BST) can become unbalanced, which increases search time. To solve this, self-balancing trees are used.
An AVL (Adelson-Velsky and Landis) Tree is a special type of BST where the difference between the heights of the left and right subtrees, called balance factor, is at most 1 for every node.

• The Complete Binary Tree is about filling levels, not balancing height. 
• Red-Black Tree is also self-balancing but follows different rules and does not strictly maintain height difference of 1.