Question 1 |
An AVL tree T contains n integers, all distinct. For a given integer k, what is time comlexity of an algorithm to find the element x in T such that |k-x| is minimized?
\Theta ( n) | |
\Theta (\log n) | |
\Theta (n \log n) | |
\Theta (n^2) |
Question 1 Explanation:
INSERT k, then find the PREDECESSOR and SUCCESSOR of k. Return the one whose difference with k is smaller. All three methods take \Theta (\log n) time.
Click to Join Our Telegram Group for Latest Update of MOCK TEST 
Click Here to Practice ALL Previous MOCK TEST FREE
Click to Join Our Telegram Group for Latest Update of MOCK TEST
Click Here to Practice ALL Previous MOCK TEST FREE
Question 2 |
Given a binary search tree containing N integers, time complexity of creating an AVL tree containing the same
values without destroying the original BST in the process is
O(N) | |
O(log N) | |
O(N log N) | |
O(N log log N) |
Question 2 Explanation:
Traverse the BST (in any order) as you visit a node, insert that value into the AVL Tree. Each AVL Tree insert takes O(log N). You have to perform such N insert. So, total time is O(N log N).
Click to Join Our Telegram Group for Latest Update of MOCK TEST
Click Here to Practice ALL Previous MOCK TEST FREE
Click to Join Our Telegram Group for Latest Update of MOCK TEST
Click Here to Practice ALL Previous MOCK TEST FREE
Question 3 |
We have n distinct values stored in a height balanced (AVL) binary search tree. Which of the
following statements is always true?
The value at each node is the median of the values in the subtree rooted at that node. | |
The shortest path between any pair of nodes is at most O(log n). | |
For any node, the difference between the size of the left subtree and the right subtree is at most 3. | |
The number of leaf nodes is greater than or equal to the number of internal nodes. |
Question 3 Explanation:
A height balanced tree has overall height at most O(log n), so the shortest path between any pair of nodes
is always at most O(log n).
The following AVL tree is a counterexample for all other statements.
Click to Join Our Telegram Group for Latest Update of MOCK TEST
Click Here to Practice ALL Previous MOCK TEST FREE
The following AVL tree is a counterexample for all other statements.
Click to Join Our Telegram Group for Latest Update of MOCK TEST
Click Here to Practice ALL Previous MOCK TEST FREE
Question 4 |
The number of ways in which the numbers {1,2,3,4,5,6,7} can be inserted in an empty AVL tree, so that we don't have to perform any rotations on it and value of root node as 4, is _____.
64 | |
24 | |
48 | |
128 |
Question 4 Explanation:
One possible is insert in the order {4, 2, 6, 1, 3, 5, 7} to make an AVL tree.
The ordering of {2, 6} and the ordering of {1, 3, 5, 7} do not matter. One can see the resulting tree is perfectly balance AVL tree.
Therefore, Total possible sequence of elements = 2!*4!=2*24=48
Click to Join Our Telegram Group for Latest Update of MOCK TEST
Click Here to Practice ALL Previous MOCK TEST FREE
The ordering of {2, 6} and the ordering of {1, 3, 5, 7} do not matter. One can see the resulting tree is perfectly balance AVL tree.
Therefore, Total possible sequence of elements = 2!*4!=2*24=48
Click to Join Our Telegram Group for Latest Update of MOCK TEST
Click Here to Practice ALL Previous MOCK TEST FREE
Question 5 |
What is the running time of an efficient method to merge two balanced binary search trees with n elements each into a balanced BST.
O(n log n) | |
O(n) | |
O(log n) | |
O(n log log n) |
Question 5 Explanation:
We can start by doing an in-order walk of both trees concurrently. At each
step, we compare the two tree elements and add the smaller one into a list, L, before
calling that element's successor. When we finish walking both trees, L will contain a
sorted list of elements from both trees. This takes O(n + n) = O(n) total time.
Now, from the sorted list, we want to create a balanced binary tree. We can do this by setting the root as the middle element of the list, and letting the first half of the list be its left subtree and the second half be its right subtree (recursively creating the balanced subtrees as well). This also takes O(n + n) = O(n) time.
The total time for this algorithm is therefore O(n)
Click to Join Our Telegram Group for Latest Update of MOCK TEST
Click Here to Practice ALL Previous MOCK TEST FREE
Now, from the sorted list, we want to create a balanced binary tree. We can do this by setting the root as the middle element of the list, and letting the first half of the list be its left subtree and the second half be its right subtree (recursively creating the balanced subtrees as well). This also takes O(n + n) = O(n) time.
The total time for this algorithm is therefore O(n)
Click to Join Our Telegram Group for Latest Update of MOCK TEST
Click Here to Practice ALL Previous MOCK TEST FREE
There are 5 questions to complete.
Suggested Mock Test For You.
ALL FREE Mock Test of GATE CSE