# Exercise: Questions on Balanced Binary Search Trees

Questions on Balanced Binary Search Trees : Question 1 :
The worst case running time to search for an element in a balanced in a binary search tree with n2^n elements is
(A)
(B)
(C)
(D)

 A B C  Correct D
Questions on Balanced Binary Search Trees : Question 2 :
What is the maximum height of any AVL-tree with 7 nodes? Assume that the height of a tree with a single node is 0.

 2 3  Correct 4 5
Questions on Balanced Binary Search Trees : Question 3 :
What is the worst case possible height of AVL tree?

 2Logn Assume base of log is 2 1.44log n Assume base of log is 2  Correct Depends upon implementation Theta(n)
Questions on Balanced Binary Search Trees : Question 4 :
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
```

 Only A A and C  Correct A, B and C Only B
Questions on Balanced Binary Search Trees : Question 5 :
Consider the following AVL tree.
```         60
/     \
20      100
/   \
80    120
```
Which of the following is updated AVL tree after insertion of 70
```A
70
/    \
60      100
/       /    \
20       80    120

B
100
/    \
60      120
/  \     /
20   70   80

C
80
/    \
60      100
/  \       \
20   70      120

D
80
/    \
60      100
/       /   \
20      70    120  ```

 A B C  Correct D
Questions on Balanced Binary Search Trees : Question 6 :
Which of the following is a self-adjusting or self-balancing Binary Search Tree

 Splay Tree AVL Tree Red Black Tree All of the above  Correct
Questions on Balanced Binary Search Trees : Question 7 :
Consider the following left-rotate and right-rotate functions commonly used in self-adjusting BSTs
```T1, T2 and T3 are subtrees of the tree rooted with y (on left side)
or x (on right side)
y                               x
/ \     Right Rotation          /  \
x   T3   – - – - – - – >        T1   y
/ \       < - - - - - - -            / \
T1  T2     Left Rotation            T2  T3
```
Which of the following is tightest upper bound for left-rotate and right-rotate operations.

 O(1)  Correct O(Logn) O(LogLogn) O(n)
Questions on Balanced Binary Search Trees : Question 8 :
Which of the following is true

 The AVL trees are more balanced compared to Red Black Trees, but they may cause more rotations during insertion and deletion.  Correct Heights of AVL and Red-Black trees are generally same, but AVL Trees may cause more rotations during insertion and deletion. Red Black trees are more balanced compared to AVL Trees, but may cause more rotations during insertion and deletion. Heights of AVL and Red-Black trees are generally same, but Red Black rees may cause more rotations during insertion and deletion.