Spiral (zig-zag) level order traversal of a binary tree

Write a program to traverse the binary tree in spiral / zigzag level order traversal.

[@yogeshsharma5168]

This man is god for programmer who are struggling to understand programming, he made everything so easy🔥

[@girishkumar5764]

sir u r the best teacher, u way of teaching made every thing easy

[@sidharthpanda8557]

I have been seeing numerous algo and ds videos. This is the best among them.

[@lakshay510]

ITS THE BEST EXPLANATION OUT THERE.

[@ranjanrohit64]

You are the one who makes algorithm so easy to understand.. Lucky to watch your videos.. ❤️

[@Deepak-gj4ni]

Sir your content is must for every computer science student

[@vibhugarg2248]

Sir ,you are absolutely the person who is teaching such questions so nicely!Thankyou so much for the help !

[@PhilGonzalez]

Great job, thank you for this explanation!

[@yifeiren8632]

Great explanation! Thank you so much!

[@siddhu8980]

Simple and Amazing explanation.👍🏻👍🏻👍🏻

[@bhatanand]

Brilliant logic. Thanks for the video.

[@nemoahuja3423]

Amazing explanation. Thank you so much!

[@reyou7]

I love the he says POPPED 😍 You're great sir!

[@amanueltassew804]

lol

[@namanvijay3514]

Great Explanation, kudos!

[@094_ramankumar9]

Nice explanation very helpful

[@lakshayhurria7703]

Nice explanation liked the way you have drawn diagrams to explain

[@prashanttiwari120]

You are doing great job sir

[@ruchirai5775]

awesome explanation !

[@asdbey735]

You're a lifesaver bro !! Do more of leetcode, InterviewBit and HackerRank solutions.

[@dpfit]

Hi Vivek. Thanks for the nice explanation.. It was very helpful.

[@tejaswinysingh8645]

amazing explanation!

[@akashbhadouria6727]

Thank you🙏💕 sir and happy new year.

[@kabboghosh1853]

best explanation on internet

[@sheldon0214]

Nice work!

[@jaytarwe2774]

very well explained sir.

[@kamalsinghbisht1964]

Great Explanation Sir

[@amitkumargupta6722]

just amazing...thanks a lot sir..

[@SpiritualManish]

Nice Sir , Thank You :)

[@ranjanrohit64]

Very well expalained sir.

[@bishwajeet_b_das]

awesome teaching skill.

[@ujjvalsharma5055]

Hi Vivek your videos are amazing and you are a great teacher. Do you have online classes too or maybe be one-to-one doubt session on specific topics?

[@pymondo1147]

Thank you sir:)

[@robertcraig2662]

Good explanation. Thnc

[@jagadeeshp2558]

Amma baboi thopu explanation 🔥🔥

[@pranaychandra8016]

Great Explanation sir please solve more questions like this if you have any online course i am ready to buy it.

[@akshaysharma8492]

awesome sir

[@sameerchaudhari8550]

nice explanations long way to go !

[@veerrajuyeleti8541]

good explanation

[@vm1662]

Great video! Thanks a lot. Quick question. Is it possible to solve this in constant time?

[@rahulkhandelwal46578]

Thank you

[@premprakash8220]

nice explanations

[@sudiptakumardas3547]

Best vedio

[@ruchirsingh3635]

nice sir ji

[@akashninave5001]

Best explanation

[@akashninave5001]

SIR :)

[@subhashishpanda1069]

Great!

[@kausachan4167]

clean

[@arjunsabu4927]

Thank u sir

[@ranjeetranjan8753]

thanx sir

[@ajayrajrana4376]

The best

[@travelogue4566]

nice explanation sir

[@vivekanandkhyade]

Thanks Chandan.!

[@keshavmaheshwari521]

mast sir

[@veerrajuyeleti8541]

sir could you do a video on given a binary tree find the largest subtree having atleast 2 other duplicate subtrees

[@kaasiimaginarium]

Nice

[@vikasvk9174]

helpful .... :)

[@hrmeet0509]

Its giving segmentation fault in GFG ! please update sir

[@subhampandey7374]

What is the time complexity ? O(L) or O(N)

[@NATANSHROCKS]

