L19. Zig-Zag or Spiral Traversal in Binary Tree | C++ | Java

[@takeUforward]

Please likeeee, shareeee and subscribeeeeeeee :) Also follow me at Insta: Striver_79

[@rahulsrivastava1040]

Understooooooooood :)

[@democratcobra]

Understand..Thanks for upload.

[@SHASHANKRUSTAGII]

That reverse logic was awesome, I could not think that!! Amazing!!

[@sixth_sense_working]

brother we case use deque

[@111rhishishranjan2]

u shown both c++ solution in that above video. NO Java

[@VikasRana1998]

Both of the solution were of c++. But thanks I understood the concept.

[@Ramu9119]

You are a genius man You have simplified the code as much as possible Hats off to you

[@secondarypemail7181]

The confidence about using a method to solve a problem even before the method to be stated in the video ,is something that boosts confidence,Thank you Striver

[@ExpoDev_Dash]

sir

[@k.vabhavmishra]

Reason behind( size -i -1 ) how we figure out how to take/ put elements in reverse order in vector: Assuming after traversing the 1st level, nodes in queue are {9, 20, 8}, And we are going to traverse 2nd level, which is even line and should print value from right to left [8, 20, 9]. We know there are 3 nodes in current queue, so the vector for this level in final result should be of size 3. Then, queue [i] -> goes to -> vector[queue.size() - 1 - i] i.e. the ith node in current queue should be placed in (queue.size() - 1 - i) position in vector for that line. For example, for node(9), it's index in queue is 0, so its index in vector should be (3-1-0) = 2.

[@sonakshibajpai6445]

thanks!

[@hrithikm.6619]

When I first started this playlist, I was absolutely clueless about trees. And just after watching the first 10 videos or so, I've started to understand how to develop the code by myself. Thank you Striver !

[@saimanaspathapadu1299]

Bro can u pl tell me where to get the notes of the code and explanation

[@dhruvchopra26]

@@saimanaspathapadu1299 Its given in the a2z sheet

[@blastercarter1955]

I did something like that but instead used reverse Inbuilt but you gave alternative by defining the temp vector size on the go nice your content always helpful bro 🥳

[@bitbuybit9193]

This question was asked to me in Adobe Interview

[@utkarshsharma6650]

hashedin too

[@utkarshsharma6650]

how many approaches did the interviewer ask?

[@akashgupta5932]

Did u selected?

[@bitbuybit9193]

@@akashgupta5932 No . But after that I got selected in Walmart

[@bitbuybit9193]

@@utkarshsharma6650 only one

[@jitinroy2246]

