Tree Views & Traversals: Zig-Zag, Boundary, Top, Bottom, Left & Right View Problems

Hello ji how are you all, This is love babbar and welcome to the channel codehelp We have reached to our lecture number 64

And here we are going to solve many questions on tree Tree videos are live, in last two videos we have seen what are trees What are the basic terms learnt the implementation

Some famous questions on tree like, height diameter balance tree identical tree sum tree and more we have solved In this video we are going to solve many more good questions And our focus in this video is we solve questions on traverse of trees and different types on views on trees

Like exact traversal , boundary traversal diagonal traversal vertical order traversal top view ,right view, bottom view left view This view type questions like top view, bottom view, left view these are very easy But these questions are frequently asked in interviews

Some time out of pressure many people could not answer them, you can confirm this with your seniors This questions are asked frequently , so you should focus on them Once you do focus carefully you can perform good in your interviews

And then your selection will be confirmed So starting with our first question Name of the first question is zig zag traversal

That means like , if we have a tree and these are the nodes Now these are linked Data are 1 2 3 4 5 6 7 8

So zig zag traversal means I will print first from left to right order so I will print 1 Then we will print in right to left order we print 4 and then 2

Again going left to right order we get 3 5 6 Again in right to left order then i get 8 and then 7 So i got answer as 1 4 2 3 5 6 8 7

When I talk about zig zag traversal or we can call it as spiral traversal Then it means that once we go left to right for one level Then in another level we go right to left

then for another one we go left to right and then right to left for another one Once left to right and once right to left and we repeat it again and again This we call as zig zag traversal

Now talking about approach, it should be like we own made it, we will think in that way We will talk about approach later now lets give shoutout to our sponsors This video is sponsored by Relevel

Relevel is basically a hiring platform which helps you to crack in you dream jobs You do not need any degree, expertise or diploma You can give Relevel test and by it you can grab your dream jobs

The best thing is you do not need to pay any money for this all of this is free of cost Also currently swiggy is hiring through this platform you can check the openings here What are the profiles and the ctcs

The only thing you have to score 70 % to qualify And once you achieve that you will be eligible for 100+ startups which can directly hire you Qualifying the test is very easy as relevel provides all study material sample tests you can practice from there

Once you qualify the test, then relevel will showcase your profile to all the companies So you probability of getting selected becomes high A lot of you given the test but you have not reattempted that again you should try

It is very good for your practice, and you are bound to get a job once you clear the test Relevel is conducting tests in 9 categories which are visible here Some new categories got added like operation associate test, HR generalist test, associate product management test

Which provides salary around 25 LPA and one more new category is added that is android development test Relevel has provided 10 crore + jobs till now to the candidates Talking about packages, you can grab around 40 LPA

Some examples of achievers are showing here And one more thing if are in monthly leaderboard then you can win exiting prizes like iphone, apple watches So you can book a slot for your test , weekend slots are open book now and attempt the test in the weekend thankyou

Now discuss about approach , we know about recursive as well as iterative way to traversal Inside recursive we have seen inorder, preorder and post order and it have iterative method also In iterative way we have seen level order traversal

We are processing this level by level So I want to go with level order traversal any try the solution with it once Now I draw a tree quickly

And give data in nodes like 1 2 3 4 5 and it goes zig zag like First I will go left to right we get answer as 1 Then go right to left we get 3 and 2

Then we go left to right that means we get 4 and 5 So my answer should be this you get that So I tell how we can solve this

We will have a queue in the starting inside this we will have a particular level of data In starting it have data of level 0 and it only have the root node that having 1 So inside queue 1 will be there in form of left to right

One flag will be there, basically one boolean variable will be there whose name will be lefttoright Which will tell that current answer came by which moment IF it is by left to right then that value will be true and if it comes false then it is by right to left

When I pop from here then I will insert its child 2 and 3 First I will check first lefttoright will be true then when we insert its child it will insert in right to left way That means 3 and then 2 then it stored 3 and then 2

Now lefttoright becomes false so when I go to the next level I go with right to left So answer will be 4 and 5 So basically what data I going to pop going to store as answer

First there will be 1 then 3 2 4 5 compare it answer got matched Now carefully listen how we are going to cde Now we want a vector int and return type of this is answer

If your root is null then simply return ans Now I created quickly a queue of node * type , we have seen level order traversal previously We said first push root in queue

