What's wrong with my idea about preorder traversal

Question

When asked to create a BST given the preorder traversal, there are answers given like this: http://www.geeksforgeeks.org/construct-bst-from-given-preorder-traversa/

which require a lot of code.

My question is, why can't I just insert into an empty tree to give me the correct answer? Is there any example where simply inserting can lead to an incorrect answer? For example, in the example given in that link, we have {10, 5, 1, 7, 40, 50} as the preorder traversal. But doesn't just using the regular BST insert method 6 times in the order of the preorder list give the appropriate tree? Can I please get a counterexample and/or explanation about why I'm incorrect? I've been unable to come up with a counterexample.

Answer 1

Just calling insert the correct number of times should indeed produce the correct tree -- but it'll take O(n log n) complexity, where it can be done with O(N) complexity.

In all honesty, unless you're working with a lot of data, the difference may not be terribly significant for you.