Printing Spiral Order Traversal of Binary Tree
Spiral Order Traversal of Binary Tree in Java
Given a Tree and we need to print the spiral order traversal of the given tree. By spiral Order Traversal We mean that alternate levels should be printed in alternate order .
Example – Level 0 to be printed left to right
Level 1 from right to left, and so on.
Spiral Order Traversal of Binary Tree In C
Algorithm :
- Create a Boolean variable flag which is used to change printing order of levels.
- If flag is 1then printGivenLevel() prints nodes from left to right else from right to left. Value of flag is flipped in each iteration to change the order.
- Function to print level order traversal :
- printSpiral(tree) set ltr to 0;
- Run a loop from 0 to height -1
- printGivenLevel(tree, d, flag);
- flag~= flag/*flip flag*/
- To print the nodes is :if tree is NULL then return;
- if level is 1, then print(tree->data);
- else if level greater than 1, then
- if(flag) printGivenLevel(tree->left, level-1, flag) and printGivenLevel(tree->right, level-1, flag);
- else printGivenLevel(tree->right, level-1, flag) and printGivenLevel(tree->left, level-1, flag);
Code in Java for Spiral Order Traversal
Run
import java.util.*;
class Node
{
int data;
Node left, right;
public Node(int item)
{
data = item;
left = right = null;
}
public Node()
{
data =0;
left = right = null;
}
}
// Binary tree Class
public class Main
{
static Node root;
void printSpiral(Node node)
{
// We will use a Queue and a Stack Here .
Queue queue = new LinkedList();
if(node == null) // Edge Case , when root is null
return;
boolean flag = false;
Stack straightPrint = new Stack();
Stack revPrint = new Stack ();
straightPrint.add(node);
while(!(straightPrint.isEmpty()) || !(revPrint.isEmpty())){
while(revPrint.size()>0){
Node temp = (Node)revPrint.pop();
System.out.print(temp.data +" ");
//Left to Right for next Level (Straight Level)
if(temp.left != null)
straightPrint.push(temp.left);
if(temp.right != null)
straightPrint.push(temp.right);
}
while(straightPrint.size() >0){
Node temp = (Node)straightPrint.pop();
System.out.print(temp.data +" ");
// Right To Left for next Level (Reverse Print )
if(temp.right != null)
revPrint.push(temp.right);
if(temp.left != null)
revPrint.push(temp.left);
}
}
}
public static void main(String[] args)
{
Main tree = new Main();
tree.root = new Node(1);
tree.root.left = new Node(5);
tree.root.right = new Node(4);
tree.root.left.left = new Node(9);
tree.root.left.right = new Node(7);
tree.root.right.left = new Node(10);
tree.root.right.right = new Node(13);
System.out.println("Spiral Order traversal of Binary Tree is ");
tree.printSpiral(root);
}
}
Output
Spiral Order traversal of Binary Tree is 1 5 4 13 10 7 9
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
Get over 200+ course One Subscription
Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others
Introduction to Trees
Binary Trees
- Binary Tree in Data Structures (Introduction)
- Tree Traversals: Inorder Postorder Preorder : C | C++ | Java
- Inorder Postorder PreOrder Traversals Examples
- Tree Traversal without Recursion
Binary Search Trees
Traversals
- Traversal in Trees
- Tree Traversals: Breadth-First Search (BFS) : C | C++ | Java
- Tree Traversals: Depth First Search (DFS) : C | C++ | Java
- Construct a Binary Tree from Postorder and Inorder
B – Trees
AVL Trees
- AVL Trees
Complete Programs for Trees
- Depth First Traversals – C | C++ | Java
- Level Order Traversal – C | C++ | Java
- Construct Tree from given Inorder and Preorder traversals – C | C++ | Java
- Construct Tree from given Postorder and Inorder traversals – C | C++ | Java
- Construct Tree from given Postorder and Preorder traversal – C | C++ | Java
- Find size of the Binary tree – C | C++ | Java
- Find the height of binary tree – C | C++ | Java
- Find maximum in binary tree – C | C++ | Java
- Check whether two tree are identical- C| C++| Java
- Spiral Order traversal of Tree- C | C++| Java
- Level Order Traversal Line by Line – C | C++| Java
- Hand shaking lemma and some Impotant Tree Properties.
- Check If binary tree if Foldable or not.- C| C++| Java
- check whether tree is Symmetric – C| C++| Java.
- Check for Children-Sum in Binary Tree- C|C++| Java
- Sum of all nodes in Binary Tree- C | C++ | Java
- Lowest Common Ancestor in Binary Tree- C | C++ | Java
Introduction to Trees
Binary Trees
- Binary Tree in Data Structures (Introduction)
- Tree Traversals: Inorder Postorder Preorder : C | C++ | Java
- Inorder Postorder PreOrder Traversals Examples
- Tree Traversal without Recursion
Binary Search Trees
Traversals
- Traversal in Trees
- Tree Traversals: Breadth-First Search (BFS) : C | C++ | Java
- Tree Traversals: Depth First Search (DFS) : C | C++ | Java
- Construct a Binary Tree from Postorder and Inorder
B – Trees
AVL Trees
- AVL Trees
Complete Programs for Trees
- Depth First Traversals – C | C++ | Java
- Level Order Traversal – C | C++ | Java
- Construct Tree from given Inorder and Preorder traversals – C | C++ | Java
- Construct Tree from given Postorder and Inorder traversals – C | C++ | Java
- Construct Tree from given Postorder and Preorder traversal – C | C++ | Java
- Find size of the Binary tree – C | C++ | Java
- Find the height of binary tree – C | C++ | Java
- Find maximum in binary tree – C | C++ | Java
- Check whether two tree are identical- C| C++| Java
- Spiral Order traversal of Tree- C | C++| Java
- Level Order Traversal LIne by Line – C | C++| Java
- Hand shaking lemma and some Impotant Tree Properties.
- Check If binary tree if Foldable or not.- C| C++| Java
- check whether tree is Symmetric C| C++| Java.
- Check for Children-Sum in Binary Tree- C|C++| Java
- Sum of all nodes in Binary Tree- C | C++ | Java
- Lowest Common Ancestor in Binary Tree. C | C++ | Java
