This set of multiple choice question on tree and its application in data structure includes MCQ 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

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