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?
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
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
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
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 _____.
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
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