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