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)$