Vertical Order Traversal in a Binary Tree

so before starting off this video i&#39;d love to thank reliable for sponsoring this entire three series we need experienced candidates how many times has this sentence shattered your dream to work in a good company or a job description which requires experience you won&#39;t ever have to listen to the sentence ever again if you use a platform like relevant by an academy he conducts a test which is completely based on skills and you need to perform in your chosen field reliable has around thousand plus job openings by 50 plus top indian companies and unicorn startups what you need to do is you just need to register for this test apply on the test and after that your interview will be scheduled and you will be hired and the best thing about this is the relevant tests are free and you can check out all the links in the description below hey everyone welcome back to the channel i hope you guys are doing extremely well so today we will be solving the problem vertical order traversal in a given binary tree so you must be understanding what is the problem by the name vertical order right so if i try to draw vertical lines in this particular binary tree this will be the first vertical line that will be drawn so i can say in the first vertical order we have 4 right right after that we will be having a line which will have 2 and 5 so the next vertical line should have 2 and 5 now if i draw the next line if i draw the next line i can say one is at first and ideally nine and ten are actually overlapping like i&#39;ve written them in the same structure but ideally they&#39;re overlapping so if uh it is overlapping just make sure that you write the smaller value at first after that the greater value okay and after that we have the value six now the next vertical we have three at the next vertical we have again 10. now there is something to observe the first thing was uh if notes are overlapping just make sure you take the smaller one if there are same nodes it doesn&#39;t matter like there can be similar value nodes in the binary tree what matters is you have to write the vertical order from left to right and while you write a single vertical order just write it from top to bottom right write right from top to bottom whenever you write it for a single vertical so you basically need to return a vector of vector for a list of list like this is this is what the first list contains the second vector contains the third list contains the fourth vector the first vector so the number of verticals like you have to return a vector of vector or a list of list which describes the vertical order traversal of a binary tree so in order to solve this problem can we actually uh consider this as one of the verticals this has another vertical this has another vertical this is another vertical this is another vertical like yes trevor we definitely can consider that now can i solve this problem uh using a couple of things one is we consider this like these linings as points on the x-axis like what i&#39;m saying is this is the zeroth line this is the minus one line as the minus two line this is the minus one sorry plus one line this is the plus two line like i can have for all verticals i can say these are the values of x perfect right now what if i i consider these guys as levels what if i say this guy is at the zeroth level all these guys are at the first level all these guys are at the second level all these guys are the third level and this guy is at the fourth level then then i can say this is at a vertical zero level zero this is at a vertical minus one level one this is at a vertical one level one this is at a vertical minus two and level two similarly these both of these guys are at vertical zero level two this guy is at level uh vertical one level two this guy is at vertical minus one level three and this guy is at vertical zero level four like i can definitely write this so if i can write this don&#39;t you think it becomes very simple what if i can have verticals so i can say i&#39;ll have a minus two vertical minus one vertical zero vertical one vertical and a two vertical correct now in this minus two vertical can i say the first element that i have is four so minus two vertical is done next i&#39;ll go to minus one vertical and i&#39;ll take it level wise so the first level guys two perfect the next level i have on this vertical is the guy at the level three that&#39;s five so i can say the vertical minus one is also done now when i come to vertical zero vertical zero has level zero that&#39;s one has level two that has nine and ten again i can use some data structure so that this is maintained in a sorted order next i can say i was six so the vertical zero is done so in this way can i get every vertical like if i have the x can i just i trade from the ascending orders of x and can i get the verticals so basically i i trade in the ascending order of x correct and for the level i i trade in the ascending order of level for f for every vertical i just need to iterate on the levels to get these guys these guys and these guys i think the job will be done so in short the question is very simple i need to traverse for every node and i need to assign the verticals and the levels to every node perfect so you can do that using any traversal so what i&#39;ll do is i&#39;ll do this using the level order traversal you can try this using in order pre-order post order whatever you feel like you can try that so what i&#39;ll do is i will initially take a q data structure okay and in the skew data structure i&#39;ll be basically storing the node the vertical and the level okay that is what i will be doing and along with that i&#39;ll be carrying a data structure of map which is having integer again for java people you can carry something like pre-map and on this vertical like assuming this guy to be vertical so on every vertical there will be multiple levels so for a level i&#39;ll again carry because for every level like as you see over here for level two there were multiple notes so for every level i will be having multiple notes so since i need if on a level there are multiple notes i need i need them in a sorted order so i can use something like a set but i&#39;ll be using a multi set now why will i be using a multiset that&#39;s that&#39;s a very good question the reason is because if you remember the question clearly stated i can have same values so please make sure you use multi-set because if you use set it will only store unique values this might happen this is 9 this also might be 9 like this can also be 9 okay so there can be repeated values so please make sure you store like this so map of integer this represents the verticals not each verticals i will be representing a level like multiple levels on every vertical on every level there might be multi nodes okay so this is what uh data structure you&#39;ll be using to store all the verticals and levels mugged okay and in java what you can use is something like a tree map of int comma again a tree map of int teacher instead of a multi set you can use something like priority queue in java okay or you can use a list and then sorted this can be anything this can be a priority queue this can be a list and after that you can sort it that is completely i&#39;ll leave that to you okay so initially while starting you have the cue just make sure node one vertical zero level zero is inserted into your q data structure so over here you&#39;re currently over here right now what you will do is whenever you start you start i treating by taking this first sky so whenever you take this that&#39;s basically node one the vertical zero and the level is zero so once you&#39;ve taken this just make sure you uh enter this into the data structure so you&#39;re saying at vertical 0 i have someone with level 0 and at level 0 i have this node 1 okay so that is what you have stored in your data structure now for node 1 just do a level order traversal simply take the left so the left guy is two now can i see the guy who is having a two if you&#39;re moving to the left the vertical will change by minus one because you&#39;re moving to the left and the level since you&#39;re moving left and down the level will be plus one so the level will become this so can i say the left node is two the vertical will go left that&#39;s minus one the right uh the down guy will be the level will increase by plus one so left is done what about right can i say in right you have a three yes i can say and can i say the vertical will increase by plus one if you move right it makes sense if you move right the vertical will increase by plus one and the level will also increase by plus one so make sure you enter that into the queue data structure once you have done this just make sure this is done and again go to the next iteration so in the next iteration get the next element of the queue okay so what you have is node 2 the vertical is minus one and you have a level as one so minus one will take a level one and a level one you have a node two perfect so just have this stored into your data structure right after that node 2 has a left node 2 has a right correct so if a node 2 has a left it will be 4 so you&#39;ll take 4 and can i say the vertical will change by minus 1 the vertical becomes -2 and after that can i say the level will also change by plus one so the level will become two so you got uh after two you got four right on the right can i say the vertical will change by plus one because you&#39;re moving right so the right node is 10 so you can insert that the next node that will be inserted into your q data structure will be 10 comma minus 1 plus 1 will be 0 and 1 plus 1 the level will be 2 so can i say 10 is at a level 0 so they had a vertical zero and a level two so can i say the node two is done i can indeed say hence i&#39;ll move to the next node so now when you come to the next traversal what you&#39;ll do is you&#39;ll take three comma one comma one so the node is three the vertical is one the level is one so at vertical one on that level one you will take the node three so in this way you can easily do it now can you say on three is left you have someone has nine so that will be nine and the vertical will change by minus one so it will become zero and the level will change by plus one that will become two so you again get this and on the right you have a ten so you can again insert n so just after this after this write ten comma the vertical will change by plus one two because you&#39;re going right and the level will change by plus one that is what you will easily get from this three so this three three is done so you can keep on nitrating from the queue the sole idea is if you&#39;re moving to the left the vertical will change by minus one the level will change by plus one and if you&#39;re moving right the vertical is going to change by plus one and the level is by plus one so every time you pop it out just make sure you put it into a into vertical after that onto its level and after that onto its multi set or priority queue like if you&#39;re doing c plus plus you can use a multiset and if you&#39;re using java you can use a priority queue because in java practice you stores the minimal element at the top right so that that is how you can definitely get something as a vertical order traversal so again i have i&#39;ve done using the level order traversal which uses a queue data structure you can do this using inorder the sole idea is very simple whenever you move left just vertical order and level and whenever you move right the vertical order and level you can use any traversal to move left and to move right doesn&#39;t matter so guys as usual the c plus plus code is on the left and the java code is on the right so what we have done is we have taken a root right initially and as i said in order to store the vertical orders we have taken a map of integer map of intent multi set over here in java as you can see we have taken a tree map of tree map of priority queue okay and after that we have taken a queue and in queue we were storing something as node comma the vertical and the level right so we have used pairs in c plus plus and in java we have used something as couple okay perfect so initially root comma zero comma zero has been pushed now you know that you have to do a level order traversal just keep on doing the level order traversal and what you will do is you will take the node right you will take the vertical order you will take the level and after that what you will do is at first just make sure you insert that into your data structure so first in vertical x of that in the level y just insert this guy because it&#39;s a multiset so you insert that right after that if there is a left you take that left and insert it into the queue by vertical minus 1 and level plus 1 if there is a right then you insert by vertical plus 1 and level plus 1 once this entire level order traversal has been completed just traverse across this map nodes okay now if you&#39;re traversing what is this p can i say this p is basically the entire thing inside this this becomes p dot first this becomes p dot second we suggest the map into comma multiset right so if i&#39;m saying p dot second what does that signify that basically signifies a map of int like levels it&#39;s level and multi-set on that right so p dot second will traverse that and you have taken an answer right so what you&#39;re doing is you&#39;re taking a column and in that column like in that level right in that how many whatever levels are there just make sure at every level you&#39;re inserting right at the end like column.pushback or column.insert whatever you want to do you&#39;re inserting the entire multiset like let&#39;s assume for a vertical traversal zero we had level zero we had level one so first we traveled for zero got the multi set inserted into the column next level once multiset we got inserted here next level to multiset we got we inserted here that is what we have done once we have got this entire level like entire vertical uh order entire vertical we will insert that vertical into the answer simple as that again you can just do a try and by yourself if your data structure is strong you&#39;ll get it so let&#39;s explain the java code okay so in the java code what we have done is we have taken a tuple okay root zero zero a similar thing we have done we have i treated uh doing a level order traversal so we have the vertical we have the level okay and right after that we have checked if if it exists if it doesn&#39;t exist we are creating a tree map okay and if the priority queue doesn&#39;t exist we are again creating a priority queue very simple if for a vertical uh a tree map doesn&#39;t exist we are creating the stream up and a foreign level the practical doesn&#39;t exist we are creating that practicum and right after that we are getting the getting the vertical getting the tree map off level and then on that practice u we are inserting node dot fact okay vertical then level and onto the practical inserting that after that it&#39;s simple if not dot left doesn&#39;t uh exist sorry it does exist we&#39;ll go left and vertical minus one level plus one and on right vertical plus one level plus one this will make sure it inserts and this while loop will be entire level order traversal once you have done this we will take a list of list integers because for every vertical i need a list that has to be returned so what i&#39;ll do is i&#39;ll iterate on the map dot value so for every vertical i&#39;ll iterate okay because map dot value means for every vertical first for vertical minus 2 minus 1 0 1 2 for every vertical i will iterate and over here i might i&#39;m just adding an empty list for every vertical empty list and on that list what i&#39;m doing is i&#39;m i trading in the priority queue and i&#39;m taking the values and adding to the end of the list okay so once this while loop is over i can say this vertical is over next again this one will go this this and then i can return the list again just go through the code by yourself once you will understand the code completely and i will give you a task just make sure you do this question by in order or a pre-order and paste that code and paste the code in the comment section okay that is your homework for this do it using in order or post order and paste it in the comment section what&#39;s the time complexity guys the time complexity will definitely be becau of n because you&#39;re traversing generally and i can say that since you&#39;re using a multi set you can add a login concept over here and since you&#39;re using practical you can use a login and the space complexity is you&#39;re using every vertical and everything so that&#39;s a big of n because for every vertical you&#39;re creating a level and you&#39;re storing all the notes so ultimately you&#39;re storing all the notes so i can summarize the space complexity to be big of n plus b of n for the q data structure that you&#39;re using again thrice of n is somewhere that is what using root and two other variables but yeah i can just write it as big o of n is the space complexity like if i summarize it and i can say n log n to be the time complexity that i am taking in order to do the vertical order traversal because of the multiset or the priority queue that they are using so i hope you&#39;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&#39;re new to the channel please do consider subscribing because i&#39;m going to bring in such more series in the upcoming future as well with this uh let&#39;s wrap up this video let&#39;s speed in the next lecture bye bye [Music]

