Zig Zag Traversal Binary Search Tree | C++ Placement Course | Lecture 28.7

[@anubhavgoyal2458]

Another approach 1st Use deque 2nd do level order traversal and when level is even (1 based index) reverse print elements otherwise simple print elements

[@tarunbisht8016]

yeah 2nd one is great

[@khushankmadaan9407]

// For the above solution, you can just perform the simple level order traversal. Considering 1 based indexing // If level is odd then then just print the elements. //If level is even just use a stack and push the elements into it and once level is traversed start popping and print the values. You will get values in reverse order because of LIFO nature of Stack. //And finally check at the end if stack still contains elements, empty the stack and print the element. vector ZigZag(Node *root) { queue q; stack st; vector ans; q.push(root); q.push(NULL); int level = 1; while (!q.empty()) { Node *x = q.front(); q.pop(); if (x != NULL) { if (level % 2 == 1) { ans.push_back(x->data); } else { st.push(x->data); } if (x->left) { q.push(x->left); } if (x->right) { q.push(x->right); } } else if (!q.empty()) { q.push(NULL); while (!st.empty()) { ans.push_back(st.top()); st.pop(); } level++; } } while (!st.empty()) { ans.push_back(st.top()); st.pop(); } return ans; }

[@mandeep2192]

why u push NULL in queue in 4th line

[@khushankmadaan9407]

@@mandeep2192 To specify that one level has been traversed completely. At first level there is only one node so, i pushed Null just after pushing the Root

[@mandeep2192]

@@khushankmadaan9407 i got it bro thnx nice code.

[@keshavraghav3896]

i have got the same intuition of check for odd or even, but i find difficulty in writting the code 😓... thnx for this one.

[@manabsaha5336]

Nice

[@005_adarshprajapati9]

just fall in love with background music

[@jaychotalia7542]

The Example used to do a dry run is not a BST. Because 6 is greater than 4, then also it is included in the left subtree.

[@adityabhandari6688]

yes, I think the link of node with data 4 was attached mistakenly to right of 2 instead of left to 3

[@rutvikrana512]

We can use deque also instead of using two stacks 🙂 void zigzag(Node* root){ deque Q; Q.push_back(root); Q.push_back(NULL); bool ltr = true; while(Q.size()>1){ if(ltr){ Node* n = Q.front(); if(n){ std::cout data left)Q.push_back(n->left); if(n->right)Q.push_back(n->right); Q.pop_front(); } else{ ltr = !ltr; } } else{ Node* n = Q.back(); if(n){ std::cout data right)Q.push_front(n->right); if(n->left)Q.push_front(n->left); Q.pop_back(); } else{ ltr = !ltr; } } } cout

[@EverythingaboutTechPro]

Cool ! But we can simply use Level order traversal and reverse the vector that we make (alternatively)

[@tejasjoshi1907]

@@EverythingaboutTechPro perfect

[@tarunbisht8016]

@@EverythingaboutTechPro even there is no need of reverse like for alternative row just store elements from backward

[@kumarivandana1554]

I think no need to check if temp is NULL or not in while loop because we already checked in the first line if root is NULL then return and the Nodes are pushed only when they are not NULL

[@saint8298]

alternate approach (decreased space complexity): void zigZagTraversal(node *&root) { vector q; q.push_back(nullptr); q.push_back(root); int reader = q.size() - 1; bool traverseDirection = true, hasChildrens = false; while (true) { node *current = q[reader]; if (current == nullptr) { if (!hasChildrens) break; hasChildrens = false; traverseDirection = !traverseDirection; reader = q.size(); cout right) { hasChildrens = true; q.push_back(current->right); } } else { if (current->right) { hasChildrens = true; q.push_back(current->right); } if (current->left) { hasChildrens = true; q.push_back(current->left); } } q[reader] = nullptr; } reader--; } }

[@arshiparveen1728]

example is not a BST ,it's not following the proper format of nodes in an ideal BST

[@sameerraj5800]

This is not a BST. Left Subtree of 4 contains 6 which is wrong.

[@varunchoudhary8797]

Very nice 👍👍

[@swastikrana2670]

great explanation

[@priyabratasingha174]

vector ZigZag(Node*root) { vector res; queue q; q.push(root); Node*p=nullptr; int level=0; while(!q.empty()) { int n=q.size(); level++; stack st; while(n--) { p=q.front(); q.pop(); if(level&1) { res.push_back(p->data); } else { st.push(p->data); } if(p->left)q.push(p->left); if(p->right)q.push(p->right); } while(!st.empty()) { res.push_back(st.top()); st.pop(); } } return res; }

[@xerOnn35]

Thanks mam!.

[@aakashthakre244]

Respected Sir/Mam Please make a video on how to practice Coding and solve ques from which platform and how to revise ques in coding because practice from geeks for geeks is difficult for me how to properly Practice particular ques and topics i am revising ques of array though i am not able to solve ques of geeks for geeks hacker earth and all the course is going bit we have to study also for backportion so how to revise and solve ques please make a dedicated video 🙏🙏🙏🙏🙏🙏🙏🙏🙏🙏🙏🙏🙏🙏🙏🙏🙏🙏🙏

[@rutvikrana512]

All the gfg practice questions are also in their feeds, we can just simply learn from that, besides gfg practice window has option to use hints if necessary, why do you need videos of everything ? Just read gfg posts you will learn more than this whole channel's content.

[@manitianajay45]

que attempt karne se phle bhul ja sab stack binary tree kuchh mat soch aaram se padh aur soch tu usse kaise solve karega jaise tu solve karega waise waise kaam tere code ko bata de bas time comp aur space ke baare main sochna baaki ho jaayega sab

[@051-rahulchourasia8]

the animated example is not abst

[@santoshbhardwaj536]

Sir java ka animated course kabtak aayga

[@sarthaktyagii7683]

good work team

[@30jayrathi59]

It is not BSt zigzag traversal it is binary tree zigzag traversal

[@avronilbanerjee5302]

Suddenly the bass increased in the music ??

[@yogesh1478]

whta is the name of song in intro

[@aakashthakre244]

Feeling demotivated because of not able to solve prblms on platforms

[@melodytunes2204]

tension mat le bhai tu akela nhi

[@aritraroy6375]

Bhaiya kya aap unacademy me 12th ka batch suru karenge¿??????? Please answer I am in very dipression for this 😭😭😭😭😭🙏🙏🙏

[@051-rahulchourasia8]

the example is not bst

[@ashuchauhan3234]

useless approch

[@adwaiymahajan8953]

Bhaiya please reply to me .🙏🙏🙏 I really want to work with you , I want to help you . I am in 10th class now and good in almost every subject specially science and math. Please tell me if I could contribute 🙏🙏

[@ajaytanwar508]

bad approach

[@shubhamgoel3998]

void zigZag2(node *root) { if (root==NULL) { return; } deque d1; bool ltr = false; d1.push_front(NULL); d1.push_front(root); while (!d1.empty()) { if (ltr) { node *temp = d1.back(); d1.pop_back(); if (temp!=NULL) { cout data right != NULL) { d1.push_front(temp->right); } if (temp->left != NULL) { d1.push_front(temp->left); } } else if (!d1.empty()) { d1.push_back(NULL); ltr = !ltr; } } else { node *temp = d1.front(); d1.pop_front(); if (temp!=NULL) { cout data left != NULL) { d1.push_back(temp->left); } if (temp->right != NULL) { d1.push_back(temp->right); } } else if (!d1.empty()) { d1.push_front(NULL); ltr = !ltr; } } } }