'Can we construct a BST from a pre-order traversal simply by inserting the elements in preorder traversal in sequence into an empty tree?

Given a preorder traversal of a BST.I have to construct the BST. Can I construct the BST from the preorder traversal simply by creating a empty BST and then inserting the elements in preorder traversal one by one starting from the first element and ending at the last element into the empty BST?

For example,consider the following BST:-

    10
   /   \
  5     40
 /  \      \
1    7      50

Its preorder traversal is :

10 5 1 7 40 50

By creating a empty BST and then inserting elements in preorder traversal one by one starting from the first element gives me the exact BST explained as follows:

(empty tree)

insert first element of preorder traversal: 10

   10

insert second element of preorder traversal: 5

   10
   /
  5

similarly,


     10       
   / 
  5  
 /  
1   

     10
   /   
  5    
 /  \  
1    7 

     10
   /   \
  5     40
 /  \ 
1    7


     10
   /   \
  5     40
 /  \      \
1    7      50

Here I have constructed the exact BST just by inserting the elements in preorder traversal one by one into an empty tree. Will this algorithm work at all cases?Is there any case where this algorithm wont work?

void insertIntoTree(struct* Node,int val)
{
   if(Node == NULL)
   {
       Node = createNewNode(val);
       return;
   }
   if(val < Node->val)
      insertIntoTree(Node->left,val);
   else
      insertIntoTree(Node->right,val);

}
int main()
{
  int preorderlist[] = { 10,5,1,7,40,50};

  for(int i=0;i <= preorderlist.size();i++)
  {
     insertIntoTree(TreeRoot,preorderlist[i]);
  }

}
algorithmbinary-search-tree


Solution 1:[1]

Your code will work, but it is not efficient. You are not using the pre-order property of the array. In fact, your code is building a BST from a general array. To improve your algorithm, you can build the tree recursively, keeping minRange and maxRange in each node. If the next element is outside the range of the current node, return back to the parent node.

EDIT: You will get the same tree, but the complexity will be O(N*logN) if the original tree was balanced and O(N^2) if it was not.

I don't want to write the code for you, but I'll try to explain my algorithm better: Keep a pointer to the last node you inserted. Also for each node keep the range of the subtree. When inserting an element, start with the pointer you kept. if the new node is in the range, insert it as a child and update the pointer. if it is not in the range, move the pointer up to its parent and try to insert there. To update the range: if you insert the new node as a left child, set its maxRange to its parent value. and respectively set minRange for a right child. The complexity will be O(N) for all cases.

Solution 2:[2]

Yes , it will work . The reason for that can be understood as follows - Since in the pre order traversal , the root node is written before its branches , therefore while traversing the array of values , you will always encounter the parent first and then its branches , and hence the tree generated by this method will be the same as the required tree . However I dont think this method will work if Inorder and Postorder traversals were given , and as others have pointed out , this is less efficient than the resursive way of doing it (althought I dont know why , further edits explaining the time complexities of both the algorithms are welcome )

Sources

This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.

Source: Stack Overflow

Solution Source
Solution 1
Solution 2 Ayush Agarwal

Related Questions