GATE CSE
First time here? Checkout the FAQ!
x
+3 votes
160 views
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 (55.7k points)   | 160 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 (13.9k points)  
edited by
@Tandua

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 Jul 2017
  1. Bikram

    5784 Points

  2. manu00x

    3602 Points

  3. Arjun

    1988 Points

  4. Debashish Deka

    1924 Points

  5. joshi_nitish

    1908 Points

  6. pawan kumarln

    1680 Points

  7. Tesla!

    1426 Points

  8. Hemant Parihar

    1334 Points

  9. Shubhanshu

    1180 Points

  10. Arnab Bhadra

    1124 Points


24,169 questions
31,187 answers
71,039 comments
29,512 users