TREE PRACTICE PROBLEMS | Tree Traversal Algorithms | DSA Course | GeeksforGeeks

Key Takeaways

hello everyone my name is Karan masu welcome to this video so in the last video we talked about the basics of tree data structure in this video we will be looking at the three standard binary tree traversal algorithms okay so first one is the inorder traversal method another is the pre-order traversal and another one is the post order traversal so what are the differences in all three of this in in order traversal we first Traverse the left sub tree then we note down the root node value and then we Traverse the right sub tree okay in I'll also tell you a trick how to remember this don't worry in pre-order traversal we first Traverse the root node then we Traverse the left sub tree and then we Traverse the right sub tree in the post order traversal we first Traverse the left sub tree then the right sub tree and then the root node okay so let me take an example so let us take an example of a binary tree so let's say this is 10 2 12 14 3 and 9 okay and I'll take the same values here okay so I'll select this and I'll copy it and I'll paste it here okay and I'll also paste it here okay so now what is the in order traversal in order traversal means you first Traverse the left sub tree then root and then the right sub tree okay so you first Traverse the left sub tree so you go to the left now still there is a left subt so you still go to the left so your output is 14 then you Traverse the root node so when you backtrack two is the root node like if I look at the so starting from the root node first we go in the left sub tree because it is first left sub tree now recursively from two also I'll go in the left sub tree so I'll come here so I'll print 14 now there is no more left sub tree so I'll go back now for this sub tree 24 and 3 two is the root node so after left sub tree is done the left sub tree of two is done so root node will be Tak taken and then the right sub tree will be taken so three will be taken then we'll backtrack from here and go back here so 10 left sub tree is over now 10 will be return because it is the root node then we will go into its right sub tree so first left sub tree is done then root is done now we go in the right sub tree so it is 12 and 9 in this order it will be printed right because when we go to 12 here also first left sub tree will be Travers there is no left sube then root will be Travers so 12 will be Travers then then nine will be Travers because it's the right one okay similarly here it will be root left right and here it will be left right root now uh let me tell you a trick how to write down these values on a pen and paper I mean how to do in order traversal pre-order traversal and postorder traversal efficiently on a pen and paper and then I'll also tell you how do you remember this order and then we will look at the code of all three traversals okay so first of all let me just remove this okay and let me paste the same tree here again now see this was the in order traversal right so whenever you want in order traversal what do you need to do is make pointers at the bottom of the nodes okay when you want to do pre-order traversals make it on the left hand side and when you want to do Post order traversal make pointers on the right hand side okay now in all three of them Traverse the peripheral of the tree in this way okay starting from here to here okay you go here and you go here here also okay and here also okay now when you are traversing whenever you encounter this pointer you note down that nodes value so while I'm going here the first pointer the first point which I encounter is this one so I'll note down 14 then from here I'll encounter two so I'll write down two then I'll encounter three so I'll write down three then I'll encounter this point that is 10 so I'll write down 10 then I'll encounter uh here I'll encounter 12 so I'll write down 12 and then I'll encounter nine I'll encounter this point at the last so I'll write down nine you can see we have got the same answer so this is in order traversal now in pre-order traversal it is root left and right so when I start traversing the first of all I'll encounter this point so I'll write down 10 then I'll encounter this point so I'll write down two then I'll encounter this point so I'll write down 14 then I'll encounter this point so I'll write down three then I'll encounter this point so I'll write down 12 and then I'll encounter this point so I'll write down nine okay so I this is the pre-order traversal let's come to the post order traversal so I'll come here come here come here and first I'll encounter this one so I'll write down 14 then I'll encounter this one so I'll write down three then I'll encounter this one so I'll write down two then I'll encounter this one so I'll write down N9 then I'll encounter this one so I'll write down 12 and then I'll encounter this one so I'll write down 10 so this is the post order traversal in with left right and then root is traversed you can also see root is at the end so this root value is at the end okay so this is the basic of in order traversal pre-order traversal and post order traversal now how do you remember this uh this order okay so that you do not make a mistake see this is in order traversal this is pre-order traversal and this is post ordered raval in all three of them left subtree is before the right sub Tree in all three of them left sub tree is before the right sub Tree in in order traversal the root is in order it is in between in the pre-order it it is pre it is before left and right sub Tre in post order traversal it is post so root is after left sub tree and right sub tree so this is left root right this is root left sub tree right sub tree this is left sub tree right sub tree and root now let's look at the actual implementation of all these three questions and submit them so this is the pre-order traversal question let's look at the code we have already understood the concept so we had to complete this function pre-order traversal where root of the binary tree was given and we needed to return the pre-order traversal in a vector so I have taken one vector answer and called the pre-order traversal function and I have passed the root and Vector in that what does pre-order traversal do if the root is not null pre-order means root left sub tree right sub tree so first of all it will push back this nodes value in the answer Vector push back root data then Traverse on the left subre and then Traverse on the right sub so it is root left and right let's submit the code Okay so we have solved this successfully let's look at the next one okay so this question is on post order traversal uh postorder traversal is uh left sub Tre right sub Tre and root node okay so if I look at the code I had to complete this post order function I have taken one vector answer I have taken post order traversal and pass the root node pointer and the answer vector and if root is not null post order means left sub Tre right sub Tre and root node so Traverse on the left sub Traverse on the right sub Tre and finally push back the value of the current root node okay let's submit it okay so we have solved this question successfully now last let us look at the code of in order traversal okay so this is the question on in order traversal let's look at the code for it okay so uh this was the code which I needed to complete uh so I have taken one vector answer and call the in order traversal function pass the root node and the answer vector and here if I look if in order traversal means left sub tree root and right sub tree so if root is not null Traverse on the left sub tree then push back the value of the current rout and then Traverse on the right sub tree okay it will give us the in order traversal let me submit it okay so we have solved this question successfully okay so I hope you have understood all these three traversals completely thank you