While q is not empty, you have to process each level Now inside a level, many elements could be there, how many lets find Int size = q.size , this is how you get the size

Then I say look at first we stored 1 then 3 ,2 and then 4, 5 Lets take a array temporary ans, I take ans wer of vector int You can take array or vector anything

Now we have to process the level So I will run a loop for (int i =0 ;i<size ;i++) what I am doing in it lets understand carefully I say first take the front node, take node* front node = q.front ()

And pop q.front , alright we did this first Now I say the temporary array I made, data will enter in it in to ways from queue First left to write or right to left

So I will create a flag, so I write bool lefttoright and give it true Now depending on this flag it will be decided that I will insert elements on normal flow or reverse order So now I will take index according to lefttoright

If lefttoright is true then go with normal flow and if false go wiht reverse order Size -i-1 and insert value in ans, ans[index]=frontnode -->data Now you have to consider left and right child if front node left is not null then push it in queue, q.push(front node__. left)

And you have to do same in for the right , you got that When you come out of the loop you do ans.push , basicall you created result there Lets change it to result

So what we store in result , for (auto i; ans) And you inserted all in result ,reslt.push_back(ans); And you return result here ,ok

Lets compile and run and check if any syntax error is there or not Ok there is a mistake we should write i there Again some silly mistake are there now also, ok check from there

Ok a small mistake we did is that, we said first go left to right but you have to change alternatively also First you went left to right so later you have to go right to left So after processing each level you have change the direction

How direction get changed, you have to change lefttoright If it is true then change it to false and if it is false then make it true Basically you want to interchange it, ok we have changed the direction

Once again we are going to check, if error is there or not , it is not good if error will come again and again Checking it quickly , created the vector if it is null then return result , created q pushed root in it Initialize left to right until q is not empty take size, take ans

Run for loop for this level taken front node pop it for this level Commenting here normal insert or reverse insert which you get from this index Ok here is another mistake, you have to size the answer first before indexing it , so you did this

Lets run it, and we got the output ok then submit it Ok then pass all the test cases if it is running, wow 520 test cases have passed So this way we completed the solution now we can do code of zig zag traversal

Lets do it again, we create a queue and inserted root in it We say at starting go left to right so we inserted 1 and 1 got stored here Then we create a temporary array, in which we store the answer

Why to create temporary array can we do without it ? I said I have to decide that the element we inserting here that will be in which order normal order or in reverse order So we store that in a temporary array and that I will store in the main answer array later

So for that decided the flow normal or reverse and stored it in temporary array And basically you are inserting your left and right child So you did these for a particular thing so now you have to change your direction

And then you passed the data in result which is stored in temporary array This way you completed this question If you look carefully what is the time complexity of this question

So every node i visited single time so it will be O(n) For space complexity, I have created queue If you complete tree is like this, so when go very below like this

So the count of the nodes will be very high so we assume it as O(n) So our space complexity will come O(n) So we have submitted the code under this constrains and all tests got passed also

So this way you solved a question named zig zag traversal Now lets go to another question, second question naming boundary traversal This question says you have nodes like this

This is your root node, put data in that 1 2 3 4 5 6 7 8 9 10 11 So the meaning of boundary traversal is that, you have to print the node like First I will print this node and then say go ahead and print that and again going ahead print that

Go ahead and print that and again going ahead and print that And again going ahead and print that, again going ahead and print that Then here and print that print that and again print that and returned there

So you got answer as 1 2 3 6 8 10 11 9 7 4 this is you boundary traversal Talking about approach in this question here, i am telling what coming in my mind first What my algo is saying is that we can solve it in 3 parts

First we print first the left part, there is a small catch in here First I will print the left part but I will not print the left node As I will print the all the leaf nodes in the second part

That is why I am saying not tot print the leaf node in the left part so I can consider it in second part So what we got is the first thing we have to do is We have to print the left part excluding leaf node

Logic says when leaf node comes you stop for left part So in short I am going to print these part only The function of left part will print this only

Second function will print the leaf nodes means those who have no child So it started from here and went there and there So in short the leaf node function printing in this way in left to right direction

First 3 then 6 then 8 then 10 then 11 ,very nice Two parts are over now third part in which we will print the right part In this also there is a small catch, leaf node is already printed

