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