590 views
1 votes
1 votes

time complexity to construct bst from preorder?

a) O(n) b)O(nlogn) c)O(n^2) d)O(1)

given O(nlogn)

my doubt:- there are two approaches one that gives O(nlogn) (by finding the inorder traversal)

                and the other that gives O(n) :-

set a range {min .. max} for every node. Initialize the range as {INT_MIN .. INT_MAX}. The first node will definitely be in range, so create root node. To construct the left subtree, set the range as {INT_MIN …root->data}. If a values is in the range {INT_MIN .. root->data}, the values is part part of left subtree. To construct the right subtree, set the range as {root->data..max .. INT_MAX}.

reference:-http://www.geeksforgeeks.org/construct-bst-from-given-preorder-traversa/

so shouldn't it be O(n) ?

Please log in or register to answer this question.

Related questions

2 votes
2 votes
3 answers
1
0 votes
0 votes
0 answers
3
2 votes
2 votes
1 answer
4
arya_stark asked Jul 4, 2018
7,131 views
Preorder is same as :a) depth-first order b) breadth-first searchc) topological order d) linear order