So when we print the right node it will be excluding leaf node That means when leaf node comes it should stop but there is also a catch Here yo have come in this direction, and here also you went in left t right direction

But here in case of right part you have go in reverse order Normally if you print the right part you will come in this way First you print 4 then 7 then 9 but in actual case

First you have print 9 then 7 and then 4 In short you will print in this direction and the bottom function will print this part You have to keep in mind that you have to print it in reverse direction

So there are many conditions but we will solve this easily as we have broke it in 3 different parts Lets code it quickly nothing is there first we print left part then leaf part then the right part Now how we can print the left part, lets say you have a tree like this

IN this case lets say you started from root I say root will be printed in every case so lets print it Then this is your left side of tree and in this I have to print the left side

So I am here now and printed this as it is the root node Then I will go to the left side and print that and again I will go to left again But this is leaf node so I will return from there and then return from there and back to root node

So what we understand is, print root first and then go to left Lets say there is no left part here, so basically if I start from here And come to left print it then try to go to left but as there is no left

I will go to its right if right is there then print it then go to left nothing is there then return Check the right nothing is there then return then return back to root In short we have done the algo like, print the root first

If left exists then call for left else call for right, got it So this way you printed the left part Now talk about how you can print the leaf part, we will discuss it later first we write the function of left part

Writing the left function is important So I write a function whose name will be void traverseleft In this you pass a root and you passed a answer by reference

Basically I want to track the answer that is why passing it by reference I say if root == NULL Then return answer in this case

Now print the data of the root, but we do not to print it We want to insert in answer, so we write ans.push_back(root->data),first you did this Now what we have to do is, print the left part

So I write traverseleft and passed left of root , ans Firstly we check the base case, If your root is null then return, first case is that Then if leaf nade is there then stop, if (root-->left == NULL && root-->right == NULL ) then it is a leaf node

If it is a leaf node then we do not want to store nor want to print then return Then we have return in this and in this also so we can do it by or condition This you have created the base case,

Now according to my algorithm, first print if left is there go to left, if right is there go to right We have to store not print, so store it ans.push_back (root->data) If root left is non null then call it

Call it on left of null Else call on right of the node Done, traverse left part is completed

Next what I have to do is the leaf node part If this my tree Then I printed the root in the first line that is line number 126

Now the left view of this part this got printed and this also Then comes the leaf node so it stopped So I have to print the leaf nodes now, this is easy

In inorder traversal you are moving left to right, the code is LNR L means you approach the left and then you approach right I tat we go in that direction you have seen it previously

So going to write it quickly lets write a function traverse leaf in which we pass root and passed the ans by reference Now in base case we write, if it is a leaf node then store it

If root is null then return If it is a leaf node, if(root-->left == NULL && root-->right == NULL ) Then I push back the data of root and return from there

Now move in left and move in right, simple logic like we do in inorder Here basically you first move the left part And then you went to the right part, so second function is also done

Now we say traverse leaf node Now where will be the leaf nodes, one will be in left subtree and another will be in right subtree Now we traverse for left subtree, I say traverseleaf (root-->left) print all leaf nodes, alright this part is done

Next traverse leaf in the right side and print all the leaf nodes Next part is to traverse the right part we look it carefully So we create a function void traverseRight

And passed node* root,vector int &ans Now in base case If your root is null then return, another case will be

Lets say you are on the leaf node if(root-->left== NULL && root -->right== NULL ) then you have to return I discuss it previously So I can merge them and make a condition like this then we can copy paste it Now I say how we can go for the right part lets understand

If this is your tree Now basically we are here now we have to print the right view This part got printed in first function and this got printed in the leaf function

Now only i have to print this part means this node Currently I am here now , and I called function for right of root So i will start from here, so I am here I will go to right

Again go to right, reached at leaf node so return As you have returned then print it, this is very important that if you have returned then print it Again you returned then print again then you returned to root node

So this logic is very important that as you have so print Lets say that this part does not exist, then what happens lets see Then you will do like this, you called for right of root then you go to right

There is nothing there so you returned If right is not there go to left, went to left Now go to its right that is leaf node then return so print the above one

Now return from there so print it So we are getting the logic as if right exists of root Then simply go to right

Else if right does not exists then go to left If you have returned then print the answer pushback data of root, done the function is also done easily