Little tweak in level order code, in adding list we check sublist position order. if it's even add, if it's odd reverse and then add. class Solution { public List zigzagLevelOrder(TreeNode root) { // using queue for level order traversal Queue qu=new LinkedList(); // making 2d arraylist List ls=new ArrayList(); // checking if we have tree empty or not if(root==null){ return ls; } // help in finding traversal position int its=0; //add root node in queue qu.add(root); while(!qu.isEmpty()){ int size=qu.size(); // for storing 1d arraylist and after completion of 1d arraylist we append this in 2d arraylist List sublist=new ArrayList(); for(int i=0;i

[@ayushjain7130]

That reverse logic was awesome, I could not think that!! Amazing!!

[@SHASHANKRUSTAGII]

That reverse logic was awesome, I could not think that!! Amazing!!

[@yajatdhawan1865]

Tumara iq kamm hai 🤣🤣

[@SHASHANKRUSTAGII]

@@yajatdhawan1865 Tumara iq kamm hai 🤣🤣

[@pritishpattnaik4674]

Hey Striver Bhaiya , I have done simply the level order traversal as u told and then I maintained a flag variable and if flag is 0 , I Push_backed the level without reversing and if the flag value is 1 , I pushed it back by reversing the level My Code : vector zigzagLevelOrder(TreeNode* root) { int flag = 0; //flag = 0 => L to R and flag = 1 => R to L vector ans; if (root == NULL) return ans; queue q; q.push(root); while (!q.empty()){ int size = q.size(); vector level; for (int i=0 ; ileft != NULL) q.push(temp->left); if (temp->right != NULL) q.push(temp->right); level.push_back(temp->val); } if (flag == 0){ ans.push_back(level); flag = 1; } else if (flag == 1){ vector rev_level = level; reverse(rev_level.begin(), rev_level.end()); ans.push_back(rev_level); flag = 0; } } return ans; }

[@shrikkanthsuresh8971]

Good one mate

[@vaibhavsingh4108]

@@shrikkanthsuresh8971 I also came with same solution .But why are u making a copy like vector rev_level = level; u can just simply reverse the level vector for flag ==1 and then push it into the ans vector

[@pritishpattnaik4674]

@@vaibhavsingh4108 yes u can do that too, I had done this to make the code more readeble

[@keshavchoudhary8857]

This is theee best resource for DSA for sure .Thanks a lot for producing such a nice content for freee....

[@starkrogers6098]

Hello Striver, My Solution is a bit different in that I used 2 stacks for achieving zig zag traversal vector zigZagTraversal(Node* root) { // Code here vector ans; stack s1, s2; int lev = 0; s1.push(root); while(!s1.empty()){ struct Node* temp = s1.top(); s1.pop(); if(temp!=NULL){ ans.push_back(temp->data); if(lev%2 == 0){ if(temp->left!=NULL) s2.push(temp->left); if(temp->right!=NULL) s2.push(temp->right); } else if(lev%2 != 0){ if(temp->right!=NULL) s2.push(temp->right); if(temp->left!=NULL) s2.push(temp->left); } } if(s1.empty()){ swap(s1,s2); lev++; } } return ans; }

[@sohiltr2310]

We can do a simple bfs and just reverse the array stored in odd indexes to get zig zag traversal

[@dreadheadhock]

we can also check the size of temp array before pushing it into final ans, if size is even -> push normally but if odd, reverse temp and then push: vector zigzagLevelOrder(TreeNode* root) { // slight modification in normal level_order vector final_ans; if(root == NULL) return final_ans; queue q; q.push(root); while(!q.empty()){ vector level_ans; int size = q.size(); for(int i = 0; i < size; i++){ TreeNode* temp = q.front(); q.pop(); if(temp -> left != NULL){ q.push(temp -> left); } if(temp -> right != NULL){ q.push(temp -> right); } level_ans.push_back(temp -> val); } // reverse the intermediate array for every odd push if(final_ans.size() % 2 != 0){ reverse(level_ans.begin(), level_ans.end()); } final_ans.push_back(level_ans); } return final_ans; }

[@mohit7717]

reverse will take O(N) that will increase TC as I think

[@humble.660]

Code in Python(Feels much easier to implement): class Solution: def zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]: res = [] if not root: return res q = deque() leftToRight = True q.append(root) while q: qLen = len(q) temp = [] for i in range(qLen): node = q.popleft() if node: if leftToRight: temp = temp + [node.val] else: temp = [node.val] + temp q.append(node.left) q.append(node.right) leftToRight = not leftToRight if temp: res.append(temp) return res

[@spartaninfo3273]

😂😂😂

[@SukritAkhauri]

Your explanation is awesome striver

[@luckyparihar2394]

there is one condition which is required more in code to get it done right, which striver forgots, for(int i=0;i

[@MR-Artist.77777]

Little bit tweaked in pushing the elements to temp. When the elements should be pushed from right to left, I swapped the elements in temp class Solution { public: vector zigzagLevelOrder(TreeNode* root) { if(root == nullptr) return vector{}; vector res; queue helper; bool isRight = false; helper.push(root); while(!helper.empty()){ int size = helper.size(); vector temp; for(int i = 0 ; i < size ; i++){ TreeNode* node = helper.front(); helper.pop(); if(node != nullptr){ temp.push_back(node->val); helper.push(node->left); helper.push(node->right); } } if(isRight){ int left = 0 , right = temp.size() -1 ; while(left < right){ swap(temp[left] , temp[right]); left++; right--; } } isRight = !isRight; if(temp.size() > 0) res.push_back(temp); } return res; } };

[@rohan8758]

*Simplest Java Code & easy to understand:* public static List zigzagLevelOrder(TreeNode root) { List ans = new ArrayList(); // base case if (root == null) { return ans; } Queue queueNodes = new LinkedList(); queueNodes.offer(root); boolean leftToRight = true; while (!queueNodes.isEmpty()) { int size = queueNodes.size(); List temp = new ArrayList(); for (int i = 0; i < size; i++) { TreeNode curr = queueNodes.poll(); temp.add(curr.val); if (curr.left != null) { queueNodes.offer(curr.left); } if (curr.right != null) { queueNodes.offer(curr.right); } } // after this level if (!leftToRight) { Collections.reverse(temp); } leftToRight = !leftToRight; ans.add(temp); } return ans;

[@aadityatelange]

at 5:38 both sides contains c++ code, team you should for this

[@gaganvishwakarma6494]

JAVA solution simplest and easy to understand public List zigzagLevelOrder(TreeNode root) { List ans = new ArrayList(); Queue q = new ArrayDeque(); boolean flag = false; if(root == null) return ans; q.offer(root); while(!q.isEmpty()){ int qsize = q.size(); List temp = new ArrayList(); for(int i = 0;i

[@krishanubiswas6869]

thanks bro....i just had forgotten that there exists a collection framework named reverse 😀

[@debayanbhunia7084]

is there any way we can improve the time complexity because we are having to reverse the temp arraylist in intervals of 2?

[@anushkachavan5065]

Understood the concept very well, Thank You Striver!

[@ashishrawat2266]

Another idea can be. We maintain level_count. if level_count is odd we push right node in queue first than left node. else push left first then right. Space saved!

[@PrinceKumar-el7ob]

Bow down for reverse part using index . I was reversing the vector using reverse function itself as last that's why it was not getting accepted in leetcode.

[@aadarshmishra2504]

It is getting accepted by reverse function as well, you might be reversing in the for loop I guess.

[@aadarshmishra2504]

vector zigzagLevelOrder(TreeNode* root) { if (!root) return {}; queue q; vector ans; bool direction = false; q.push(root); while(!q.empty()) { int sz = q.size(); vector currLevel; for (int i = 0 ; i < sz ; i++) { TreeNode *currNode = q.front(); q.pop(); currLevel.push_back(currNode->val); if (currNode->left) q.push(currNode->left); if (currNode->right) q.push(currNode->right); } if (direction) { reverse(currLevel.begin(),currLevel.end()); } direction = !direction; ans.push_back(currLevel); } return ans; }

[@yagniktalaviya2146]

@@aadarshmishra2504 i reversed in for loop and it got accepted

[@pranavgupta7343]

Hi, I performed the simple level order traversal then reversed the odd rows at the end....Which I think is quite similar to the boolean variable logic mentioned here...Nice explanation

[@anmolverma075]

Thanks for the idea , this was good!

[@lakshsinghania]

we can keep a count of no of lvls : here is the sol class Solution { public: vector zigzagLevelOrder(TreeNode* root) { // if the lvl is an odd num then left to right // or else if the lvl is an even num then right to left vector res; if(root == NULL) return res; queue q; int lvl = 1; q.push(root); while(!q.empty()){ int size = q.size(); vector row; for(int i=0; i left != NULL) q.push(node -> left); if(node -> right != NULL) q.push(node -> right); row.push_back(node -> val); } // if the lvl is even then reverse the row vector if(lvl % 2 == 0) reverse(row.begin(), row.end()); lvl++; res.push_back(row); } return res; } };

[@ritiksingh1230]

Good solution bhai tera samajhne mein mujhe jyada aasani hua

[@nayanjha5670]

class Solution{ public: //Function to store the zig zag order traversal of tree in a list. vector zigZagTraversal(Node* root) { vector res=helper(root); vector ans; for(int i=0;i right != NULL) q.push(node -> right); row.push_back(node -> data); } // if the lvl is even then reverse the row vector if(lvl % 2 == 0) reverse(row.begin(), row.end()); lvl++; res.push_back(row); } return res; } }; gfg question syntax solution

[@adarshchauhan7976]

Helpful ! :) Using similar logic tried to write simple code .. by reversing the 1-d (on /off). Hope it will help. Just added a flag and changing the flag after one iteration and then revering as per flag ..remaining code is just Level Order traversal. vector zigzagLevelOrder(TreeNode* root) { int f = 0 ; queueq; vectorv; if(root == NULL) return v; q.push(root) ; int len ; TreeNode * temp; while(!q.empty()){ len = q.size(); vectorhelp; f = (!f); for(int i = 0 ; i < len ; i++){ temp = q.front(); q.pop(); help.push_back(temp->val); if(temp->right) q.push(temp ->right); if(temp->left) q.push(temp->left); } if(f == 1) reverse(help.begin(), help.end()); v.push_back(help); } return v ; }

[@MandeepSingh-tu4hp]

*****Java - O(N) ***** solution without using Dqueue and reverse method. I did struggle with revese logic without adding additional complexity finally have something that work class Solution { public List zigzagLevelOrder(TreeNode root) { Queue queue = new LinkedList(); List res = new LinkedList(); if(root == null) return res; queue.add(root); boolean flag=false; while(queue.size()>0) { int size = queue.size(); LinkedList subList = new LinkedList(); for(int i =0; i

[@saurabhjejurkar5065]

Great Solution

[@Japhu]

Well done, this one is more intuitive than the Leetcode sample

[@nihalnandannayak8869]

I solved this problem using 2 stack , but this is the best approach

[@sparshsharma6068]

5:57 , Bhaiya dono side me c++ wala code hai screen pe. But jarurt nhi padi code dekhne ki, explanation se hi clear hogya tha ke kasie hoga code. Amazing Explanation, likeeeed, shareeeed and subscribeeeeeeeed : )

[@willturner3440]

Reverse nhi kr paoge, dekh lo aage bhi

[@sparshsharma6068]

@@willturner3440 what do you mean?

[@rakshayadav1892]

Python code: class Solution: def zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]: if not root: return [] st=[root] ans=[] flag=True while st: t=[] l=[] while st: k=st.pop(0) t.append(k.val) if k.left: l.append(k.left) if k.right: l.append(k.right) if flag: ans.append(t) flag=False st=l else: ans.append(t[::-1]) flag=True st=l return ans

[@RITIKKUMAR-mo9ki]

Another Solution using dict in O(n) def zigZagTraversal(self, root): d={} q=deque() q.append([root,0]) while(len(q)!=0): x=q.popleft() if(x[0].left): q.append([x[0].left,x[1]+1]) if(x[0].right): q.append([x[0].right,x[1]+1]) if(x[1] not in d): d[x[1]]=[x[0].data] else: d[x[1]].append(x[0].data) ans=[] for i in sorted(d.keys()): if(i%2!=0): ans.extend(d[i][::-1]) else: ans.extend(d[i]) return ans

[@tonyconor681]

We can basically do it using 2 stack approach the storing the reverse from 2nd stack to arraylist as a TreeNode ...

[@tonyconor681]

But the main issue is having the time complexity & the most important space complexity increase using 2 stack can someone help out

[@harsh2k2]

class Solution make the below changes in level order traversal code { public: vector> zigzagLevelOrder(TreeNode *root) { vector> ans; if (root == NULL) return ans; queue q; q.push(root); bool l2r = true; // added in level order travesal code of striver while (!q.empty()) { int size = q.size(); vector level; for (int i = 0; i < size; i++) { TreeNode *node = q.front(); q.pop(); if (node->left != NULL) q.push(node->left); if (node->right != NULL) q.push(node->right); level.push_back(node->val); } if (!l2r) reverse(level.begin(), level.end()); // added in level order travesal code of striver ans.push_back(level); l2r = !l2r; // to change the direction } return ans; } };

[@lifehustlers164]

Completed 20/54(37% done) !!!

[@mohith.n.official]

We can do level order traversal and w can reverse after each level right based on flag

[@NishilPatel-d2m]

class Solution { public: vector zigzagLevelOrder(TreeNode* root) { // for zigzag level order traversal if c = odd than left to right and vice versa vector ans; if(!root)return ans; queue q; q.push(root); int c = 1; while(!q.empty()) { int size = q.size(); vector level; TreeNode* temp = root; for(int i = 0;ival); if(temp->left)q.push(temp->left); if(temp->right)q.push(temp->right); } if(c%2==0) { reverse(level.begin(),level.end()); } ans.push_back(level); c = (c + 1)%2; } return ans; } }; Author - Nishil Patel

[@cs04abhinavasthana36]

just check if level is odd or even : if level is even store from Left to right and if level is odd store from right to left. code is below: vector zigzagLevelOrder(TreeNode* root) { if(root==NULL)return {}; vector ans; queue q; q.push(root); int level=0; while(!q.empty()){ int s=q.size(); vector path; for(int i=0;ival); if(node->left)q.push(node->left); if(node->right)q.push(node->right); } if(level%2!=0)reverse(path.begin(),path.end()); ans.push_back(path); level++; } return ans; }

[@rohangangwar6604]

what a explanation bhaiya i am using reverse function instead of using this ....issi ka naam striver bhaiya maza aagya bhaiya aapke explanation se hi code kiya tha bina dekhe bs reverse use kiya end me yeh dekhe ki aapne kaise kiya maza aagya smartly reverse these .....HATS OFF

[@jitinroy2246]

more simple form for right->left index. add elements in first-first it will automatic be reverse way. class Solution { public List zigzagLevelOrder(TreeNode root) { // using queue for level order traversal Queue qu=new LinkedList(); // making 2d arraylist List ls=new ArrayList(); // checking if we have tree empty or not if(root==null){ return ls; } // flag=true means left->right, false means right->left boolean flag=true; //add root node in queue qu.add(root); while(!qu.isEmpty()){ int size=qu.size(); // for storing 1d arraylist and after completion of 1d arraylist we append this in 2d arraylist List sublist=new ArrayList(); for(int i=0;i

[@stith_pragya]

Thank You So Much for this wonderful video...........🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻

[@Lime-rr6te]

guys, code wagera share krne ke liye pastebin use kr liya kro, also dequeue kr skte ho instead of vector, (just personal pref), (vector is faster ofc)

[@hareshnayak7302]

understood,thanks striver for this amazing video.

[@huungryyyy]

🤩🤩 great explanation loved it

[@ganeshjaggineni4097]

NICE SUPER EXCELLENT MOTIVATED

[@amansaini4969]

Hi Striver, Your reverse logic is syntactically wrong, you cant put a element a certain index if list is currently of not that size

[@pranavgupta7343]

Here's the code ....I just reversed the odd rows at the end after level order.. class Solution { public: vector level(TreeNode* root){ vector ans; if(root == NULL) return ans; queue q; q.push(root); while(!q.empty()){ int size = q.size(); vector lvl; lvl.clear(); for(int i = 0; i < size; i++){ TreeNode* curr = q.front(); q.pop(); if(curr->left) q.push(curr->left); if(curr->right) q.push(curr->right); lvl.push_back(curr->val); } ans.push_back(lvl); } for(int i = 1; i < ans.size(); i+= 2){ reverse(ans[i].begin(), ans[i].end()); } return ans; } vector zigzagLevelOrder(TreeNode* root) { return level(root); } };

[@rajaroy43]

This question was asked to me in an Amazon interview .

[@nilesh69420]

Both are C++ solutions. Also the solution provided in the article won't work for Java. In C++, we have liberty of using vector like array after declaring its size but in java, we can't put element at that index in ArrayList. If we add(index, element), it will just push the arrayList from that index to the next index which will not be useful. We can use LinkedList or Collections.reverseOrder.

[@manantyagi614]

Instead of the queue, we can also use dequeue so that we don't have to maintain the index.

[@Adityasharma-ii3dg]

@ayushnegi4432 maybe he's talking about this

[@Adityasharma-ii3dg]

@ayushnegi4432 class Solution { public: vector zigzagLevelOrder(TreeNode* root) { vector ans; if(!root) return ans; queue q; q.push(root); bool flag=0; // vector v; while(!q.empty()){ int n=q.size(); vector v; for(int i=0;ileft) q.push(top->left); if(top->right) q.push(top->right); v.push_back(top->val); } flag=(!flag); if(flag==1) { ans.push_back(v); } else { reverse(v.begin(),v.end()); ans.push_back(v); } } return ans; } };

[@Adityasharma-ii3dg]

@ayushnegi4432 i am aditya sharma remember the name.

[@ishangujarathi10]

Loved the logic part, understood completely!!!

[@prabhakaran5542]

Understood ❤

[@bharathkumar5870]

if interviewer asks code the problem without using reverse,use dque datastructure

[@shanmukhigampa460]

Both the solutions are in C++ code, but thankyou!!

[@nishchaygupta9988]

We can also try to think of Left View of binary tree at one level and Right View of Binary Tree at the next level as required. If there's a problem in this approach, please feel free to correct me.

[@parthsalat]

Please post the code here

[@mayankmewar5049]

I used a queue for storing from left to right and a stack for reverse, but your technique looks nicer

[@hustler516]

Same approach came into my mind

[@hustler516]

But time complexity will be more in this .....more than O(N)

[@tonyconor681]

Queue approach is having more time & space complexity

[@abhayjaiswal5156]

Bro both the solution code shown in this video is of C++, just for information sake , Thanks for the video anyways. Also heard about ur bad health due to some inhaling issue.. Get well soon for that.. more power to you

[@sapnavats9105]

I would have approached it using using modular operator with level order traversal to keep count of even and odd levels and accordingly apply reverse operation.

[@anujjain9273]

i did the same the solution got accepted too but time complexity for reverse function is o(n) which would further increase the time complexity

[@rohangangwar6604]

woow me too instead of switching the flag i maintain a counter if it is even then do nothing otherwise apply reverse

[@bhavkushwaha]

Thankyou Striver, Understood!

[@mriduljain1981]

completed lecture 19 of Tree playlist.

[@atharvakulkarni2024]

REVERSE LOGIC WAS AMAZING BHAIYYA....WONDERFULL VIDEOS TILL NOW....EXCITED TO MOVE FURTHER...

[@mellowftw]

Yeah really impressive

[@manikantasai6118]

This was asked in Groww to me for sde internship

[@enigmanarratives1]

this code is beauty i did it using reverse function but this is far better than that i wish soon i will be able to think fast and correct like you

[@dreamer6911]

make sure to like the video if u understand, like i did.

[@ayushmansharma5321]

i think it is very complex //my approach using 2 stack with same complexity class GFG { //Function to store the zig zag order traversal of tree in a list. ArrayList zigZagTraversal(Node root) { Stack ms = new Stack(); Stack hs = new Stack(); ms.push(root); int level = 0; ArrayList al = new ArrayList(); while(ms.size()>0){ Node temp = ms.pop(); al.add(temp.data); if(level%2==0){ if(temp.left!=null) hs.push(temp.left); if(temp.right!=null) hs.push(temp.right); } else if(level%2!=0){ if(temp.right!=null) hs.push(temp.right); if(temp.left!=null) hs.push(temp.left); } if(ms.size()==0){ ms = hs; hs = new Stack(); level++; } } return al; }

[@Saurabh-fe2bg]

I was able to code by myself thanks man!!

[@kartikverma6412]

or we can simply just reverse the sub vector which is at the odd index, after we built the whole 2d array for level order traversal...

[@smitsonani7006]

nice explanation sir G

[@rohitbagade9182]

Yes they are very much exactly Identical

[@easycode3189]

Greate Explanation || Thank you So Much

[@ritikshandilya7075]

Thanks Striver

[@SouravKumar-tc2ql]

bro please complete tree series from sde sheet . I HAVE MY AMAZON INTERVIEW

[@sans.creates]

hey when is it, i too have

[@apmotivationakashparmar722]

Thank you so much

[@deepbytes4854]

# Python solution : class Solution: def zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]: res = [] if root is None : return res q =[root] # will have list of list containing elements in level in zigzag leftToRightFlag = True # initially we move from left to right while q : size = len(q) row = [] for i in range(size) : node = q.pop(0) if node.left : q.append(node.left) if node.right : q.append(node.right) row.append(node.val) # here row will contain elements of one level if leftToRightFlag : res.append(row) # append as it is for left to right leftToRightFlag = False # set flag false else : row = row[::-1] # reverse row because we want right to left res.append(row) leftToRightFlag = True return res

[@BinayMann]

Thanks , I understood

[@pratyayamrit7336]

which is a better approach , this one or 2 stack approach ? except for the ovious fact i am using two stack ?

[@SatyamPratap-sg1nz]

what a fantabulous code quality!

[@jasonbrody4618]

Liked. Cfbr will watch after some time

[@cinime]

Understood! Such a great explanation as always, thank you very much!!

[@riturajanand6508]

Can we do the same easily using deque or there will be any concerns involved?

[@AnkitRajput-gc2ht]

both the code at end was of c++, so incase for refernce to a complete java code in a easy way : /* OM VIGHNHARTAYE NAMO NAMAH : */ import java.lang.*; import java.util.*; class node { int data; node left; node right; public node(int data) { this.data = data; this.left = null; this.right = null; } } class ZIGZAG { public static void main(String args[]) { node root = new node(1); root.left = new node(2); root.right = new node(3); root.left.left = new node(4); root.left.right = new node(5); root.right.right = new node(6); root.left.left.left = new node(7); root.left.right.left = new node(8); root.left.right.right = new node(9); solution s = new solution(); s.zigzagtraversal(root); } } class solution { void zigzagtraversal(node root) { List ds = new LinkedList(); Queue q = new LinkedList(); boolean flag = false; q.offer(root); while (!q.isEmpty()) { int size = q.size(); List level = new ArrayList(size); for (int i = 0; i < size; i++) { node temp = q.poll(); if (temp.left != null) q.offer(temp.left); if (temp.right != null) q.offer(temp.right); level.add(temp); } if (flag) { Collections.reverse(level); } flag = !flag; ds.add(level); } for (List level : ds) { for (node n : level) { System.out.print(n.data + " "); } System.out.println(); } } }

[@aryashjain7893]

dono code cpp ke hai bhai :) koi nahi nice explaination , loved the video

[@rishabhgupta9846]

understood,able to solve by myself

[@ravimane5508]

There was C++ code on both side.

[@suheabkhan2546]

Best tree series

[@tishajain397]

Bring series on dp and backtracking plzzzzz bro n u r doing absolutely great

[@lone_wolf7721]

dp ka series aayega dipawali me ...aur agar abhi dekhna hai to aditya verma ka dekh lo

[@priyankasetiya1358]

Java code class Solution { public List zigzagLevelOrder(TreeNode root) { List ds=new ArrayList(); if(root==null){ return ds; } Queue queue=new LinkedList(); queue.add(root); boolean flag=true;//whenever this flag will be true we will be doing right to left traversal at that level while(!queue.isEmpty()){ List list=new ArrayList(); int queueSize=queue.size(); for(int i=0;i

[@NoxuzBlog]

genious approach

[@vaibhavsinghania8368]

Hey in the java code queue declaration line is throwing error on my ide as: "The type Queue is not generic; it cannot be parameterized with arguments ". Can someone pls help.

[@thegreekgoat98]

Damn! Striver is a magician...

[@ankitasinha9912]

How is time complexity O(N) here as it has nested two loops shouldn't it be O(N^2)?

[@Shivi32590]

thank you

[@piyushverma8207]

What would be the space complexity of this method? class Solution { public: vector zigzagLevelOrder(TreeNode* root) { if(root == NULL) return {}; vector ans; stack st1; stack st2; st1.push(root); bool but = true; while(!st1.empty() || !st2.empty()){ if(but){ int size = st1.size(); vector midAns; for(int i=0; ival); if(node->left!=NULL) st2.push(node->left); if(node->right!=NULL) st2.push(node->right); } ans.push_back(midAns); but = false; } else{ int size = st2.size(); vector midAns; for(int i=0; ival); if(node->right!=NULL) st1.push(node->right); if(node->left!=NULL) st1.push(node->left); } ans.push_back(midAns); but = true; } } return ans; } };

[@jatin_lanje]

O(n)

[@TheLearningLab898]

Brother, your content is fantastic and it speaks for itself. You don't have to ask us to like your videos because we genuinely appreciate the effort you put into creating such great content. Keep up the good work!😍

[@vinodsonatakke1879]

Thank you for such valuable contents

[@sarathchandra941]

Can anyone tell me why I'm not getting any error when creating list of List as below List li = new ArrayList (); But getting error when creating as below List li = new ArrayList (); What is the difference in both.. Here my aim is to have the list of list of integers

[@siddharthupadhyay4246]

Thank sir you do soo good to us

[@himanshidafouty347]

Understood

[@anshuraj8077]

stack hai ya queue