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 !
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
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 🥳
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 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
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.
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
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 : )
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
*****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
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);
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 ; }
*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;
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.
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!
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; }
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
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; } };
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.
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
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
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; }
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
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; } };
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; }
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
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.
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
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
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.
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
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!😍
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
Bhaiya I have a doubt...in the java code you have used add(0,node.val) but this has a time complexity of O(n)...so I don't think the time complexity is O(n) for the java solution.
@@Codistency I think in java, using a stack to temporarily store the node values for the even level would be a better approach. Incase you find a solution without stack, please share it here, I would be more than happy to know about an O(n) solution without using stack in java.
Can we do this with a deque, like if flag is 0, we can do pop front and do push back of its child, if flag is 1, we can do pop back and do push front of its child, is that an accepted one??
Yes, it will work. in even levels: pop from the front and push to back (left then right) in odd levels: pop from the rear and push to front (right then left)
I tried the same logic for spiral traversal in gfg and it worked, below is the code used. If you any doubts feel free to ask in comments. vector findSpiral(Node *root) { //Your code here deque q; q.push_back(root); vector ans; bool flag=1; if(root==NULL) return ans; while(!q.empty()) { int count=q.size(); for(int i=0;ileft) q.push_back(temp->left); if(temp->right) q.push_back(temp->right); ans.push_back(temp->data); } else { Node *temp=q.back(); q.pop_back(); if(temp->right) q.push_front(temp->right); if(temp->left) q.push_front(temp->left); ans.push_back(temp->data); } } flag=!flag; } return ans; }
bhaiya dono side ke codes aapne C++ me hi provide kr diye hai, java me code nhi diya by mistake. Is is aviliable at Website so that i can refer from there.
![BabyChiefDoit - Too Slow (feat. STAR BANDZ) [Official Music Video]](http://i.ytimg.com/vi/zayaxws7RPg/mqdefault.jpg)
Please likeeee, shareeee and subscribeeeeeeee :) Also follow me at Insta: Striver_79
Understooooooooood :)
Understand..Thanks for upload.
That reverse logic was awesome, I could not think that!! Amazing!!
brother we case use deque
u shown both c++ solution in that above video. NO Java
Both of the solution were of c++. But thanks I understood the concept.
This question was asked to me in Adobe Interview
hashedin too
how many approaches did the interviewer ask?
Did u selected?
@@akashgupta5932 No . But after that I got selected in Walmart
@@utkarshsharma6650 only one
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 !
Bro can u pl tell me where to get the notes of the code and explanation
@@saimanaspathapadu1299 Its given in the a2z sheet
You are a genius man You have simplified the code as much as possible
Hats off to you
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
sir
That reverse logic was awesome, I could not think that!! Amazing!!
That reverse logic was awesome, I could not think that!! Amazing!!
Tumara iq kamm hai 🤣🤣
@@yajatdhawan1865 Tumara iq kamm hai 🤣🤣
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 🥳
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;
}
Good one mate
@@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
@@vaibhavsingh4108 yes u can do that too, I had done this to make the code more readeble
This is theee best resource for DSA for sure .Thanks a lot for producing such a nice content for freee....
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.
thanks!
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
Your explanation is awesome striver
Understood the concept very well, Thank You Striver!
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 : )
Reverse nhi kr paoge, dekh lo aage bhi
@@willturner3440 what do you mean?
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
thanks bro....i just had forgotten that there exists a collection framework named reverse 😀
is there any way we can improve the time complexity because we are having to reverse the temp arraylist in intervals of 2?
*****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
Great Solution
Well done, this one is more intuitive than the Leetcode sample
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;
}
We can do a simple bfs and just reverse the array stored in odd indexes to get zig zag traversal
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 ;
}
*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;
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.
It is getting accepted by reverse function as well, you might be reversing in the for loop I guess.
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;
}
@@aadarshmishra2504 i reversed in for loop and it got accepted
I solved this problem using 2 stack , but this is the best approach
understood,thanks striver for this amazing video.
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!
Thank You So Much for this wonderful video...........🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
Hi Striver,
Your reverse logic is syntactically wrong, you cant put a element a certain index if list is currently of not that size
there is one condition which is required more in code to get it done right, which striver forgots,
for(int i=0;i
🤩🤩 great explanation loved it
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;
}
reverse will take O(N) that will increase TC as I think
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
Thanks for the idea , this was good!
NICE SUPER EXCELLENT MOTIVATED
Understood ❤
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;
}
};
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.
Please post the code here
Loved the logic part, understood completely!!!
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
😂😂😂
Completed 20/54(37% done) !!!
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
We can basically do it using 2 stack approach the storing the reverse from 2nd stack to arraylist as a TreeNode ...
But the main issue is having the time complexity & the most important space complexity increase using 2 stack can someone help out
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;
}
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)
This question was asked to me in an Amazon interview .
at 5:38 both sides contains c++ code, team you should for this
Thankyou Striver, Understood!
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
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;
}
};
Good solution bhai tera samajhne mein mujhe jyada aasani hua
I was able to code by myself thanks man!!
Understood! Such a great explanation as always, thank you very much!!
This was asked in Groww to me for sde internship
Thanks , I understood
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;
}
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
I used a queue for storing from left to right and a stack for reverse, but your technique looks nicer
Same approach came into my mind
But time complexity will be more in this .....more than O(N)
Queue approach is having more time & space complexity
REVERSE LOGIC WAS AMAZING BHAIYYA....WONDERFULL VIDEOS TILL NOW....EXCITED TO MOVE FURTHER...
Yeah really impressive
thank you
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.
Instead of the queue, we can also use dequeue so that we don't have to maintain the index.
@ayushnegi4432 maybe he's talking about this
@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;
}
};
@ayushnegi4432
i am aditya sharma
remember the name.
Both the solutions are in C++ code, but thankyou!!
Thanks Striver
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
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
Greate Explanation || Thank you So Much
Yes they are very much exactly Identical
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
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.
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
woow me too instead of switching the flag i maintain a counter if it is even then do nothing otherwise apply reverse
what if there is null in any level we dont have to push it why??
Understood
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
understood,able to solve by myself
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...
make sure to like the video if u understand, like i did.
understood.
nice explanation sir G
if interviewer asks code the problem without using reverse,use dque datastructure
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!😍
completed lecture 19 of Tree playlist.
what a fantabulous code quality!
genious approach
Liked. Cfbr will watch after some time
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
thankyou struer
dono code cpp ke hai bhai :)
koi nahi nice explaination , loved the video
bro please complete tree series from sde sheet .
I HAVE MY AMAZON INTERVIEW
hey when is it, i too have
Thank you for such valuable contents
cant we just reverse the vectors at odd indexes in vector of vectors
Bhaiya I have a doubt...in the java code you have used add(0,node.val) but this has a time complexity of O(n)...so I don't think the time complexity is O(n) for the java solution.
I did not see when did I use this? Line number of code ?
wait he haven't mentioned java code they both are cpp itself
@@purellajajisaipavankumar651 oops my bad, he got that from description, the java code 😅
@@takeUforward Line no. 18 of java code
@@Codistency I think in java, using a stack to temporarily store the node values for the even level would be a better approach. Incase you find a solution without stack, please share it here, I would be more than happy to know about an O(n) solution without using stack in java.
Can we do this with a deque, like if flag is 0, we can do pop front and do push back of its child, if flag is 1, we can do pop back and do push front of its child, is that an accepted one??
Try to write n submit, problem links in description..
a kind of 01 BFS right??
might work!!
Yes, it will work.
in even levels: pop from the front and push to back (left then right)
in odd levels: pop from the rear and push to front (right then left)
I tried the same logic for spiral traversal in gfg and it worked, below is the code used. If you any doubts feel free to ask in comments.
vector findSpiral(Node *root)
{
//Your code here
deque q;
q.push_back(root);
vector ans;
bool flag=1;
if(root==NULL) return ans;
while(!q.empty())
{
int count=q.size();
for(int i=0;ileft) q.push_back(temp->left);
if(temp->right) q.push_back(temp->right);
ans.push_back(temp->data);
}
else
{
Node *temp=q.back();
q.pop_back();
if(temp->right) q.push_front(temp->right);
if(temp->left) q.push_front(temp->left);
ans.push_back(temp->data);
}
}
flag=!flag;
}
return ans;
}
question for the same: practice.geeksforgeeks.org/problems/level-order-traversal-in-spiral-form/1/?track=dsa-workshop-1-trees&batchId=308
Thx
bhaiya dono side ke codes aapne C++ me hi provide kr diye hai, java me code nhi diya by mistake. Is is aviliable at Website so that i can refer from there.
Can we do the same easily using deque or there will be any concerns involved?
stack hai ya queue
Thank sir you do soo good to us
How is time complexity O(N) here as it has nested two loops shouldn't it be O(N^2)?
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);
}
};
which is a better approach , this one or 2 stack approach ? except for the ovious fact i am using two stack ?
Bring series on dp and backtracking plzzzzz bro n u r doing absolutely great
dp ka series aayega dipawali me ...aur agar abhi dekhna hai to aditya verma ka dekh lo
Right side me Java code ni h pyare striver bhaiya.
Great explanation🤩
can we do it by using deque data structure so we can insert and pop from wherever we want?????
Thank you sir