traverse root of right, ans and you retun the ans I say do it do not know any syntax error will come it not It is saying call for root left is not not matching somewhere lets check lets check it quickly

There should be ans so quickly compile and run it it says correctly write the code do not write it in dizziness, I say I am shooting in night Some time it got mistaken you can forgive me sometime

Now it should run, logical mistake should not be there this are sill mistakes we can correct it Now it is saying some spelling mistake is there in line number 155 ok quickly correct it and I will run it and submit it Lets check it again, as wrong answer comes it will be little bit embarrassing

I didn't have done logical mistake just for spelling mistakes Here we have catched a mistake correcting it Now lets run it, now also there is some small issue

It says you did something wrong in 170, you didn't written the name correctly we did it right previously So 123 we say submit, it says ok then passed your all test cases, ok got it This way we have done the second question also

Now move on to our third question, who have pasted sticker on my pyjama what is going on in this country Third question which says vertical traversal of binary tree Which I am thinking is the most complicated one rest all are easy

Third question, vertical order traversal Ok lets start then, lets say my tree is like this I say there is 1 2 3 4 5 6 7 8 9

I say to do vertical order traversal So you draw vertical lines then on each and you can get the logic what I want to say So in short If I see so what we get as answer

first 4 will come then 2 then 1 and 5 and 6 then 3 and 8 then in this line 7 then 9 So basically going with vertical lines so first 4 comes then 2 come then 1 5 and 6 as 6 will come at the same level below 5 Now in the next line 3 and 8 in this line 7 and this line we get 9

So you get the answer as 4 2 1 5 6 3 8 7 9, this traversal is called as vertical order traversal You can check the question here, 5 and 6 are overlapping So in this case as we go left to right and we store it 5 and then 6

Different questions have different questions, in this questions They should be printed as they appear in level order traversal of tree so this type you have to this question So there is a nice way to solve this question

like there is a number line, we are talking about approach So there is a number line and lets say I assume the first one as 0 Then back one will be -1 and it keeps on decreasing and in another way in keeps on increasing like 1 and then 2

So I can say this as a type of horizontal distance this is x axis So I can say this node 1 and node 2 what is the distance between them that is 1 Now I want to show where is 1 indicating on the number line at 0

And 2 is at -1 4 is at -2 5 at 0 6 at 0 3 at 1 8 at 1 7 at 2 9 at 3 So I get the horizontal distance from root

So what we do with this horizontal distance, is that what i am getting the output is dependent on which thing? You should think of that, if I do level order traversal then first my answer will come this This answer is coming for 0 that means for 0 we will get answer as 1

Then for -1 the answer is coming 2 and for 1 we get 3 Then I go to this level for -2 the answer is coming 4 for 0 the answer is coming 5 and 6 So this is going to be a vector in which you are going to store the answer

Then I went to 7 which is coming for 2 so for 2 the answer is coming 7 Then you ho to another level for 1 the answer is coming 8 and for 3 the answer is coming 9 If I want to print it in single line basically in a sorted order

First I will print for -2 and for -1 and 0 and 1 and 2 and then for 3 So the answer for -2 is 4 then 2 then 1,5,6 for 1 is 3 and 8 and for 2 it is 7 and for 3 it is 9 So lets compare it with the above so it matched

So we got like if we create a mapping of horizontal distancing basically these are all horizontal distances And the nodes we added in it is by level wise nodes So if we create mapping of level order nodes of horizontal nodes then my work is over

What is the meaning of level order node, this is simple another mapping of level with nodes Nodes are list of answer of int type or vector in which want to store int type So I have to create a data structure, create a map which store a horizontal value which will be a integer

So integer, anoter map of int type , nodes which is a vector of int So I stored a map like this you got that So I have created a data structure from here by using the map

This will indicate the horizontal distance this int will indicate level and this will indicate the level of nodes you get this So I created a data structure of this type, by which I can extract this mapping which I have created above Hope you are enjoying, so we have to take care of this

If I want to store anything in this map of nodes Then in input I should have this horizontal distance and this level So I required two things one is horizontal distance and another is level

We are going slow so you get this very well If I want to push or insert anything in this we want this two things Si I say If I am doing level order traversal, I got the answer by level order traversal

So I have to create a queue, lets make type of queue It will have node * and with it two more things are there HD and level two integers are required So I will take a pair of int , int

