Data Structure Multiple Choice Questions – Binary Tree

This set of Data Structure Multiple Choice Questions & Answers (MCQs) focuses on “Binary Tree”.

1. The number of edges from the root to the node is called __________ of the tree.
a) Height
b) Depth
c) Length
d) Width
View Answer

2. The number of edges from the node to the deepest leaf is called _________ of the tree.
a) Height
b) Depth
c) Length
d) Width
View Answer

3. What is a full binary tree?
a) Each node has exactly zero or two children
b) Each node has exactly two children
c) All the leaves are at the same level
d) Each node has exactly one or two children
View Answer

4. What is a complete binary tree?
a) Each node has exactly zero or two children
b) A binary tree, which is completely filled, with the possible exception of the bottom level, which is filled from right to left
c) A binary tree, which is completely filled, with the possible exception of the bottom level, which is filled from left to right
d) A tree In which all nodes have degree 2
View Answer

5. What is the average case time complexity for finding the height of the binary tree?
a) h = O(loglogn)
b) h = O(nlogn)
c) h = O(n)
d) h = O(log n)
View Answer

6. Which of the following is not an advantage of trees?
a) Hierarchical structure
b) Faster search
c) Router algorithms
d) Undo/Redo operations in a notepad
View Answer

7. In a full binary tree if number of internal nodes is I, then number of leaves L are?
a) L = 2*I
b) L = I + 1
c) L = I – 1
d) L = 2*I – 1
View Answer

8. In a full binary tree if number of internal nodes is I, then number of nodes N are?
a) N = 2*I
b) N = I + 1
c) N = I – 1
d) N = 2*I + 1
View Answer

9. In a full binary tree if there are L leaves, then total number of nodes N are?
a) N = 2*L
b) N = L + 1
c) N = L – 1
d) N = 2*L – 1
View Answer

10. Which of the following is incorrect with respect to binary trees?
a) Let T be a binary tree. For every k ≥ 0, there are no more than 2k nodes in level k
b) Let T be a binary tree with λ levels. Then T has no more than 2^{λ – 1} nodes
c) Let T be a binary tree with N nodes. Then the number of levels is at least ceil(log (N + 1))
d) Let T be a binary tree with N nodes. Then the number of levels is at least floor(log (N + 1))
View Answer

11. Construct a binary tree by using postorder and inorder sequences given below.
Inorder: N, M, P, O, Q
Postorder: N, P, Q, O, M
a)
b)
c)
d)
View Answer

Answer: d
Explanation: Here,
Postorder Traversal: N, P, Q, O, M
Inorder Traversal: N, M, P, O, Q
Root node of tree is the last visiting node in Postorder traversal. Thus, Root Node = ‘M’.
The partial tree constructed is:

The second last node in postorder traversal is O. Thus, node P becomes left child of node O and node Q becomes right child of node Q. Thus, the final tree is:

12. Construct a binary search tree by using postorder sequence given below.
Postorder: 2, 4, 3, 7, 9, 8, 5.
a)
b)
c)
d)
View Answer

13. Construct a binary tree using inorder and level order traversal given below.
Inorder Traversal: 3, 4, 2, 1, 5, 8, 9
Level Order Traversal: 1, 4, 5, 9, 8, 2, 3
a)
b)
c)
d)
View Answer

Answer: a
Explanation: Inorder Traversal: 3, 4, 2, 1, 5, 8, 9
Level Order Traversal: 1, 4, 5, 9, 8, 2, 3
In level order traversal first node is the root node of the binary tree.
Thus the partially formed tree is:

In level order traversal, the second node is 4. Then, node 3 becomes left child of node 4 and node 2 becomes right child of node 4. Third node of level order traversal is 8. Then, node 5 becomes left child of node 8 and node 9 becomes right child of node 8. Thus, the final tree is:

More MCQs on Binary Tree:

• Binary Tree MCQ (Set 2)
• Binary Tree MCQ (Set 3)
• Binary Tree Operations MCQ
• Balanced Binary Tree MCQ
• Threaded Binary Tree MCQ

Sanfoundry Global Education & Learning Series – Data Structure.

To practice all areas of Data Structure, here is complete set of 1000+ Multiple Choice Questions and Answers.