Balanced Binary Search Trees

Balanced Binary Search Trees

Question 1

What is the worst-case time complexity to search an element in a balanced binary search tree with N * 2^N nodes?

1. O(log N)
2. O(N log N)
3. O(N)
4. O(N * 2^N)

Answer: C

Time taken in the worst case to search an element will be equal to O(H), where H is the height of a binary search tree. Since it is a balanced binary search tree, the tree's height will be logarithmic in terms of the number of nodes.

H = O(log(N * 2^N)) 

H = O(log(N) + log(2^N))

H = O(log(N) + N)

Since log(N)<<N, the time complexity can be written as O(N).

Question 2

What can be the maximum height of an AVL tree having 7 nodes? Consider that a tree with only one node has a height of 0.

1. 2
2. 3
3. 4
4. 5

Answer: B

In AVL trees, the difference between the height of two children of a node can be at most 2. The following diagram shows the most unbalanced AVL tree that we can get with 7 nodes.

Question 3

What is the closest worst-case height of an AVL tree with N nodes?

1. 2 log N
2. 1.44 log N
3. Depends on implementation
4. Theta(N)

Answer: B

Let N be the number of nodes in an AVL tree of height H. Then N can be represented in terms of H as:

N+1 = 1/sqrt(5) * ((1 + sqrt(5))/2)^(h+3) 

On solving the above equation, we will get that H ~ 1.44*logN.

Question 4

Which of the following is a self-balancing Binary Search Tree?

1. Splay tree
2. AVL tree
3. Red Black tree
4. All of these

Answer: D

All the three given trees- Splay, AVL, Red-Black tree are self-balancing binary search trees.

Question 5

We use left-rotate and right-rotate functions to balance the height of a binary search tree. What is the time complexity of these functions?

1. O(1)
2. O(log N)
3. O(log log N)
4. O(N)

Answer: A

The rotation operations are performed in constant time as only a few pointers are changed. You can read in detail about rotations on self-balancing binary search trees here.

Question 6

Which of the following is true about Red-Black trees?

1. The distance between the root and the furthest leaf is twice the distance between the root and the nearest leaf.
2. At least one child of every black node is red.
3. The root can be red.
4. A leaf node may be red.

Answer: A

The root and the leaf nodes (NULL) are always black in a Red-Black tree. 

1. Also, in a Red-Black tree, every path from the root to a leaf has the same number of black nodes. 
2. Every Red node must have two black child nodes.

Let R be the count of red nodes of a path from the root to a leaf and B be the count of black nodes. From (1) and (2), we can say that B>R.

The maximum and minimum distance from the root to the leaf can be B + R and B, respectively.

Since R < B, B + R < 2*B.

Thus, the distance between the root to the furthest leaf is no more than twice the distance between the root to the nearest leaf.

Question 7

Is the following statement true?

“A Red-Black tree can have all black nodes.”

1. Yes
2. No

Answer: A

A perfect Binary Search Tree with all black nodes does not violate any of the properties of Red-Black trees.

Question 8

The recurrence relation for finding the complexity of search operation in the self-balanced binary search tree is:

1. T(n) = 2T(n/2) + k
2. T(n) = T(n/2) + k
3. T(n) = T(n/2) + log(n)
4. T(n) = T(n/2) + n

Answer: B

Searching operation in a self-balanced binary search tree takes O(log N). In each operation, the number of candidate nodes gets nearly halved. Thus, we get the relation T(n) = T(n/2) + k.

Question 9

There are two balanced binary search trees B1 and B2, having N and M elements, respectively. What is the time complexity of the best-known algorithm to merge both these trees?

1. O(N + M)
2. N log M
3. M log N
4. O(N^2 + M^2)

Answer: A

We know that the inorder traversal of a binary search tree gives a sorted array. We will perform an in-order traversal of both B1 and B2 to get two sorted arrays. We then merge both these arrays into a single sorted array. This can be done in O(N + M). After this, we recursively create the final binary search tree by picking the middle element and calling the recursive function on the left and right halves.

Question 10

What is the worst-case complexity of initially adding N^2 elements into an AVL tree containing N elements?

1. O(N^4)
2. O(N^2)
3. O(N^2 log N)
4. O(N^3)

Answer: C

The time complexity to insert one node in an AVL tree is O(log N). 

To insert the 1st node, the time complexity will be: O(log(N))

To insert the 2nd node, the time complexity will be: O(log(N+1))

To insert the 3rd node, the  time complexity will be: O(log (N+2))

…

To insert the N^2th node, the  time complexity will be: O(log (N + N^2))

Thus, total time taken is: log(N) + log(N+1) + log(N+2) + … log(N + N^2)

= log(N * (N+1) * (N+2) * (N + N^2))

= log(N^(N^2))

= N^2 log(N)

Check out this problem - Root To Leaf Path

Key Takeaways

In this article, we discussed various quality multiple-choice questions based on Balanced Binary Search Trees. We hope that this blog has helped you enhance your knowledge of balanced binary search trees and if you would like to learn more, check out our articles on code studio. 

Recommended problems -

• Binary Array Sorting
• Vertical Order Traversal of a Binary Tree
• Leaf Nodes in Binary Tree

Do upvote our blog to help other ninjas grow. Happy Coding!