Saurabh school lect..i think thiz is wrong interpretation..rt?

Question

Answer 1

The result is wrong,

remove the right subtree  : { 40 , 35 , 45 } of 15 in the image ,

And make the subtree { 40 , 35 , 45 }   as the right subtree of 30.

Comments

Ohk you are drawing in the correct manner, but after fixing 7 as the root
then only two nodes left 6 and 8,
From inorder,  we can dedude that 6 will become left child of 7 and 8 will become right
child of 7.  [Left , Parent , Right] [ 1 , 2 , 3 , 4 , 5 , 6 ,  7 , 8 ]
But pre oder says [ 7 , 8 ,  6 ]   it says ,  either [ 8 , 6  ] will be it's left subtree  or it's is right subtree or 8 will be left child and 6 will be it's right child.  [ parent , left ,  right]
But it can't be possible because inorder say's 6 will be it's left child of 7 and 8 will be it's right child
Also , left have small key as compared to parent and right have large key as compared to parent.
Hence we can't create correct binary search tree by assuming option (A) as preorder.

---

plz explain for other option

---

Just understand the concept and try it your self.

Ok it is simple first value of preoder is the root of the tree .

Fix the root.

Now search the fixed root in the inorder, all nodes which are present in  the left will come in left subtree of your

bst and all nodes which are present to the right in the inorder , will come to right subtree of root.

Now solve for left and right subtree.

For all those nodes which come in left subtree , the node which become the left child of root is that node

which present first in preorder.  and then again find it's position in inorder and nodes which are left to the position in inorder , will come to left subtree of that node and nodes which are present in the right in inorder will come to it's right subtree.

Do these process for each part of each node left and right.