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); } }
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.
This man is god for programmer who are struggling to understand programming, he made everything so easy🔥
sir u r the best teacher, u way of teaching made every thing easy
I have been seeing numerous algo and ds videos. This is the best among them.
ITS THE BEST EXPLANATION OUT THERE.
You are the one who makes algorithm so easy to understand.. Lucky to watch your videos.. ❤️
Sir ,you are absolutely the person who is teaching such questions so nicely!Thankyou so much for the help !
Sir your content is must for every computer science student
Brilliant logic. Thanks for the video.
Simple and Amazing explanation.👍🏻👍🏻👍🏻
I love the he says POPPED 😍 You're great sir!
lol
Nice explanation liked the way you have drawn diagrams to explain
You're a lifesaver bro !! Do more of leetcode, InterviewBit and HackerRank solutions.
Amazing explanation. Thank you so much!
Nice explanation very helpful
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?
Hi Vivek. Thanks for the nice explanation.. It was very helpful.
best explanation on internet
Great Explanation, kudos!
Amma baboi thopu explanation 🔥🔥
You are doing great job sir
Great Explanation Sir
Great Explanation sir please solve more questions like this if you have any online course i am ready to buy it.
Great job, thank you for this explanation!
Nice work!
amazing explanation!
just amazing...thanks a lot sir..
Thank you🙏💕 sir and happy new year.
Good explanation. Thnc
awesome explanation !
Best explanation
SIR :)
Great video! Thanks a lot.
Quick question. Is it possible to solve this in constant time?
Very well expalained sir.
awesome sir
Best vedio
very well explained sir.
awesome teaching skill.
You should start with recursive solution of the problem.
sir could you do a video on given a binary tree find the largest subtree having atleast 2 other duplicate subtrees
nice sir ji
nice explanations long way to go !
nice explanation sir
Thanks Chandan.!
Nice Sir , Thank You :)
The diagram itself is self explanatory
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);
}
}
thanks bete
good explanation
Its giving segmentation fault in GFG ! please update sir
mast sir
Thank you
nice explanations
clean
Thank you sir:)
What is the time complexity ? O(L) or O(N)
O(n)
Sir can u solve same problem in O(n)
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.
thanx sir
Great!
Thank u sir
Won't the space complexity increase due to this
No its the standard one so dont worry
how this is different from BFS?
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.
The best
helpful .... :)
spiral and zig-zag traversal are not same.
Nice
Rather than explaining the steps it would be better to say why we are doing it
sir can u please explain the full running code for rubik's cube ... i need it.
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;
}
Only one test case passed at gfg
If anyone is submitting in geeksforgeeks then this is the vALID SOLUTION FOR IT.
ide.codingblocks.com/s/97585
don't use it guyes,its giving TLE
Great explanation! Thank you so much!
Thank you