GATE CSE
First time here? Checkout the FAQ!
x
+3 votes
155 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 (53.2k points)   | 155 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.5k 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 Apr 2017
  1. akash.dinkar12

    3660 Points

  2. Divya Bharti

    2580 Points

  3. Deepthi_ts

    2040 Points

  4. rude

    1966 Points

  5. Tesla!

    1768 Points

  6. Debashish Deka

    1614 Points

  7. Shubham Sharma 2

    1610 Points

  8. Prashant.

    1492 Points

  9. Arjun

    1472 Points

  10. Arunav Khare

    1464 Points

Monthly Topper: Rs. 500 gift card

22,086 questions
28,062 answers
63,297 comments
24,169 users