5.11 Construct Binary Search Tree(BST) from Preorder( example) |Data structures

hi guys welcome back in this video I'm going to discuss with you how to construct a binary search tree when only either pre-order is given or postorder is given fine okay so let us start suppose the question is you're supposed to construct a binary search tree and the pre-order traversal of that trick is given only the pre-order traversal of that trace given okay either the question would be it would be asked he find out the inorder traversal of this tree or to find out the postorder traversal of this tree or construct a binary search tree using this preorder traversal take care three questions you have been asked fine you know de Traverse we'll find out corner post order traversal find out Cornell you're supposed to construct a binary search tree fine okay now only pre-order is given now but epithet order traversal is first of all route would be traversed then left and then right fine now how to find out in order traversal of this tree inorder traversal would be C in order of binary search tree would always be in ascending order sorted data wouldn't be there take care data would be ascending order I'm just talking about this binary search tree I'm not asking about I'm not telling about any binary tree okay this condition is true for only binary search tree the inorder traversal of a binary search tree would always be give you the data in ascending order fine now C preorder is given so obviously we have the data of that tree now find out that in order in order would be data would be in ascending order so just arrange the data five after five we have 16 17 18 19 20 60 70 n you define okay this would be the inorder traversal of this mind research tree having this preorder okay and everybody knows the inorder traversal is first left part would be true then root and then right sub-tree of that first of all this left subtree then root and then right supreme fine now construct a binary search tree we have in order we have pre-order okay now see first step is you are supposed to find out first of all the root but should be the root of that BST fine the root of kaha say find out curseth o from pre-order only because the first element would be true yeah happy root yoga in the middle of this one so we can't say he left makan saga right in the cones over kuru toga so you'll find out the root from the pre-order see this 20 would be root because first one is rude then left and then right so 20 would be root of our subtree I'm going to right here at this place and mark 20 in in order here we have 20 fine so this one is root and to the left of this route to the left of this root we have left subtree and right make up right subtree so this would be left subtree or left part and this would be right path 20k left may upkeep on console is sub 3 over 5 16 17 18 and 19 and to the right of 20 you would have 60 70 and 85 fine now either first of all you can go to the left or right now construct thus this train from this suppose we are going to the left subtree now we are having 5 16 17 18 and 19 you can see 5 16 17 18 and 19 this is left subtree okay now what do I have to do is out of these numbers you can find out the number in pre-order with just which number is coming first out of these numbers see 16 is coming first 5 is after 16 17 is also after 18 is also after and I is also after 16 top of these numbers 16 is coming first in the pre-order fine so to this left subgrade to this left subtree 16 would be rude fine the tree would be 20 here's 16 out of this subtree 16 would be root because 16 is coming first and to the left of 16 we have 5 and to the right of 16 we have 17 18 and 19 17 18 and 19 fine and to the right of this one we have 60 70 and 85 okay now see this one is root now to the left we have only five two five here though I'm making here next after five only we have one number two taking here next is coming that is five the five would be root the article problem Houdini now check out of this sub tree out of 17 18 and 19 fine check out which number is coming first in this pre-order out of 17 18 and 19 which one is coming first 18 because 17 is after 18 19 is after 18 so 17 is coming sorry 18 is coming first so for this subtree 18 would be root and to the left of 18 we have 17 to the right of 18 we have 19 so this would be updated as 18 would be root here we have left 17 here we have right 19 because root he left me up my left subtree ogres make our upper right subtree fine okay now we have already done with this left subtree yet Ravitch can now go to this right subtree of this 20 60 70 and 85 here we can't say which one would be the root which one would do in the left node and which one would be the right one so yeh kaisa Petacchi lega from this pre-order now to 60 70 and 85 which number is coming first in this pre-order check out the 60 60 is coming first 70s after 60 85 is also after 60 so this 60 would become the rule the number which come first in this pre-order that would become the route this is the rule out of these 360 would be rude fine and 60 would be the road okay and 60 K now check out it in order 60 K write Omega has 70 and 80 the root K make yoga root K the wrong way that would be right sub-tree 66 GK right may open a passage 70 and 85 check out any nodal C 60 K right may both happening 60 hum a pataga 60 would be the route and from this one we can say route here item a job' hoga that would be right subtree of that route 60 k right making over 70 and 85 now out of these two we cannot say which one is route so you can say potentially aha may we would check out we have to check out this pre-order thought of these two numbers which is coming first 85 85 is coming first but if I could be the route now see 85 is rude so route a left may seventies to the left of this route right this would be the root k left make out the left subtree so 85 would be the route or SK left make our graph come 70 hi so this is your binary search tree you can create BST when only pre-order is given so in next video I am going to discuss with you how to construct a BS tree if post order is given fine till then bye bye take care

Channel: Jenny's lectures CS/IT NET&JRF

Views: 154,849

Keywords: binary search, bst, avl tree, binary search java, optimal binary search tree, complete binary tree, what is binary tree, threaded binary tree, binary search tree deletion, full binary tree, binary search tree pr, preorder traversal, binary tree in data structure, binary search tree, ugc net computer science, study material, preparation, GATE computer science preparation, coaching classes, algorithms, jennys lectures, jayanti khatri lamba, data structures, notes, pdf

Id: GW63gMgfeS8

Length: 8min 58sec (538 seconds)

Published: Sun Jan 27 2019