so before starting off this video i&amp;#39;d love to thank reliable for sponsoring this entire three series we need experienced candidates how many times has this sentence shattered your dream to work in a good company or a job description which requires experience you won&amp;#39;t ever have to listen to the sentence ever again if you use a platform like relevant by an academy he conducts a test which is completely based on skills and you need to perform in your chosen field reliable has around thousand plus job openings by 50 plus top indian companies and unicorn startups what you need to do is you just need to register for this test apply on the test and after that your interview will be scheduled and you will be hired and the best thing about this is the relevant tests are free and you can check out all the links in the description below hey everyone welcome back to the channel i hope you guys are doing extremely well so today we will be solving the problem vertical order traversal in a given binary tree so you must be understanding what is the problem by the name vertical order right so if i try to draw vertical lines in this particular binary tree this will be the first vertical line that will be drawn so i can say in the first vertical order we have 4 right right after that we will be having a line which will have 2 and 5 so the next vertical line should have 2 and 5 now if i draw the next line if i draw the next line i can say one is at first and ideally nine and ten are actually overlapping like i&amp;#39;ve written them in the same structure but ideally they&amp;#39;re overlapping so if uh it is overlapping just make sure that you write the smaller value at first after that the greater value okay and after that we have the value six now the next vertical we have three at the next vertical we have again 10. now there is something to observe the first thing was uh if notes are overlapping just make sure you take the smaller one if there are same nodes it doesn&amp;#39;t matter like there can be similar value nodes in the binary tree what matters is you have to write the vertical order from left to right and while you write a single vertical order just write it from top to bottom right write right from top to bottom whenever you write it for a single vertical so you basically need to return a vector of vector for a list of list like this is this is what the first list contains the second vector contains the third list contains the fourth vector the first vector so the number of verticals like you have to return a vector of vector or a list of list which describes the vertical order traversal of a binary tree so in order to solve this problem can we actually uh consider this as one of the verticals this has another vertical this has another vertical this is another vertical this is another vertical like yes trevor we definitely can consider that now can i solve this problem uh using a couple of things one is we consider this like these linings as points on the x-axis like what i&amp;#39;m saying is this is the zeroth line this is the minus one line as the minus two line this is the minus one sorry plus one line this is the plus two line like i can have for all verticals i can say these are the values of x perfect right now what if i i consider these guys as levels what if i say this guy is at the zeroth level all these guys are at the first level all these guys are at the second level all these guys are the third level and this guy is at the fourth level then then i can say this is at a vertical zero level zero this is at a vertical minus one level one this is at a vertical one level one this is at a vertical minus two and level two similarly these both of these guys are at vertical zero level two this guy is at level uh vertical one level two this guy is at vertical minus one level three and this guy is at vertical zero level four like i can definitely write this so if i can write this don&amp;#39;t you think it becomes very simple what if i can have verticals so i can say i&amp;#39;ll have a minus two vertical minus one vertical zero vertical one vertical and a two vertical correct now in this minus two vertical can i say the first element that i have is four so minus two vertical is done next i&amp;#39;ll go to minus one vertical and i&amp;#39;ll take it level wise so the first level guys two perfect the next level i have on this vertical is the guy at the level three that&amp;#39;s five so i can say the vertical minus one is also done now when i come to vertical zero vertical zero has level zero that&amp;#39;s one has level two that has nine and ten again i can use some data structure so that this is maintained in a sorted order next i can say i was six so the vertical zero is done so in this way can i get every vertical like if i have the x can i just i trade from the ascending orders of x and can i get the verticals so basically i i trade in the ascending order of x correct and for the level i i trade in the ascending order of level for f for every vertical i just need to iterate on the levels to get these guys these guys and these guys i think the job will be done so in short the question is very simple i need to traverse for every node and i need to assign the verticals and the levels to every node perfect so you can do that using any traversal so what i&amp;#39;ll do is i&amp;#39;ll do this using the level order traversal you can try this using in order pre-order post order whatever you feel like you can try that so what i&amp;#39;ll do is i will initially take a q data structure okay and in the skew data structure i&amp;#39;ll be basically storing the node the vertical and the level okay that is what i will be doing and along with that i&amp;#39;ll be carrying a data structure of map which is having integer again for java people you can carry something like pre-map and on this vertical like assuming this guy to be vertical so on every vertical there will be multiple levels so for a level i&amp;#39;ll again carry because for every level like as you see over here for level two there were multiple notes so for every level i will be having multiple notes so since i need if on a level there are multiple notes i need i need them in a sorted order so i can use something like a set but i&amp;#39;ll be using a multi set now why will i be using a multiset that&amp;#39;s that&amp;#39;s a very good question the reason is because if you remember the question clearly stated i can have same values so please make sure you use multi-set because if you use set it will only store unique values this might happen this is 9 this also might be 9 like this can also be 9 okay so there can be repeated values so please make sure you store like this so map of integer this represents the verticals not each verticals i will be representing a level like multiple levels on every vertical on every level there might be multi nodes okay so this is what uh data structure you&amp;#39;ll be using to store all the verticals and levels mugged okay and in java what you can use is something like a tree map of int comma again a tree map of int teacher instead of a multi set you can use something like priority queue in java okay or you can use a list and then sorted this can be anything this can be a priority queue this can be a list and after that you can sort it that is completely i&amp;#39;ll leave that to you okay so initially while starting you have the cue just make sure node one vertical zero level zero is inserted into your q data structure so over here you&amp;#39;re currently over here right now what you will do is whenever you start you start i treating by taking this first sky so whenever you take this that&amp;#39;s basically node one the vertical zero and the level is zero so once you&amp;#39;ve taken this just make sure you uh enter this into the data structure so you&amp;#39;re saying at vertical 0 i have someone with level 0 and at level 0 i have this node 1 okay so that is what you have stored in your data structure now for node 1 just do a level order traversal simply take the left so the left guy is two now can i see the guy who is having a two if you&amp;#39;re moving to the left the vertical will change by minus one because you&amp;#39;re moving to the left and the level since you&amp;#39;re moving left and down the level will be plus one so the level will become this so can i say the left node is two the vertical will go left that&amp;#39;s minus one the right uh the down guy will be the level will increase by plus one so left is done what about right can i say in right you have a three yes i can say and can i say the vertical will increase by plus one if you move right it makes sense if you move right the vertical will increase by plus one and the level will also increase by plus one so make sure you enter that into the queue data structure once you have done this just make sure this is done and again go to the next iteration so in the next iteration get the next element of the queue okay so what you have is node 2 the vertical is minus one and you have a level as one so minus one will take a level one and a level one you have a node two perfect so just have this stored into your data structure right after that node 2 has a left node 2 has a right correct so if a node 2 has a left it will be 4 so you&amp;#39;ll take 4 and can i say the vertical will change by minus 1 the vertical becomes -2 and after that can i say the level will also change by plus one so the level will become two so you got uh after two you got four right on the right can i say the vertical will change by plus one because you&amp;#39;re moving right so the right node is 10 so you can insert that the next node that will be inserted into your q data structure will be 10 comma minus 1 plus 1 will be 0 and 1 plus 1 the level will be 2 so can i say 10 is at a level 0 so they had a vertical zero and a level two so can i say the node two is done i can indeed say hence i&amp;#39;ll move to the next node so now when you come to the next traversal what you&amp;#39;ll do is you&amp;#39;ll take three comma one comma one so the node is three the vertical is one the level is one so at vertical one on that level one you will take the node three so in this way you can easily do it now can you say on three is left you have someone has nine so that will be nine and the vertical will change by minus one so it will become zero and the level will change by plus one that will become two so you again get this and on the right you have a ten so you can again insert n so just after this after this write ten comma the vertical will change by plus one two because you&amp;#39;re going right and the level will change by plus one that is what you will easily get from this three so this three three is done so you can keep on nitrating from the queue the sole idea is if you&amp;#39;re moving to the left the vertical will change by minus one the level will change by plus one and if you&amp;#39;re moving right the vertical is going to change by plus one and the level is by plus one so every time you pop it out just make sure you put it into a into vertical after that onto its level and after that onto its multi set or priority queue like if you&amp;#39;re doing c plus plus you can use a multiset and if you&amp;#39;re using java you can use a priority queue because in java practice you stores the minimal element at the top right so that that is how you can definitely get something as a vertical order traversal so again i have i&amp;#39;ve done using the level order traversal which uses a queue data structure you can do this using inorder the sole idea is very simple whenever you move left just vertical order and level and whenever you move right the vertical order and level you can use any traversal to move left and to move right doesn&amp;#39;t matter so guys as usual the c plus plus code is on the left and the java code is on the right so what we have done is we have taken a root right initially and as i said in order to store the vertical orders we have taken a map of integer map of intent multi set over here in java as you can see we have taken a tree map of tree map of priority queue okay and after that we have taken a queue and in queue we were storing something as node comma the vertical and the level right so we have used pairs in c plus plus and in java we have used something as couple okay perfect so initially root comma zero comma zero has been pushed now you know that you have to do a level order traversal just keep on doing the level order traversal and what you will do is you will take the node right you will take the vertical order you will take the level and after that what you will do is at first just make sure you insert that into your data structure so first in vertical x of that in the level y just insert this guy because it&amp;#39;s a multiset so you insert that right after that if there is a left you take that left and insert it into the queue by vertical minus 1 and level plus 1 if there is a right then you insert by vertical plus 1 and level plus 1 once this entire level order traversal has been completed just traverse across this map nodes okay now if you&amp;#39;re traversing what is this p can i say this p is basically the entire thing inside this this becomes p dot first this becomes p dot second we suggest the map into comma multiset right so if i&amp;#39;m saying p dot second what does that signify that basically signifies a map of int like levels it&amp;#39;s level and multi-set on that right so p dot second will traverse that and you have taken an answer right so what you&amp;#39;re doing is you&amp;#39;re taking a column and in that column like in that level right in that how many whatever levels are there just make sure at every level you&amp;#39;re inserting right at the end like column.pushback or column.insert whatever you want to do you&amp;#39;re inserting the entire multiset like let&amp;#39;s assume for a vertical traversal zero we had level zero we had level one so first we traveled for zero got the multi set inserted into the column next level once multiset we got inserted here next level to multiset we got we inserted here that is what we have done once we have got this entire level like entire vertical uh order entire vertical we will insert that vertical into the answer simple as that again you can just do a try and by yourself if your data structure is strong you&amp;#39;ll get it so let&amp;#39;s explain the java code okay so in the java code what we have done is we have taken a tuple okay root zero zero a similar thing we have done we have i treated uh doing a level order traversal so we have the vertical we have the level okay and right after that we have checked if if it exists if it doesn&amp;#39;t exist we are creating a tree map okay and if the priority queue doesn&amp;#39;t exist we are again creating a priority queue very simple if for a vertical uh a tree map doesn&amp;#39;t exist we are creating the stream up and a foreign level the practical doesn&amp;#39;t exist we are creating that practicum and right after that we are getting the getting the vertical getting the tree map off level and then on that practice u we are inserting node dot fact okay vertical then level and onto the practical inserting that after that it&amp;#39;s simple if not dot left doesn&amp;#39;t uh exist sorry it does exist we&amp;#39;ll go left and vertical minus one level plus one and on right vertical plus one level plus one this will make sure it inserts and this while loop will be entire level order traversal once you have done this we will take a list of list integers because for every vertical i need a list that has to be returned so what i&amp;#39;ll do is i&amp;#39;ll iterate on the map dot value so for every vertical i&amp;#39;ll iterate okay because map dot value means for every vertical first for vertical minus 2 minus 1 0 1 2 for every vertical i will iterate and over here i might i&amp;#39;m just adding an empty list for every vertical empty list and on that list what i&amp;#39;m doing is i&amp;#39;m i trading in the priority queue and i&amp;#39;m taking the values and adding to the end of the list okay so once this while loop is over i can say this vertical is over next again this one will go this this and then i can return the list again just go through the code by yourself once you will understand the code completely and i will give you a task just make sure you do this question by in order or a pre-order and paste that code and paste the code in the comment section okay that is your homework for this do it using in order or post order and paste it in the comment section what&amp;#39;s the time complexity guys the time complexity will definitely be becau of n because you&amp;#39;re traversing generally and i can say that since you&amp;#39;re using a multi set you can add a login concept over here and since you&amp;#39;re using practical you can use a login and the space complexity is you&amp;#39;re using every vertical and everything so that&amp;#39;s a big of n because for every vertical you&amp;#39;re creating a level and you&amp;#39;re storing all the notes so ultimately you&amp;#39;re storing all the notes so i can summarize the space complexity to be big of n plus b of n for the q data structure that you&amp;#39;re using again thrice of n is somewhere that is what using root and two other variables but yeah i can just write it as big o of n is the space complexity like if i summarize it and i can say n log n to be the time complexity that i am taking in order to do the vertical order traversal because of the multiset or the priority queue that they are using so i hope you&amp;#39;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&amp;#39;re new to the channel please do consider subscribing because i&amp;#39;m going to bring in such more series in the upcoming future as well with this uh let&amp;#39;s wrap up this video let&amp;#39;s speed in the next lecture bye bye [Music]

Transcript for:Vertical Order Traversal in a Binary Tree

Transcript for:
Vertical Order Traversal in a Binary Tree