/* */ Click to Join Live Class with Shankar sir Call 9798158723

# Data Structure MCQ - Avl Tree

Q1.What is the worst case possible height of AVL tree?
1. 2Logn Assume base of log is 2
2. 1.44log n Assume base of log is 2
3. Depends upon implementation
4. Theta(n)

Q2.Which of the following is AVL Tree?
```A
100
/
50       200
/
10            300

B
100
/
/
50        200
/        /
10       150     300
/
5

C
100
/
/
50            200
/            /
10    60       150     300
/
5                   180       400
```
1. Only A
2. A and C
3. A, B and C
4. Only B

Explanations :A Binary Search Tree is AVL if balance factor of every node is either -1 or 0 or 1. Balance factor of a node X is [(height of X->left) - (height of X->right)]. In Tree B, the node with value 50 has balance factor 2. That is why B is not an AVL tree.
Q3.Which of the following is a self-adjusting or self-balancing Binary Search Tree
1. Splay Tree
2. AVL Tree
3. Red Black Tree
4. All of the above

Q4.Which of the following is true
1. The path from the root to the furthest leaf is no more than twice as long as the path from the root to the nearest leaf
2. At least one children of every black node is red
3. Root may be red
4. A leaf node may be red

Q5. What is the maximum height of an AVL tree with p nodes?
1. p
2. log(p)
3. log(p)/2
4. p/2

Explanations :Consider height of tree to be ‘he’, then number of nodes which totals to p can be written in terms of height as N(he)=N(he-1)+1+N(he-2). since N(he) which is p can be written in terms of height as the beside recurrence relation which on solving gives N(he)= O(logp) as worst case height.
Q6.Given an empty AVL tree, how would you construct AVL tree when a set of numbers are given without performing any rotations?
1. just build the tree with the given input
2. find the median of the set of elements given, make it as root and construct the tree
3. use trial and error
4. use dynamic programming to build the tree

Explanations :Sort the given input, find the median element among them, make it as root and construct left and right subtrees with elements lesser and greater than the median element recursively. this ensures the subtrees differ only by height 1.
Q7.What maximum difference in heights between the leafs of a AVL tree is possible?
1. log(n) where n is the number of nodes
2. n where n is the number of nodes
3. 0 or 1
4. atmost 1

Explanations :At every level we can form a tree with difference in height between subtrees to be atmost 1 and so there can be log(n) such levels since height of AVL tree is log(n).
Q8.Why to prefer red-black trees over AVL trees?
1. Because red-black is more rigidly balanced
2. AVL tree store balance factor in every node which costs space
3. AVL tree fails at scale
4. Red black is more efficient

Explanations :Every node in an AVL tree need to store the balance factor (-1, 0, 1) hence space costs to O(n), n being number of nodes. but in red-black we can use the sign of number (if numbers being stored are only positive) and hence save space for storing balancing information. there are even other reasons where redblack is mostly prefered.
Q9.Given an empty AVL tree, how would you construct AVL tree when a set of numbers are given without performing any rotations?
1. just build the tree with the given input
2. find the median of the set of elements given, make it as root and construct the tree
3. use trial and error
4. use dynamic programming to build the tree