0 votes 0 votes Wanted asked Jan 20, 2017 Wanted 406 views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
Best answer 1 votes 1 votes 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. vipsharmavip answered Jan 20, 2017 • selected Jan 20, 2017 by Wanted vipsharmavip comment Share Follow See all 6 Comments See all 6 6 Comments reply Show 3 previous comments vipsharmavip commented Jan 20, 2017 reply Follow Share 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. 0 votes 0 votes Wanted commented Jan 20, 2017 reply Follow Share plz explain for other option 0 votes 0 votes vipsharmavip commented Jan 20, 2017 reply Follow Share 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. 0 votes 0 votes Please log in or register to add a comment.