GATE CSE
First time here? Checkout the FAQ!
x
+3 votes
154 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 (52.5k points)   | 154 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.3k 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.4k 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 Mar 2017
  1. rude

    5246 Points

  2. sh!va

    3054 Points

  3. Rahul Jain25

    2920 Points

  4. Kapil

    2732 Points

  5. Debashish Deka

    2602 Points

  6. 2018

    1574 Points

  7. Bikram

    1444 Points

  8. Vignesh Sekar

    1440 Points

  9. Akriti sood

    1424 Points

  10. Sanjay Sharma

    1128 Points

Monthly Topper: Rs. 500 gift card

21,556 questions
26,907 answers
61,269 comments
23,278 users