This one will indicate the horizontal distance and the second one will indicate the level Insert this two inside a pair, so you prepared like this So I want two things one this mapping and another this queue

And by mutualizing this two I will get my desired answer Half things you have got and half things you will get by code Basically the game is to prepare this list, if I do this I will get the answer

Lets go and quickly code, lets prepare a map this one Create a map of type int, map, int, vector of int give space here whenever you close that Naming it as nodes then I create a queue pair of node*,pair of int , int take care when you are closing it

You say this is my q, now I have to return vector of int in answer Now I check if(root == NULL) then simply return the ans Then push in a pair q, which pair

Node root and another pair lets make it Of horizontal distance and level So what we know level is 0 and horizontal distance is also 0 in first line

So you inserted 0,0 , now I say While till my q is not getting empty play game , which game First extract the value which is in the front, this value is there in the front

So name it temp= q.front From this I want the front node , so Node* frontnode =temp.first Then I want the horizontal distance from that

How it will come so temp.second , it will return pair of this type And the first value of this is horizontal distance . first Similarly we will do for level temp.second .second

Up to his you have done , now what your minds say is That in which node I am there make a entry corresponding to that inside the map So basically I say a simple logic

Name of map is nodes in it horizontal distance is HD and level is this .insert, insert the data of the front node So you have created a entry on this particular horizontal distance and level

Now I say simply, if front node left is non null Then push a pair in q, which type, left of front node Second value is the pair so we have to create a pair

In this pair we have horizontal distance and level So when you to left then your horizontal distance get decremented Means horizontal distance -1

Basically when you push child level get incremented from 1,so level +1 Same you say If right node of front is non null

Then push a pair in which you have inserted right node and created a pair Of horizontal distance when you go to right your horizontal distance get incremented from 0 to1 So horizontal distance +1 and your level get incremented definitely in both

So you did this also and you have copied the node So you did this also and when we come out So we have to extract answer from the map

We say for auto i belongs to nodes , what is i here i is basically a row representing here a int value and here a map This int value is horizontal distance and tis map is int, vector

I have interested in extracting this vector So I call it as i,first and this i,second so up to this is completed Going in, for auto j belongs to i.second now lets understand the value of j

So here j represents one row in which data type is like this, got this Then for auto k belongs to j.second This is j.second and this is j.second so k comes to this

So basically I have to push the data which is in the vector which I write k And returned the ans here , lets check once for syntax mistake, if it is there then we will correct it Here it is it is saying there is no function like insert

Lets check it once so in vector there will not insert that will be push back We compile and run it, it say it is running Then lets submit it , it checked the test cases and all are cases are passed

This way we did vertical traversal which I thought will be the complicated thing to teach You can understand teaching is a different thing and coding id different So hope you have got it clearly

Now lets move on to our next code whose name is top view of a binary tree Now this 4 questions are important in this two we will understand and rest two will be very easy Now we assume we have a tree 1 2 3 4 5 6 7

This says top view, if my eye is here and we are trying to see it from here So first I will be viewing this then this then this then this and then that So in short what I am getting is, if I draw this more correctly for you

This 5 is coming below this 1 like this 6 will be coming there So 1 is hiding this 5 and 6 So my answer is coming I see 4 first then 2 then 1 then 3 then 7

Both 5 and 6 are below 1 so I can't see them , so answer will be coming 42137 Approach, how are we going to solve this is important As we did the vertical order traversal think in that way

This will coming in 0 let say this is the number line This is 0 this is -1 then -2 this is 1 and then 2 So for this three 0 is coming here is -1 and here is -2

Here there is 1 and here 2 So first I am going like this for level 0 and store 1 for 0 Then I went for level 1 this way and for -1 the answer is 2 and for 1 it is 3

Then I went like this I say for -2 answer is 4 and then I saw 0 for 5 and 6 Basically they both are on same level I have written like this as you can understand it Already for 0 one value is stored, so now the values coming for 0 will get hide

So for each horizontal distance there should be a 1 to 1 mapping of node So I say We will create a map of int , int This will indicate the horizontal distance and this will indicate the data of node

So if have stored data of node for any horizontal distance, already a value is present in it Then I will discard all other mapping coming to that node, because the present node will hide other nodes for that particular mapping So this is my logic, we will do level order traversing and create the map of int, int

