Top 20 MCQ Questions On Trees And Their Applications

This set of MCQ questions on trees and their applications in data structure includes multiple-choice questions on algorithms pertaining to binary search tree along with other algorithms such as height balanced trees, A-A trees and AVL trees.

1. In ……………………….. ; for any node n, every descendant node’s value in the left subtree of n is less than the value of n and every descendant node’s value in the right subtree is greater than the value n.
A) binary tree
B) binary search tree
C) AVL tree
D) binary heap tree

2. For finding a node in a …………………, at each stage we ideally reduce the number of nodes we have to check by half.
A) binary tree
B) binary search tree
C) AVL tree
D) binary heap tree

3. In the best case of BST, the time is on the order of ……………………, but in the worst case it requires linear time.
A) log₂n
B) n
C) log₂(n+1)
D) n+1

4. …………………. of binary search tree starts by visiting the current node, then its left child and then its right child.
A) Preorder traversal
B) In-order traversal
C) Linear traversal
D) Post-order traversal

5. The order with which the nodes are inserted affects the running time of the ……………………. search algorithm.
A) AVL Tree
B) Red-Black Tree
C) Binary Search Tree
D) Binary Heap Tree

6. ……………….. of binary search tree starts by visiting the current node’s left child, then its right child and finally the current node itself.
A) Preorder
B) In-order
C) Linear
D) Post-order

7. With an ideal balance, the running time for inserts, searches and deletes, even in the worst case is ………………………
A) log₂n
B) n
C) log₂(n+1)
D) n+1

8. In binary search tree, a …………………. exists if starting from some node n there exists a path that returns to n.
A) cycle
B) node
C) root
D) subtree

9. In binary search tree, a …………………… rooted to node n is the tree formed by imaging node n was a root.
A) cycle
B) node
C) root
D) subtree

10. …………………………… is a binary search tree whose left subtree and right subtree differ in height by at most 1 unit and whose left and right subtrees are themselves AVL trees.
A) Red-Black Tree
B) AVL Tree
C) Binary Head Tree
D) A-A Tree

11. ………………… is a binary search tree whose leaves are external nodes.
A) Red-Black Tree
B) AVL Tree
C) Binary Heap Tree
D) A-A Tree

12. Which of the following is/are properties of red-black tree.
i) every node is either red or black ii) the root is red iii) If a node is red, then both its children are black iv) every leaf is black
A) i, ii and iii only
B) i, iii and iv only
C) i, ii and iv only
D) All i, ii, iii and iv

13. A lemma is a red-black tree with n internal nodes has height at most ……………
A) 2lg(n)
B) 2n
C) 2lg(n+1)
D) n+1

14. While inserting into ………………………….., insertions are done at a leaf and will replace an external node with an internal node with two external children.
A) red-black tree
B) AVL tree
C) binary search tree
D) binary heap tree

15. For an AVL tree ………………………….. is the additional piece of information which indicates if the difference in height between the left and right subtree is the same or if not, which of the two subtrees has height one unit larger.
A) tree factor
B) balance factor
C) additional factor
D) unit factor

16. ………………… is a complete binary tree, that is completely filled except possibly at the bottom level.
A) Red-Black Tree
B) AVL Tree
C) Binary Heap Tree
D) A-A Tree

17. In a …………………….. for every node X with a parent P, the key in P is less than or equal to the key in X.
A) red-black
B) AVL
C) binary search
D) binary heap

18. An insertion into a ……………………….. is performed by inserting the new node in the location referenced by next in the array and then “sifting it up” by comparing the key of the newly inserted node with the key of the parent.
A) red-black
B) AVL
C) binary search
D) binary heap

19. While deleting nodes from a binary heap, …………………. node is replaced by the last leaf in the tree.
A) left leaf
B) right leaf
C) root
D) cycle

20. The worst-case height of an AVL tree with n nodes is ……………
A) 2 lg n
B) 1.39 lg n
C) 1.44 lg n
D) 1.64 lg n

Answers

1. B) binary search tree
2. B) binary search tree
3. A) log₂n
4. A) Preorder traversal
5. C) Binary Search Tree
6. D) Post-order
7. A) log₂n
8. A) cycle
9. D) subtree
10. B) AVL Tree
11. A) Red-Black Tree
12. B) i, iii and iv only
13. C) 2lg(n+1)
14. A) red-black tree
15. B) balance factor
16. C) Binary Heap Tree
17. D) binary heap
18. D) binary heap
19. C) root
20.C) 1.44 lg n