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