Tree Data Structure : MCQs & PYQs with Explanation

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 A

In a Binary Tree:

• Inorder Traversal Follows: Left → Root → Right
• Postorder Traversal Follows: Left → Right → Root
• Preorder Traversal Follows: Root → Left → Right

Given:

• Inorder: E, I, C, F, B, G, D, J, H, K
• Postorder: I, E, F, C, G, J, K, H, D, B

In postorder traversal, the last element is always the root. Therefore, Root = B.
Now split Inorder traversal around B.

• Left Subtree: E, I, C, F
• Right Subtree: G, D, J, H, K

Now split postorder accordingly.
Left Subtree Postorder:

• I, E, F, C

Right Subtree Postorder:

• G, J, K, H, D

Construct Left Subtree:
From left subtree postorder, last element is C. So, C becomes left child of B.
In inorder:
E, I | C | F

• Left of C: E, I
• Right of C: F

From Postorder:

• E, I gives subtree with root E.
• I becomes right child of E.
• F becomes right child of C.

Thus, left subtree preorder becomes: C, E, I, F.
Construct Right Subtree:
Right subtree postorder are G, J, K, H, D. Last element is D So D becomes right child of B.
In inorder:
G | D | J, H, K

• Left of D is G and Right of D are J, H, K.

From postorder:

• G is left child.
• H becomes root of right subtree.
• J becomes left child of H.
• K becomes right child of H.

Thus, right subtree preorder becomes D, G, H, J, K.
Final Preorder Traversal sequence are B, C, E, I, F, D, G, H, J, K.

Option C

The relation between leaf nodes and nodes having degree 2 is generally derived using the property of a full (strict) binary tree. In such a tree, every internal node has exactly two children.
If L is number of leaf nodes and I is number of nodes with degree 2 then the standard relation is L=I+1.
Given that the number of leaf nodes is n, and using the relation L=I+1, we get n=I+1. Therefore, I=n-1. Hence, the number of nodes with degree 2 is n-1.

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