# Level order traversal of a binary tree in spiral form in Java

A Binary tree is a special form of the general tree where each node has at most two children, that are left and right child.

Look at the example of the binary tree shown below.

In the above example, we have a binary tree with 7 nodes. Node A is the root node, and nodes D, E, F and G are the leaf node.

## Level order traversal

Level order traversal in the binary tree is traversing through the node in a fixed pattern. In level-order traversal, first, we visit the root node and then keep on traversing from the left node to the right node till the end of the tree. For a normal level order traversal, the output would be A, B, C, D, E, F and G.

## Spiral form

In the spiral form, the nodes are traversed in an alternate pattern. First, we traversed from the left node to the right node, then from the right node to the left node, which goes on till the end of the tree.

In Spiral form, beginning from level 0 (Root node), the nodes from the even level are traversed from right to left node and for the odd level, we traverse from left to right node.

Let us go through some examples given below

**Example1**

**Output:**

1 2 3 7 6 5 4

**Explanation**:

Level 0: 1

Level 1: 2 3

Level2: 4 5 6 7

Here, the nodes are first visited from left to right to right and the right to left, giving the output as 1 2 3 7 6 5 4.

**Example2**

**Output:**

2 7 5 9 6 2 5 11 4

**Explanation**:

Level 0: 2

Level 1: 7 5

Level2: 2 6 9

Level3: 5 11 4

Here, the nodes are first visited from left to right and then right to left, giving the output as 2 7 5 9 6 2 5 11 4.

## Using Recursion

The first approach for level order traversal in spiral form involves recursion. The basic principle in this approach would be to find the height of the binary tree and then use recursion for traversing each level and display the nodes as per the current level.

### Algorithm

Step 1: Create variable **height **and **i**. The variable **height** is used to store the height of the binary tree, and variable **i** is used for traversing in the for loop.

Step 2: Initialize variable **leftToRight** as false. It Identifies if the current level should be traversed from left to right node or right to left node.

Step 3: Initialize a for loop from **1** to **height**.

Step 4: Display the level order traversal in spiral form using the **printNodesAtLevel (node, level, leftToRight)** recursive function.

1. If the node is null, then return

2. If the **level **is equal to 1, then print the node data.

3. If the **level** is greater than 1

a. If **leftToRight** is true, call the function **printNodesAtLevel **recursively, which will print the nodes in the order left to the right node.

b. If **leftToRight** is false, call the function **printNodesAtLevel **recursively, which will print the nodes in the order right to the left node.

Step5: Update **leftToRight = !leftToRight**. It will change the traversal direction for the next level

**FileName: **SprialBinaryTree.java

// Java program to demonstrate level order traversal // in spiral form using recursion // Node class for representing the node and its children class Node { int data; Node left; Node right; public Node(int d) { data = d; left = null; right = null; } } class SprialBinaryTree { Node root; // method to display level order traversal // in spiral form void displaySpiralForm(Node node) { int height = getHeight(node); int i; // Identifies if the current level // should be traversed from the left node to the right node // or right node to left node boolean leftToRight = false; for (i = 1; i <= height; i++) { printNodesAtLevel(node, i, leftToRight); // Change the traversal direction for the next level leftToRight = !leftToRight; } } //Compute the height of the given binary tree int getHeight(Node node) { if (node == null) return 0; else { // find the height of both right and left subtree int leftHeight = getHeight(node.left); int rightHeight = getHeight(node.right); // return the maximum among both the subtrees if (leftHeight > rightHeight) // +1 to count for the current level return (leftHeight + 1); else return (rightHeight + 1); } } // method to display nodes at the given level void printNodesAtLevel(Node node, int level, boolean leftToRight) { if (node == null) return; if (level == 1) System.out.print(node.data + " "); else if (level > 1) { if (leftToRight != false) { printNodesAtLevel(node.left, level - 1, leftToRight); printNodesAtLevel(node.right, level - 1, leftToRight); } else { printNodesAtLevel(node.right, level - 1, leftToRight); printNodesAtLevel(node.left, level - 1, leftToRight); } } } // main method public static void main(String[] args) { SprialBinaryTree tree = new SprialBinaryTree(); tree.root = new Node(1); tree.root.left = new Node(2); tree.root.right = new Node(3); tree.root.left.left = new Node(4); tree.root.left.right = new Node(5); tree.root.right.left = new Node(6); tree.root.right.right = new Node(7); System.out.println("Level order traversal of binary tree in spiral form is "); tree.displaySpiralForm(tree.root); } }

**Output:**

Level order traversal of binary tree in spiral form is 1 2 3 7 6 5 4

**Time complexity:**

O(n^2). Here, n is the count of the nodes.

**Space complexity:**

O(n). It is due to the recursion function stack.

## Using Stacks

In this approach for level order traversal in spiral form, we use two stacks. The basic idea for this approach is to use two stacks for the level order traversal that will maintain the alternate order.

## Algorithm

Step 1: Declare two stacks, **stack1** and **stack2,** for storing the nodes in alternate levels.

Step 2: Push the first level, i.e. root node in the **stack1**.

Step 3: Create a while loop that will traverse until one of **stack1** or **stack2** is non-empty.

Step 4: Inside the while loop:

a. Create a nested while loop till **stack1 **is non-empty

- Pop the node from
**stack1**and print the data. - Push the right and left child of the node, given that they exist in
**stack2,**beginning from the right and then the left child.

b. Create a nested while loop till **stack2 **is non-empty