This int will indicate the horizontal distance and this int will indicate the node data But the main logic is the mapping will be one to one mapping That means, if you have mapped an node for a horizontal distance

Then you can't map any node for that same horizontal distance Because that node will hide all other nodes coming for that horizontal distance Same example is there 1 is hiding 5 and 6 logic is going to very simple

Lets code quickly we will use level order traversal We say base case, have to return then create a vector int ans Then check if root == null

Then in this case return ans, ok we reached up to here Now I have create a map of int , int Which is basically mapping of node with horizontal distance

So I call it, amp of int, int and named it top node Then I made queue, what I have to insert in queue So I have to insert horizontal distance inside the map

So created a pair inside queue of type node* and a int which shows you horizontal distance Lets make a pair inside queue First root and then horizontal distance which is 0 at starting

Then I say while not q.empty In this case first take the value which is in the front temp = q.front Then I say node *frontnode= temp.first

Then I say give the horizontal distance that is temp.second , this two things is over Then one to one mapping in map, maintain 1 to 1 mapping or I can write in better way If one value is present for a horizontal distance then do nothing

So if topnode .find, trying to find data in this horizontal distance If you are not getting it then do the first entry for corresponding horizontal distance So you write topnode [hd] = frontNode->data, after this story is same

If frontnode left is non null then in this case Make a pair as I said the data will be pair in q In pair left of frontnode and horizontal distancewhen we go to left

I told you in the above when going to left its decrementing So you did horizontal distance -1 Then next condition will be if your right of front node is non null then push in q ,push what?

Create one pair first then insert right of front node And when you go to right then your horizontal distance becomes 1 from 0 got incremented, so horizontal distance+1 Then you copy then front, this I do at the last , upto that you got

Now I have to store it in my answer So for auto i belongs to top node Basically i is showing a row in which there is value for int, int

So I want to store ans.push back I say first thing in the map is horizontal distance and second is topnode or the answer which I want to find So basically I want i.second and returned answer here

I say run it if any syntax error comes, it will come I know So we did a small mistake here it will be topnode.end, now running So answer is coming correct

So you are trying to find entry corresponding to hd in topnode map If you don't get entry, then there is no mapping present corresponding to it So its output will come equal to topnode,end , got it what I want to say

Submit it ok done, this you did this question Now we can move on to our next problem which is bottom view Same there is not much change in there so you can get it easily

If my map is this type Here there is 1 here 2 here 3 here 4 and 5 6 7 is there So what we are getting is this is in a single line, this is in a single line

Then this 3 nodes are on single line this this is in single line and this is in a single line Its horizontal distance is 0 on going left it is -1 then it is -2 Then if you go to right from -1 that will be 0

Then going right of 0 it will be 1 then going right it will be 2 If you went to right of 1 then it will be 0 So we have to look from the bottom now means your eyes are here

So at first you saw 3 then you saw 2 then 6 and beside 6 1 and 45 both hided Now you saw 4 and then 7 , so you did this like this If we look thier example carefully, so thier exaple is like this

This is 10 then 20 it is 30 this is 40 and this is 60 So this is in a single line and this is in a single line This 2 are in a single line and this is in a single line

This is 0 a ns as we go right of it it is 1 and going to left that will be -1 Form -1 right will be 0 and left will be -2 So if we view from bottom first will come 40 then 20 then 60

behind 60 there is 10 as they are in same horizontal distance so 10 got hided Then will come 30 So 40 20 60 30 this will be your answer

If we think carefully then logic is very simple I say do simple traverse and write answer corresponding to 0 that is 1 Now we traverse here 2 coming corresponding to -1

And 4 is coming corresponds to 1 Then 3 comes in corresponds to -2 Now here comes 5 so you cut 1 and made it 5 then comes 6 so you cut 5 and write 6

Now 7 comes corresponds to 2 So in short if you want to print the answer, so you answer will come first for -2 then -1 then 0 and then for 1 and then 2 So -2 answer is 3, then -1 answer is 2 for 0 it is 6 for 1 it is 4 and for 2 it is 7

So the answer will be 3 2 6 4 7 So what we understand is that the numbers which you are getting corresponds horizontal distance Simply insert it don't see it is first or last

Which will remain in the final list will be your result Simply if I copy paste old code here, lets assume I don't know how to code I say don't check any condition to put just insert it