O(n)

[@jonaskhanwald566]

The diagram itself is self explanatory

[@VikasGupta2014]

You should start with recursive solution of the problem.

[@rajanrocky7215]

Code for the spiral model import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; import java.util.*; //class representing Structure of treeNode in the binary tree class treeNode { int data; treeNode left; treeNode right; treeNode(int value) { data = value; left = null; right = null; } } class Source { static treeNode rootNode; void printSpiral(treeNode rootNode) { if (rootNode == null) return; // NULL check /*Create two stacks named "left2Right" used for printing the levels from left to right and "right2Lef" used for printing the levels from right to left.*/ Stack left2Right = new Stack(); Stack right2Left = new Stack(); // Push root node to the stack right2Left.push(rootNode); // printing the spiral order traversal of the tree while (!right2Left.empty() || !left2Right.empty()) { // print all the nodes in the level from left to right while (!right2Left.empty()) { treeNode tempNode = right2Left.peek(); right2Left.pop(); System.out.print(tempNode.data + " "); // push the right child and then push the left child to the stack "left2Right" if (tempNode.right != null) left2Right.push(tempNode.right); if (tempNode.left != null) left2Right.push(tempNode.left); } // Print all the nodes in the level from right to left while (!left2Right.empty()) { treeNode tempNode = left2Right.peek(); left2Right.pop(); System.out.print(tempNode.data + " "); // push the left child and then push the right child to the stack "right2Left" if (tempNode.left != null) right2Left.push(tempNode.left); if (tempNode.right != null) right2Left.push(tempNode.right); } } } public static void main(String[] args) { Source binaryTree = new Source(); //root node of the binary tree treeNode rootNode; Scanner in = new Scanner(System.in); //number of elements int n = in.nextInt(), element; //queue used to create a binary tree Queue q = new LinkedList(); // creating a new binary tree. rootNode = new treeNode(in.nextInt()); q.add(rootNode); treeNode cur = null; for (int i = 1; i < n; i++) { cur = q.remove(); //Note: if the element is -1 then the node is null element = in.nextInt(); if (element != -1) { cur.left = new treeNode(element); q.add(cur.left); } i++; //Note: if the element is -1 then the node is null element = in.nextInt(); if (element != -1) { cur.right = new treeNode(element); q.add(cur.right); } } //print the spiral order traversal of the tree binaryTree.printSpiral(rootNode); } }

[@pulkitkaushik4539]

thanks bete

[@TotluTV]

how this is different from BFS?

[@sandeepvedavyas8701]

In bfs it would not be zigzag. It would print nodes from left to right in all levels unlike this problem where you have to print left to right and right to left for alternating levels.

[@SEVERANCE850]

Won't the space complexity increase due to this

[@prashanthgatram237]

No its the standard one so dont worry

[@siddhu8980]

Sir can u solve same problem in O(n)

[@h3ct0rgr]

It is O(n) time, all nodes will be popped once from either stack. It is saving two child nodes for each so it is still in order of N.

[@dsk9258]

sir can u please explain the full running code for rubik's cube ... i need it.

[@uditkumar867]

spiral and zig-zag traversal are not same.

[@amitkumargupta6722]

vector findSpiral(Node *root) { vector arr; stack s1,s2; s1.push(root); while(s1.empty()==false || s2.empty()==false) { while(s1.empty()==false) { Node *curr=s1.top(); s1.pop(); arr.push_back(curr->data); if(curr->right!=NULL) s2.push(curr->right); if(curr->left!=NULL) s2.push(curr->left); } while(s2.empty()==false) { Node *curr=s2.top(); s2.pop(); arr.push_back(curr->data); if(curr->left!=NULL) s1.push(curr->left); if(curr->right!=NULL) s1.push(curr->right); } } return arr; }

[@chetan8524]

Only one test case passed at gfg

[@karthikJampani]

Rather than explaining the steps it would be better to say why we are doing it

[@pranaychandra8016]

If anyone is submitting in geeksforgeeks then this is the vALID SOLUTION FOR IT. ide.codingblocks.com/s/97585

[@seraj_valley]

don't use it guyes,its giving TLE

[@preetirautela3537]

Thank you