# 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

Stack stack1 = 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

1. 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

Deque deque = 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.