First time here? Checkout the FAQ!
+3 votes
You are given the pre-oder traversal T of a binary search tree on the n elements 1, 2, 3,...n. You have to determine the unique binary search tree that has T as its pre-oder traversal. What is the time complexity of the most efficient algorithm for doing this?

(A)$\Theta (n^{2})$

(B)$\Theta (n log n)$

(C)$\Theta (log n)$

(D)$\Theta (n)$
asked in DS by Veteran (58.4k points)   | 167 views

2 Answers

+4 votes
Best answer

Check this link.

Quoting the relevant portion:

We left out some details on how we search the root value’s index in the inorder sequence. How about a simple linear search? If we assume that the constructed binary tree is always balanced, then we can guarantee the run time complexity to be O(N log N), where N is the number of nodes. However, this is not necessarily the case and the constructed binary tree can be skewed to the left/right, which has the worst complexity of O(N2).

A more efficient way is to eliminate the search by using an efficient look-up mechanism such as hash table. By hashing an element’s value to its corresponding index in the inorder sequence, we can do look-ups in constant time. Now, we need only O(N) time to construct the tree, which theoretically is the most efficient way

Now, since options are given in terms of Theta, we need to prove the lower bound as well. Since we have to traverse the inorder sequence at least once, to find each element, lower bound would be $\Omega(n)$. So run time would be $\Theta(n)$

Since it is asking for the most efficient method, so answer should be option (D) $\Theta(n)$

answered by Loyal (3.4k points)  
edited by
@Kapil: Since we're given numbers 1,2,3,...$n$, we're given the inorder sequence.
I wrote it in flow. Then, edited that :)
Happens with me as well. :P
What will be the time complexity when elements are not consecutive. but are sorted but not consecutive. like 10, 20 , 30... Will the complexity change. Again hash table can be used Right?
Yes, it should be same. .
0 votes
D should be answer. beacuse the seach for the element in the inorder can be done in constant time. Take an array and push inorder in it, Now we exactly know the index of the element in the inorder.
answered by Veteran (14.1k points)  
edited by

plz plz go for detail.

Such ans not understandable at all.
Time complexity is max when we have a skewed tree. If we have a skew tree everytime only one node will be in position and we have to find that node in the given post order too. so the time complexity is due to the same. (n-1) time we have to search a element in the preorder. But here as number are given we can use binary search instead of the linear search . which decrease it complexity. It may not be the correct answer what is the answer.

Related questions

Top Users Sep 2017
  1. Habibkhan

    6970 Points

  2. Warrior

    2490 Points

  3. Arjun

    2368 Points

  4. rishu_darkshadow

    2136 Points

  5. A_i_$_h

    2004 Points

  6. nikunj

    1980 Points

  7. makhdoom ghaya

    1760 Points

  8. manu00x

    1750 Points

  9. Bikram

    1744 Points

  10. SiddharthMahapatra

    1718 Points

26,060 questions
33,668 answers
31,079 users