Data Structures Multiple Choice Questions and Answers on Binary Tree Properties
https://www.computersprofessor.com/2017/10/data-structures-multiple-choice_27.html
1. The number of edges from the root to the node is called __________ of the tree.
a) Height
b) Depth
c) Length
d) None of the mentioned
Answer: b
Explanation: By definition.
2. The number of edges from the node to the deepest leaf is called _________ of the tree.
a) Height
b) Depth
c) Length
d) None of the mentioned
Answer: a
Explanation: By definition.
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
Answer: a
Explanation: By definition.
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) None of the mentioned
Answer: c
Explanation: By definition.
5. What is the 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)
Answer: d
Explanation: The nodes are either a part of left sub tree or the right sub tree, so we don’t have to traverse all the nodes, this means the complexity is lesser than n, in the average case, assuming the nodes are spread evenly, the time complexity becomes O(n).
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
Answer: d
Explanation: This is an application of stack.
7. In a full binary tree if number of internal nodes is I, then number of leaves L are?
a) L = 2I
b) L = I + 1
c) L = I – 1
d) L = 2I – 1
Answer: b
Explanation: Trace with respect to the diagram.
8. In a full binary tree if number of internal nodes is I, then number of nodes N are?
a) N = 2I
b) N = I + 1
c) N = I – 1
d) N = 2I + 1
Answer: d
Explanation: Trace with respect to the diagram.
9. In a full binary tree if there are L leaves, then total number of nodes N are?
a) N = 2L
b) N = L + 1
c) N = L – 1
d) N = 2L – 1
Answer: d
Explanation: Trace with respect to the diagram.
10. Which of the following is correct 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) All of the mentioned
Answer: d
Explanation: Refer the diagram.
