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

Question

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

insert second element of preorder traversal: 5

   10
   /
  5

similarly,


     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]);
  }

}

Not sure I understand the question. What are the "all cases" that you are referring to? — RobertBaron
@RobertBaron "Is it true that converting an arbitrary BST to preorder form, and then converting back to a BST, will always produce a result identical to the original BST?" As with most things involving BSTs, the answer involves recursion. — Raymond Chen
You are missing child node references. Just creating a new node won't get you a correct BST. You need to return the node and insert into parent's left or right reference accordingly, because currently the left or right reference passed as a parameter for non existing value would be NULL. — nice_dev
@RobertBaron Is there any case that the above algorithm wont work? — Mike Tsubasa

Shuki Avraham Shuki Avraham · Accepted Answer · 2019-06-08T14:48:47

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.

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

1 Answers