How to make a BST from a inorder traversal?

#1

how to make a BST from a inorder traversal?

#2

hey @shakul, I think you cannot build BST from inorder traversal. The reason is you need to build root firstly and with inorder traveral you never know the exact position of root until specified.

#3

how to solve this question then

#4

also can i build a unique BST from preorder or postorder traversal?

#5

hey @shakul, question has not mentioned root,therefore this traversal can give multiple trees. But we can build the tree considering middle most value as root.

Watch the lecture where Binary tree was build using an array, same logic will be used here.

node* build(int * arr,int s,int e)
{
if(s>e)
{
return NULL;
}
int mid=(s+e)/2;
node* root=new node(arr[mid]);
root->left=build(arr,s,mid-1);
root->right=build(arr,mid+1,e);
return root;
}

#6

yeah,i know this,plz tell me how you know ki iss method se jo tree aayega uska preorder vhi hoga jo submission m hona chahiye,
also can you remain on this thread for a little while?

#7

hey @shakul, yes submission will be same.

#8

can i buld a unique BST from either of preorder or post order?

#9

hey @shakul, yes you can build unique BST with pre and post beacuse you are aware of root node in that case. In preorder travesal, first number is root and last in post order.

#10

can you give me an example to clear this?

#11

hey @shakul there is a video lecture in your course for preorder with this name CPP - Binary Search Tree - Insertion & Build

Please go through this lecture once

#12

what is the time complexity of insertion and build code in CPP binary search tree?
i think that it should be o(n) as we are traversing
each node once

#13

hey @shakul, for build function it is O(N) and for insertion is O(N) in worst case. So total complexity is O(N2)

#14

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.