Q46

MCQ2 marks, −0.5

You are given the postorder traversal, $P$ , of a binary search tree on the $n$ elements $1, 2, \dots, n$ . You have to determine the unique binary search tree that has $P$ as its postorder traversal. What is the time complexity of the most efficient algorithm for doing this?

(A)

$\Theta(\log n)$

(B)

$\Theta(n)$

(C)

$\Theta(n\log n)$

(D)

None of the above, as the tree cannot be uniquely determined

Loading…