Engineering Questions with Answers - Multiple Choice Questions

Data Structure MCQ – Binary Tree Properties

1 - Question

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

Answer: b
Explanation: The number of edges from the root to the node is called depth of the tree.




2 - Question

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

Answer: a
Explanation: The number of edges from the node to the deepest leaf is called height of the tree.




3 - Question

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

Answer: a
Explanation: A full binary tree is a tree in which each node has exactly 0 or 2 children.




4 - Question

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

Answer: c
Explanation: A binary tree, which is completely filled, with the possible exception of the bottom level, which is filled from left to right is called complete binary tree. A Tree in which each node has exactly zero or two children is called full binary tree. A Tree in which the degree of each node is 2 except leaf nodes is called perfect binary tree.




5 - Question

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

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(logn).




6 - Question

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

Answer: d
Explanation: Undo/Redo operations in a notepad is an application of stack. Hierarchical structure, Faster search, Router algorithms are advantages of trees.




7 - Question

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

Answer: b
Explanation: Number of Leaf nodes in full binary tree is equal to 1 + Number of Internal Nodes i.e L = I + 1




8 - Question

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

Answer: d
Explanation: Relation between number of internal nodes(I) and nodes(N) is N = 2*I+1.




9 - Question

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

Answer: d
Explanation: The relation between number of nodes(N) and leaves(L) is N=2*L-1.




10 - Question

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

Answer: d
Explanation: In a binary tree, there are atmost 2k nodes in level k and 2k-1 total number of nodes. Number of levels is at least ceil(log(N+1)).




11 - Question

 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) data-structure-questions-answers-binary-tree-properties-q11a
b) data-structure-questions-answers-binary-tree-properties-q11b
c) data-structure-questions-answers-binary-tree-properties-q11c
d) data-structure-questions-answers-binary-tree-properties-q11d

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:
data-structure-questions-answers-binary-tree-properties-q11e
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:
data-structure-questions-answers-binary-tree-properties-q11d




12 - Question

 Construct a binary search tree by using postorder sequence given below.
Postorder: 2, 4, 3, 7, 9, 8, 5.
a) data-structure-questions-answers-binary-tree-properties-q12a
b) data-structure-questions-answers-binary-tree-properties-q12b
c) data-structure-questions-answers-binary-tree-properties-q12c
d) data-structure-questions-answers-binary-tree-properties-q12d

View Answer

Answer: b
Explanation: Postorder sequence is 2, 4, 3, 7, 9, 8, 5.
Inorder sequence is the ascending order of nodes in Binary search tree. Thus, Inorder sequence is 2, 3, 4, 5, 7, 8, 9. The tree constructed using Postorder and Inorder sequence is




13 - Question

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) data-structure-questions-answers-binary-tree-properties-q13a
b) data-structure-questions-answers-binary-tree-properties-q13b
c) data-structure-questions-answers-binary-tree-properties-q13c
d) data-structure-questions-answers-binary-tree-properties-q13d

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:
data-structure-questions-answers-binary-tree-properties-q13e
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:
data-structure-questions-answers-binary-tree-properties-q13a

Get weekly updates about new MCQs and other posts by joining 18000+ community of active learners