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 tree, the degree of a node is the number of children (subtrees) that the node has.
The degree of a tree is defined as the maximum degree of any node present in the tree.

The maximum degree among all nodes is 2. Therefore, the degree of the tree is 2.

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 C

The given preorder traversal is 38, 14, 8, 23, 18, 20, 56, 45, 82, 70. Since this is a Binary Search Tree (BST), we can obtain the inorder traversal by arranging all the elements in ascending order.
So, the inorder traversal is 8, 14, 18, 20, 23, 38, 45, 56, 70, 82.
Now, we have both traversals:

• Preorder: 38, 14, 8, 23, 18, 20, 56, 45, 82, 70
• Inorder: 8, 14, 18, 20, 23, 38, 45, 56, 70, 82

In preorder, the first element is always the root, so 38 is the root. Using 38 in the inorder sequence, we divide the tree into:

• Left subtree: 8, 14, 18, 20, 23
• Right subtree: 45, 56, 70, 82

For the left subtree, the preorder sequence is 14, 8, 23, 18, 20. Its root is 14. Following the same process gives the postorder sequence is 8, 20, 18, 23, 14.
For the right subtree, the preorder sequence is 56, 45, 82, 70. Its root is 56, giving the postorder sequence is 45, 70, 82, 56.
Finally, postorder traversal follows: Left Subtree → Right Subtree → Root. Therefore, 8, 20, 18, 23, 14, 45, 70, 82, 56, 38 is postorder traversal sequence.

The Binary Search Tree (BST) constructed from the given preorder sequence is shown below:

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 A

Deletion of a node in a Binary Search Tree (BST) depends on the number of children that the node has. There are three main cases:

• Node has No Children (leaf node): Simply remove the node.
• Node has One Child: Connect the parent directly to the node's only child.
• Node has Two Children: Replace the node's value with its inorder successor or inorder predecessor, and then delete that successor/predecessor.