Spiral or Zigzag binary tree traversal in java (BFS & example)

Yogesh

9 years ago

Given a binary tree, print the binary tree in spiral or zig-zag order using breadth first search (BFS) algorithm.
In level order traversal or BFS, we are traversing the binary tree breadth wise.
The brief algorithm is as follows:
- Traverse the binary tree, level by level.
- At each level, traverse siblings from left to right or right to left

In spiral binary tree traversal, we need to traverse left to right at one level and right to left at subsequent level. The alternate flow at each level will result in spiral or zigzag traversal of a binary tree. The level order traversal or BFS of binary tree shown in Fig 1 is as follows:
40 60 70 25 80 65 51

Algorithm – traverse binary tree in spiral or zigzag order using java

Create two stacks, One to traverse left to right and another to traverse right to left.
Add root to stackOne.
Visit the next level i.e. Level 1.
- Iterate through stackOne.
  - Print elements of stackOne.
  - Add right child to stackTwo.
  - Add left child to stackTwo.
Visit the next level i.e. Level 2, Iterate through stackTwo.
- Print elements of stackTwo.
- Add left child to stackOne.
- Add right child to stackOne
At the end of traversal we will get spiral or zig-zag output.

The Spiral traversal of above tree is (following the red arrow 1 -> 2 -> 3 -> 4)
40 50 70 51 65 80 25

Program – print binary tree in spiral or zigzag order (BFS) using java

1.) SpiralTraversal Class:

SpiralTraversal class is responsible for printing the binary tree in spiral or zigzag order using breadth first search algorithm.

package org.learn.Question;

import java.util.Stack;

public class SpiralTraversal {

	public static void spiralTraversal(Node root) {
		if (root == null) {
			System.out.println("Tree is empty");
			return;
		}

		Stack<Node> stackOne = new Stack<Node>();
		Stack<Node> stackTwo = new Stack<Node>();
		stackOne.push(root);
		while (!stackOne.isEmpty() || !stackTwo.isEmpty()) {
			// insert right to left in stack
			while (!stackOne.isEmpty()) {
				Node node = stackOne.pop();
				System.out.printf("%d ", node.data);
				if (node.right != null) {
					stackTwo.push(node.right);
				}
				if (node.left != null) {
					stackTwo.push(node.left);
				}
			}
			System.out.println("");
			// insert left to right in stack
			while (!stackTwo.isEmpty()) {
				Node node = stackTwo.pop();
				System.out.printf("%d ", node.data);
				if (node.left != null) {
					stackOne.push(node.left);
				}
				if (node.right != null) {
					stackOne.push(node.right);
				}
			}
			System.out.println("");
		}
	}
}

2.) Node class:

Node class representing the Nodes of a binary tree.

package org.learn.Question;

public class Node {
	public int data;
	public Node left;
	public Node right;

	public Node(int num) {
		this.data = num;
		this.left = null;
		this.right = null;
	}

	public Node() {
		this.left = null;
		this.right = null;
	}
	public static Node createNode(int number) {
		return new Node(number);
	}
}

3.) App Class:

We are constructing the binary tree in main method
Print binary tree in spiral or zig-zag order using level order traversal algorithm.

package org.learn.Client;

import org.learn.Question.Node;
import org.learn.Question.SpiralTraversal;

public class App {
	public static void main(String[] args) {
		// root level 0
		Node A = Node.createNode(0);
		// Level 1
		Node B = Node.createNode(50);
		Node C = Node.createNode(70);
		// Level 2
		Node D = Node.createNode(25);
		Node E = Node.createNode(80);
		Node F = Node.createNode(65);
		Node G = Node.createNode(51);

		// connect Level 0 and 1
		A.left = B;
		A.right = C;
		// connect level 1 and level 2
		B.left = D;
		B.right = E;
		C.left = F;
		C.right = G;

		System.out.println("Spiral tree traversal using DFS:");
		SpiralTraversal.spiralTraversal(A);
	}
}

Output- spiral or zigzag traversal order (BFS) using java

Spiral tree traversal using BFS:
100
50 150
160 125 80 25