In short I say remove the condition and run it Now submit it, so all test cases got passed So guys you have done top view , so bottom view question will be very easy

I know I don't have discussed time and space complexity in last three questions You will have to read it yourself and see how map is effecting the time complexity, I didn't discussed them intentionally How map is effecting the time complexity, once think it carefully

Now move on to left view of a binary tree, if we got the left we can do the right one So we are going to learn left view Lets say I have a tree ,8 nodes

Meaning of left view is my eye is here on the left of the tree So what you can see , lets first put the values 1 2 3 4 5 6 7 8 9 So for level 0 I can see 1

Now from here I can see 2 only as 5 got hided behind 2 Now from here I can see 3 only as 4 and 6 got hided behind 3 so the answer will come 3 Now from here I can see 7 only as 8 got hided behind 7

Now from here I can see 9 so answer will be 9 So the answer will be 1 2 3 7 9 this will be my left view Now thinking about approach, how we can solve this

Now a normal thing we are observing that when I am traversing What I have to do is, I have to print only the first nodes of each level In this level first node is this and for this level first node is this this level first node is this

And for this first node is this and for this first node is this So I have to print the first node of each level in direction from left to right So we can do it by level order traversal or by recursive traversal

We did many questions by level order traversal now we will do it by recursive traversal As I can teach it by small code so why we will go for longer one My intent should be to teach you in easy and optimum way

So we go with recursion, level order will be ok also I say you go to any level then print or store the first node So how I will know that this is the first node

If you store the level and track which level is running That means if you are here then you say this is level 0 Now if you call, for left or call for right in both cases you are going to increase the level

Level will be 1, in short you make a variable naming level and increment it as go down If you are tracking level then it will be easy to know that when you went to the next level Now my function will be like this, I am going to solve

It will have thing first thing will be root and next will be level First one will be the base case I know if your root is null then return now we have to go left to right

So I called a function for left and increase level Then for right also called a function and I have to increase the level One thing is pending, that is I have to store the left view here

In short I should have a data structure here Let say I have taken a vector here, and I have to store left view in this vector So I say I impose a condition, if level == size of the vector, you write the name of the vector here

If this condition becomes true then I will come to next level You entered into a new level, that is where we want to go I say we came to new level so I will get the first node then store it in vector quickly

There is no function like store I am saying it for understanding only You store the data of root in it, simple that is the code Lets code once you will get all of that

First I have to create a vector for storing answer vector int ans Now I say I create a solve function and pass root ans and level in it and will return ans here Here I have to create a solve function inside it one root should be there one ans which will be by reference and should be one level

For base case ,if root== null then return If we are in a new level I say you have a condition We entered into a new level

The condition says if your level== ans.size Then you have came to a new level then push pushback data of root Call for left and right, you say solve send answer for root left and level +1

Like that you say solve send answer for root right and level +1 Ok code is up to here lets check ok here is a mistake Lets run it there should not be syntax error in that , no there is not

Now submit it and that passed all the test cases, very nice You got that, I will giving you a homework you have to make recursive tree for this of this code Or make function call stack , ok do it

Now you have a question you have printed it from the left But let say you have to print it from right means your eye is observing from here then So I will see this then this then this then this then this

I say nothing is there if I copy this function and paste it in the right view part And again I copy this function and paste it in the right view part Now I have change it slightly, what is it

When I was printing the lefty view so my call is going from left to right But for the right view my call should go right to left This means your left call will be above the left call, over

Lets run it , submit it submitted this way you can do for right view also So if you can do the the top view then you can do the bottom that way

If you can do the the left view then you can do the right one and vice versa So this way we did 7 questions zig zag traversal boundary traversal top view bottom view left view right view One question is homework for you, that is diagonal traversal of binary tree

You did the vertical one then it will be easy to you I will give small hint for this, simply if tis is like this Then simply you have to print this part, no I will give you in homework

Understand a simple logic when you go right then don't do anything to the horizontal distance And when you come to left then decrement it, rest you can do I trust you Complexity I haven' t discussed in this intentionally

Because I want you do some google search and what is the effect when we use maps in the solution This is a homework for you, time is 3: 57 AM of the morning And I got tired, when ever I think that I think it could be done even better

So thats it for this video, see you at next video, for now BYE BYE !!