BST from Preorder by just inserting the nodes in same order

Question

To construct a BST from the preorder traversal given, if I try to insert in the BST in the same order as given in preorder, I get the BST. So, we don't to create the in-order by sorting of the elements or perform any other alogrithm?

Is there an example which shows that tree can't be constructed by just inserting the elements ?

Answer 1

You're correct... you can just insert the nodes in the order given by a preorder traversal to rebuild the tree.

The first node inserted must be placed at the right place, since it's the root and a preorder traversal always places the root first. What follows in the preorder traversal is the preorder layout of the left subtree followed by the right subtree. As the left subtree nodes are inserted, they are inserted by going left from the root, then recursively applying the same procedure on that subtree. The right subtree is rebuilt the same way. Using induction, you can formally prove this if you like.

Hope this helps!