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