Java Binary Tree Spiral Level Traversal

Chapter: Interview Programs Last Updated: 04-11-2016 15:27:23 UTC

Program:

            /* ............... START ............... */
                
import java.util.Queue;
import java.util.Stack;
import java.util.LinkedList;

public class JavaBinaryTreeSpiralLevelTraversal {

	public static class TreeNode {
		int data;
		TreeNode left;
		TreeNode right;

		TreeNode(int data) {
			this.data = data;
		}
	}

	public static void spiralOrZigzagLevelOrder(TreeNode root) {
		if (root == null)
			return;
		Stack<TreeNode> stack = new Stack<TreeNode>();
		stack.push(root);

		boolean directionflag = false;
		while (!stack.isEmpty()) {
			Stack<TreeNode> tempStack = new Stack<TreeNode>();

			while (!stack.isEmpty()) {
				TreeNode tempNode = stack.pop();
				System.out.printf("%d ", tempNode.data);
				if (!directionflag) {
					if (tempNode.left != null)
						tempStack.push(tempNode.left);
					if (tempNode.right != null)
						tempStack.push(tempNode.right);
				} else {
					if (tempNode.right != null)
						tempStack.push(tempNode.right);
					if (tempNode.left != null)
						tempStack.push(tempNode.left);
				}
			}
			// for changing direction
			directionflag = !directionflag;

			stack = tempStack;
		}

	}

	public static void main(String[] args) {
		JavaBinaryTreeSpiralLevelTraversal bi = new JavaBinaryTreeSpiralLevelTraversal();
		// Creating a binary tree
		TreeNode rootNode = createBinaryTree();
		System.out.println("Spiral/Zigzag traversal of binary tree :");
		spiralOrZigzagLevelOrder(rootNode);
	}

	public static TreeNode createBinaryTree() {

		TreeNode rootNode = new TreeNode(40);
		TreeNode node20 = new TreeNode(20);
		TreeNode node10 = new TreeNode(10);
		TreeNode node30 = new TreeNode(30);
		TreeNode node60 = new TreeNode(60);
		TreeNode node50 = new TreeNode(50);
		TreeNode node70 = new TreeNode(70);
		TreeNode node5 = new TreeNode(5);
		TreeNode node55 = new TreeNode(55);

		rootNode.left = node20;
		rootNode.right = node60;

		node20.left = node10;
		node20.right = node30;

		node60.left = node50;
		node60.right = node70;
		node10.left = node5;
		node50.right = node55;

		return rootNode;
	}
}
                /* ............... END ............... */
        

Output

Spiral/Zigzag traversal of binary tree :
40 60 20 10 30 50 70 55 5 

Notes:

  • Steps for solution:
  • Create an empty stack s and push root to it.
  • while stack is not NULL Do following
  • Create a empty stack called tempStack.
  • Pop a node from stack and push it to tempStack depending on directionFlag
  • Change directionFlag to change the direction of traversal
  • set stack=tempStack

Tags

Binary Tree Spiral Level Traversal, Java, Interview Programs

Similar Programs Chapter Last Updated
Java Program To Find Frequency Of Character In String Interview Programs 28-09-2017
Java Program To Find Power Of Number Using While Loop Interview Programs 30-08-2017
Java Program To Count Divisors Of Integer Number Interview Programs 24-06-2017
Java Program To Sort N Names In Ascending Order Interview Programs 24-06-2017
Java Program To Count Total Number Of Words In String Interview Programs 24-06-2017
Java Program To Print All Prime Numbers From 1 to N Interview Programs 24-06-2017
Java Program To Extract Digits / Numbers From String Interview Programs 22-09-2018
Java First Repeated Character In String Interview Programs 16-05-2017
Java String Character Repetition Count Interview Programs 15-05-2017
Java Program To Check Vowel Or Not Interview Programs 25-09-2018
Java Program To Check Alphabet Or Not Interview Programs 06-04-2017
Java Program To Find First Repeated And Non Repeated Character In String Interview Programs 25-03-2017
Java Spiral Matrix Interview Programs 22-09-2018
Java Program To Reverse A Number Using Strings Interview Programs 13-02-2017
Java Program To Print Diamond Star Pattern Interview Programs 16-12-2016
Java Program To Print Pyramid Pattern Of Star Interview Programs 16-12-2016
Java Program To Find Second Largest Number In Array Interview Programs 04-12-2016
Java Depth First Search Interview Programs 04-12-2016
Java Breadth First Search Interview Programs 04-12-2016
Java Linked List Length Recursive Solution Interview Programs 17-11-2016
Java Linked List Length Iterative Solution Interview Programs 17-11-2016
Java Linked List Node Deletion At Given Position Interview Programs 17-11-2016
Java Linked List Node Delete Interview Programs 17-11-2016
Java Sum Of Digits Using Recursion Interview Programs 06-11-2016
Java Program To Reverse Vowels Of String Interview Programs 05-11-2016
Java Program To Remove Vowels From String Interview Programs 05-11-2016
Java Find Top Two Maximum Numbers In Array Interview Programs 05-11-2016
Java QuickSort Example Interview Programs 05-11-2016
Java Binary Tree Preorder Traversal Interview Programs 04-11-2016
Java Binary Tree InOrder Traversal Interview Programs 31-10-2016

1 2 3 4 5