- Pop the node from
**stack2**and print the data. - Push the right and left child of the node, given that they exist in
**stack1**beginning from the left and then the right child

**FileName: **SprialBinaryTree1.java

// Java program for level order traversal // in spiral form using two stacks import java.util.*; // Node class for representing the node and its children class Node { int data; Node left; Node right; public Node(int d) { data = d; left = null; right = null; } } public class SpiralBinaryTree1 { static Node root; // method to display level order traversal // in spiral form void displaySpiralForm(Node node) { if (node == null) return; // Declare 2 stacks for storing the alternate levels // for right node to left node Stackstack1 = new Stack (); // for the left node to the right node Stack stack2 = new Stack (); // Push the first level, i.e. root node stack1.push(node); //Keep traversing till one of the stack1 is empty while (!stack1.empty() || !stack2.empty()) { // till stack1 is not empty, pop a node from stack1 and display it // and then push its children in stack2 while (!stack1.empty()) { Node temp = stack1.peek(); stack1.pop(); System.out.print(temp.data + " "); if (temp.right != null) stack2.push(temp.right); if (temp.left != null) stack2.push(temp.left); } // till stack2 is not empty, pop a node from stack2 and display it // and then push its children in stack1 while (!stack2.empty()) { Node temp = stack2.peek(); stack2.pop(); System.out.print(temp.data + " "); if (temp.left != null) stack1.push(temp.left); if (temp.right != null) stack1.push(temp.right); } } } // main method public static void main(String[] args) { SpiralBinaryTree1 tree = new SpiralBinaryTree1(); tree.root = new Node(1); tree.root.left = new Node(2); tree.root.right = new Node(3); tree.root.left.left = new Node(4); tree.root.left.right = new Node(5); tree.root.right.left = new Node(6); tree.root.right.right = new Node(7); System.out.println("Level order traversal of binary tree in spiral form is "); tree.displaySpiralForm(root); } }

**Output:**

Level order traversal of binary tree in spiral form is 1 2 3 7 6 5 4

**Time complexity:**

O(n), where n is the number of the nodes. It is because each node is traversed through only once.

**Space complexity:**

O(n). It is because we are storing the nodes in the stacks.

## Using Deque

In this approach for level order traversal in spiral form, we use Deque (Doubly ended queue. The basic idea for this approach is to use deque to push and pop the nodes from both ends in an alternate pattern.

### Algorithm

Step 1: Create a Deque **deque**.

Step 2: Add the root of the binary tree in the **deque**.

Step 3: Initialize a Boolean variable **direction = true**. It Identifies if the current level should be traversed from the left node to the right node or the right node to the left node

Step 4: Create a while loop that will keep on traversing till the **deque** is empty

Step 5: Inside the while loop:

Initialize variable **size **that will store the current size of the deque.

a. If **direction == false**

- Create a nested while loop till
**size**> 0

- Decrement the
**size**by 1 - Add the child from the back of the deque, given that they exist starting from the left child and then the right child.Print the current node.
- Change
**direction = !direction**.

b. **Else**

- Create a nested while loop till
**size**> 0

- Decrement the
**size**by 1 - Add the child from the front of the deque, given that they exist starting from the right child and then the left child.
- Print the current node.
- Change
**direction = !direction**.

**FileName:** SpiralBinaryTree2.java

// Java program for level order traversal // in spiral form using Doubly ended queue import java.util.ArrayDeque; import java.util.Deque; public class SpiralBinaryTree2 { // Node class for representing the node and its children static class Node { int key; Node left; Node right; public Node(int key) { this.key = key; } } static class BinaryTree { public BinaryTree(){ }; public Node root; } // method to display level order traversal // in spiral form public static void displaySpiralForm(Node root) { // Create a Deque Dequedeque = new ArrayDeque<>(); // Add the root of the tree in deque deque.offer(root); // Identifies if the current level // should be traversed from the left node to the right node // or right node to left node boolean direction = true; while (!deque.isEmpty()) { // get the current size of deque int size = deque.size(); if (!direction) { // Traverse from left to right while (size-- > 0) { // Add the child from the back of the deque // Starting from the left child and then the right child if (deque.peekFirst().left != null) deque.offerLast(deque.peekFirst().left); if (deque.peekFirst().right != null) deque.offerLast(deque.peekFirst().right); // display the current node System.out.print(deque.pollFirst().key + " "); } // Change the traversal direction direction = !direction; } else { // Add the child from the front of the deque // Starting from the right child and then the left child while (size-- > 0) { // Insert the child in the front of the deque // Right child first if (deque.peekLast().right != null) deque.offerFirst(deque.peekLast().right); if (deque.peekLast().left != null) deque.offerFirst(deque.peekLast().left); // display the current node System.out.print(deque.pollLast().key + " "); } // Change the traversal direction direction = !direction; } } } // main method public static void main(String[] args) { BinaryTree tree = new BinaryTree(); tree.root = new Node(1); tree.root.left = new Node(2); tree.root.right = new Node(3); tree.root.left.left = new Node(4); tree.root.left.right = new Node(5); tree.root.right.left = new Node(6); tree.root.right.right = new Node(7); System.out.println("Level order traversal of binary tree in the spiral form is "); displaySpiralForm(tree.root); } }

**Output:**

Level order traversal of binary tree in the spiral form is 1 2 3 7 6 5 4

**Time complexity:**

O(n).

**Space complexity:**

O(n). It is because we are placing nodes in the deque.