5.7 Construct Binary Tree from Preorder and Inorder traversal with example | Data structures

hi guys welcome back in this video we'll discuss how to construct a binary tree from pre-order and inorder traversal fine so say this one is the pre-order traversal of a tree and this one is inorder traversal of a binary tree and you are supposed to construct a binary tree from these traversals fine see as you all know pre-order is route then left and then right fine and the inorder traversal is row left then route and then right ok now first of all when you see you are supposed to construct a tree or you can say binary tree your first step is to find out the root of that tree okay now how you can find out root of the tree from these traversals fine from a dock in order traversal you can't find root because root is in the middle of left and right but we can't say which one is root kaha Paves committed over kidney elements to the left of that root and how many elements are to the right of that root fine so you can find out root of the element from the root of the tree from this pre-order traversal because in pre-order traversal root is always first firstly traversed so in pre-order traversal we will scan scan this data from this left to right now first is one now one would be root because starting way up in a pre-order traversal make your head root will always be traversed now the one would be root over binary tree fine now next step is to find out its left subtree and right suffering now I will find out the element of left subtree and the element of right subtree from this in order traversal see from this inorder traversal find out where is this one this one it is our one and this one is wrote now see to the left off route left sub-tree is there into the right of route that right part or you can say the right subtree will be this the one all the elements to the left of this one would be the left subtree and all the elements to the right would form the right subtree fine so in the left to the left of this subtree how many elements and which elements are there eight four ten nine eleven two and five these are to the left of this end to the right six three and seven six three and say these elements will form the right subtree fine now see now first of all you can construct this left subtree or you can construct the right subtree fine we'll go to the left part now out of these elements which should be the root of this left subtree see a tree is complete till this level we have only find this one as a root now from these elements find out which one would be the root of this left subtree now how this is to be find out from this preorder traversal right the rule is out of these elements find C out of these elements the element which is coming first in this preorder traversal when you scan this traversal from left to right fine that first element would be the root of this left subtree find out out of these elements which is coming first when you will go from here to there one is already there now second C out of these elements we finally found this - now two would be root of this left subtree now out of these elements which are the left of this two and which are which elements are right of this two we'll find out left and right left and right find out can they kill you will go to the in order traversal find out the location of two here we have this too now this one is our route all the elements to the left would be the left sub-tree and all the elements to the right of this two would be right sub-tree out of these elements fine so out of these elements to is route and all the elements to the left on once elements a bit to the left of this two we have 8 4 10 9 and 11 these elements would be to the left of this 2 and to the right of this to it we have only this five only one fine only five we have now our problem is divided into you know that subproblem now we have these elements only now out of these elements find out which would be the root of this left subtree left subtree of this to eight for ten nine eleven and root find out connect today we will go to the pre-order travel self out of these elements the elements which is coming first when you scan this pre-order from left to right that would be the root of this left subtree the out of eight for 10 nine eleven which element is coming first when you will go from this to from left to right for is coming first out of eight for ten nine eleven four is coming first now four would be root of this left subtree now left and right of this four would be which elements would be to the left of this 4 and which elements are to the right of this for you find out connect ely we will go to the in order traversal now find out the location of food here we have the sole fine 4 is a root root key left make our left subtree and root right make a basic neighbor element so me that will form a supreme now to the left of 4 we have 8 out of these elements only we are not going to check 6 3 7 out of these elements only 40 left map Nebraska hi 8 now 8 would be the left of this war and 10 nine eleven ten nine eleven are ten 9/11 these are to the right of this four fine now here we have only one element that's fine now construct the subtree from 10 9 and 11 fine now out of these elements which would be the root and to find out the root we'll go to the preorder traversal now find out which elements from these elements from 10 9 and 11 which element is coming first when you go from here to here 10 9 11 I guess 9 10 or 11 are coming after this 9 so 9 would be root fine now this out of 10 and 11 which which would be to the left of 9 and which would be to the right of this 9 we'll find the left and right part when you will go to this in order traversal now locate this 9 in this inorder traversal here we have this 9 fine and 10 is to the left of 9 and 11 is to the right of 9 the left of 9 whole left of this root would be the left part so 10 would be to the left of 9 and 11 would be to the right of 9 so this has a left subtree we are done with our left subtree now come to the right subtree right subtree may we have only six three and seven three elements which would be the root of this right subtree find out out of six three and seven which is coming first when you traverse this preorder from this scan the pre-order traversal from left to right six three and seven three three is coming first six and seven are coming up to this 3 2 3 would be route now out of 6 and 7 which element would be to the left of this and which element to the right of this 3 to find out this we will go to the in order traversal now locate this three in this in order to ever sell here we have this three and three is a root and six is to the left of three and seven is to the right of three so six would be to the left part of this three and seven would be right part of this three fine so this is our binary tree and you can construct this free from this pre-order and this inorder traversal if you want to verify it then you can now find out pre-order and inorder traversal of this tree and if pre-order and inorder are same as given in the question then you can say our trees you have formed a right binary tree fine so I'll see in the next video till then bye bye take

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

Views: 323,912

Keywords: prim's algorithm in data structure, balanced binary tree, floyd warshall, what is spanning tree, minimum spanning tree definition, what is minimum spanning tree, binary tree, binary tree from preorder and inorder, preorder, inorder, ugc net computer science, gate computer science, GATE, jenny's lectures, construction of binary tree, prims and kruskals, dsa, ds notes, pdf, algorithms, types of binary tree, best youtube channels, bt, it, cse, engineering, study material, preparation

Id: PoBGyrIWisE

Length: 9min 44sec (584 seconds)

Published: Thu Jan 31 2019