+3 votes
167 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 | 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
Answer is B)

:(
It will be D). only .
ok :)
^ what ll be ans if postorder given instead of preorder and rest r same ?
@Saurabh, again $O(N)$ only.

@Pratyush, Actually your answer says only $O(N)$, and to show $\Theta (N)$ you have to also show that why it takes $\Omega (N)$.

@kapil is it nt the same as http://gateoverflow.in/458/gate2008-46

@Saurabh,

Yes, that's the same question. But, you can check the links

Might be this method was introduced after $2008$ !!

@Kapil: I agree, but the post uses big-Oh notation loosely, where they could have used Theta notation. This is common in competitive programming world where they use Big-Oh almost exclusively. Although that would still require proving the lower bound. Which I think is obvious since we have to traverse the inorder sequence at least once, which makes the lower bound $\Omega(n)$
.........
@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
@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.

0 votes
1 answer
1
0 votes
0 answers
2
+3 votes
1 answer
3