everyone welcome back to the channel i hope you guys are doing extremely well so today we will be discussing the boundary traversal of binary tree from the free country series so basically you'll be given a binary tree okay and you have to print the boundary traversal so as of now we will be solving the anti-clockwise boundary traversal if you understand the anti-clockwise you can definitely do the clockwise by yourself so basically if i take the boundary traversal first you'll start from one right then anti-clockwise so you go to two then you go to three then you go to four that's boundary right then you go to five again boundary then you go to 6 then you go to 10 then you go to 11 then you go to 9 then you go to 8 then you go to 7 so basically anti-clockwise right anti-clockwise so i want the anti-clockwise boundary traversal of any given binary tree so how do you solve such a question it's very simple first we're going to take the left boundary since it's an anti-clockwise left boundary uh excluding leaves i can say excluding the leaf notes that's what i'm gonna initially uh take after that i'm gonna take the leaf notes and after that i'm going to take the right boundary in the reverse direction right and if i follow this method i think i will get my boundary traversal first i'll get the left then i'll get the leaf then i'll get the right in the reverse in the reverse very very very important the right boundary should be in the reverse and also it should exclude the leaf notes so let's first discuss how do you get the left boundary excluding leaf nodes so in order to get the boundary traversal we definitely have to take a data structure which stores uh the boundary traversal so the first thing that you will always do is you will take the root of the tree and you'll put it because that's that's a part of the left boundary as well as the right boundary so in order to avoid any confusion please make sure you put the whatever is the root of the tree into the data structure right after that you'll start off with the left boundary now how do you start off with the left boundary again very simple you start from the roots left so you take on 2 you put that into your data structure then if there exists a left you will go so you'll put it on and if there exists a left of 3 it doesn't exist so if there doesn't exist a left you'll go to the right very very important if there doesn't exist the left you'll go to the right so you'll go to the right and you'll get four next does there exist a left of four yes five but the moment you see that it's a leaf node we see that it's a leaf node right five is a leaf node because it doesn't have a left neither uh does it have a right so it's a leaf node and i want the traversal excluding leaf the left boundary excluding leaf so can i say i have actually gathered my left boundary excluding leaf so the left boundary traversal has been completed that's time for the leaf nodes so in order to get the leaf nodes we have to do a in order traversal yes you cannot do a level order traversal because i want the leaf notes from the bottom right i want from left to right so if you do a level order it might happen let's say the leaf notes are finishing some level above like before this there is a level where the leaf nodes are finishing so these guys will come up first if you are doing a level order traversal that's why it's better you do in order traversal which is which is basically root and then it goes to the left and then it goes to the right okay so what it will do is whenever you do a in order traversal first you'll get 5 then you'll get 6 then you'll get 10 and then you will get 11. in this order you will get all the leaf notes if you do an in order traversal basically travels for all the notes in the tree and check which notes are your leaf notes and whichever are your leaf nodes just add them into your data structure so we are done with that right now it's time for the right boundary on the reverse excluding the leaf so let's do that so for the right boundary what you'll do is you will start from roots right so this is where you start off and since we want in the anti-clockwise you want this in a reverse direction so you can use a vector or a stack or whatever you want to use and you're getting seven right next go to the right you're getting eight next does there exist right no so if there doesn't exist a right very very important if there doesn't exist right you'll go to the left so that's nine next does there exist a right yes but this one is your leaf node and it was clearly mentioned that i have to exclude the leaf so we will stop because it's a leaf node we have reached the end so we'll stop our trap right boundary traversal over here now this is my stack or vector like you can take a stack you can take a vector whatever you wanna take you can take it so this we have taken right now take from the like from the last first you'll take nine then you will take eight take from the last okay then you will take seven so what it will make sure is this is the entire boundary traversal and make sure that you took nine eight seven so it's already in the opposite direction right already in the reverse direction so i can say that i have taken the right boundary in the reverse direction hence i have completed all my three steps so if i summarize these three steps i can say love i can say left boundary means left left left and if there doesn't exist left then you'll go right leaf node means normal inorder traversal and checking of node whichever is the leaf node you just add it right boundary means right right right and whenever there is not a right you move left and you exclude the leaf like whichever is the leaf node you just do not take it and initially you always take the root note that's what the algorithm is in order to figure out the boundary traversal of any given binary tree so let's check out the code so as usual this is the c plus plus code and this is the java code again pretty much identical so you can definitely follow the c plus plus and you can just have an eye on the java code just if you feel like so initially we declare a vector the data structure which is going to store the entire boundary traversal so i first check if if just in case the root is empty okay then we're gonna just uh return an empty data structure like if we're not given a binary we return an empty data structure after that if the root node is not a leaf then we're to add that into our data structure and after that the three steps left leaves right as we did and we return our answer right so we will check the left leaves and right so let's check the left boundary so as i said left means left left left left left left left and if there is no left then you move to the right so initially i start with roots left and if it's not a leaf node then only we will add that into our left boundary excluding leaf right or else i'll move to the left and if there doesn't exist a left then i'll move to the right super simple left boundary right boundary is the exact opposite we start off with the right right and it's not a leaf we will add it and we will move to right right right right right and if it is not a right then i'll take the left simple and this time we'll store this into some data structure temp and right after this we will take the reverse yes we'll take the reverse so right boundary is also done right after that we have add leaves as i said it's a simple in order traversal that's left right and whenever you're coming to the root if it's a leaf node please add that into your data structure correct so there are three steps i can say the left boundary at max will take height of the tree the right boundary will take height of the tree and the normal traversal will take we go off and so if i just uh summarize that i can say it's a big o of n like if i just take it off and and the auxiliary space used is we go off and i'm not considering the space used in uh this rest because generally when we return answers we do not consider that we i'm just talking about our algorithmic complexity not about uh storing answers and all that this is this time complexity and space complexity linear in nature so i hope you've understood the entire explanation as well as the code just in case you did please please please make sure you like this video because it took a lot of efforts to make this entire tree series also if you wish you can definitely drop in a comment that will keep motivating me to make such further series also if you're new to the channel please do consider subscribing because i'm going to bring in such more series in the upcoming future as well with this uh let's wrap up this video let's speed in the next lecture bye [Music]