Spiral or Zigzag level order traversal of binary tree in java recursive

Approach A

Printing a binary tree in a spiral zigzag pattern involves performing a level-order traversal but alternating the order of traversal for each level. Specifically, you traverse the first level left-to-right, the next level right-to-left, and so on.

Java Code Implementation

Here’s how you can implement this in Java:

Define the structure of the binary tree.
Perform a spiral zigzag level-order traversal.

java

import java.util.*;

class TreeNode {

int data;

TreeNode left, right;

public TreeNode (int item) {

data = item;

left = right = null;

}

public class SpiralZigzagTree {

TreeNode root;

// Function to print nodes in spiral zigzag order

void printSpiral(TreeNode node) {

if (node == null) {

return;

}

// Create two stacks to store alternate levels

Stack< TreeNode > currentLevel = new Stack<>();

Stack< TreeNode > nextLevel = new Stack<>();

// Push the root node to the current level stack

currentLevel.push(node);

boolean leftToRight = true;

// Loop while any of the stacks have nodes

while (!currentLevel.isEmpty()) {

// Pop a node from the stack and print it

TreeNode temp = currentLevel.pop();

System.out.print(temp.data + " ");

// Store data according to the current order

if (leftToRight) {

if (temp.left != null) {

nextLevel.push(temp.left);

}

if (temp.right != null) {

nextLevel.push(temp.right);

}

} else {

if (temp.right != null) {

nextLevel.push(temp.right);

}

if (temp.left != null) {

nextLevel.push(temp.left);

}

// If the current level stack is empty, switch the order

// and swap the stacks

if (currentLevel.isEmpty()) {

leftToRight = !leftToRight;

Stack< TreeNode > tempStack = currentLevel;

currentLevel = nextLevel;

nextLevel = tempStack;

}

public static void main(String[] args) {

SpiralZigzagTree tree = new SpiralZigzagTree();

// Creating a binary tree

Node rootNode=createBinaryTree();

System.out.println("Spiral Zigzag Order traversal of binary tree is:");

tree.printSpiral(rootNode);

}

public static TreeNode createBinaryTree()

{

TreeNode rootNode =new TreeNode(1);

TreeNode node2=new TreeNode(2);

TreeNode node3=new TreeNode(3);

TreeNode node4=new TreeNode(4);

TreeNode node5=new TreeNode(5);

TreeNode node6=new TreeNode(6);

TreeNode node7=new TreeNode(7);

TreeNode node8=new TreeNode(8);

TreeNode node9=new TreeNode(9);

TreeNode node10=new TreeNode(10);

TreeNode node11=new TreeNode(11);

TreeNode node12=new TreeNode(12);

TreeNode node13=new TreeNode(13);

TreeNode node14=new TreeNode(14);

TreeNode node15=new TreeNode(15);

rootNode.left=node2;

rootNode.right=node3;

node2.left=node4;

node2.right=node5;

node3.left=node6;

node3.right=node7;

node4.left=node8;

node4.right=node9;

node5.right=node10;

node5.left=node11;

node6.left=node12;

node6.right=node13;

node7.right=node14;

node7.left=node15;

return rootNode;

}

Explanation

TreeNode Class:

Represents a node in the binary tree with data, left, and right fields.

printSpiral(TreeNode node):

Uses two stacks (currentLevel and nextLevel) to keep track of nodes at the current and next levels.
leftToRight flag to determine the direction of traversal for the current level.
Loops through nodes in currentLevel, printing them and pushing their children onto nextLevel in the appropriate order.
Switches the direction and stacks when currentLevel is empty.

main Method:

Constructs a sample binary tree using createBinaryTree method.
Calls printSpiral to print the tree in spiral zigzag order.

Output

For the provided binary tree, the output will be:

Output

Spiral Zigzag Order traversal of binary tree is:

1 2 3 7 6 5 4 8 9 10 11 12 13 14 15

Conclusion

This program effectively prints a binary tree in a spiral zigzag order using a level-order traversal with two stacks to manage the order of traversal for each level. Adjust the tree structure in the main method to test with different binary trees.

Approach B

To print a binary tree in a spiral zigzag pattern using a recursive approach, we need to:

Determine the height of the tree.
Print nodes at each level in alternating left-to-right and right-to-left order.

Here's how you can implement this:

Java Code Implementation

java

class TreeNode {

int data;

TreeNode left, right;

public TreeNode (int item) {

data = item;

left = right = null;

}

public class SpiralZigzagTreeRecursive {

TreeNode root;

// Function to print nodes in spiral zigzag order

void printSpiral(TreeNode node) {

int height = getHeight(node);

boolean leftToRight = false;

for (int i = 1; i <= height; i++) {

printLevel(node, i, leftToRight);

leftToRight = !leftToRight;

}

// Function to get the height of the tree

int getHeight(TreeNode node) {

if (node == null) {

return 0;

}

int leftHeight = getHeight(node.left);

int rightHeight = getHeight(node.right);

return Math.max(leftHeight, rightHeight) + 1;

}

// Function to print nodes at a given level

void printLevel(TreeNode node, int level, boolean leftToRight) {

if (node == null) {

return;

}

if (level == 1) {

System.out.print(node.data + " ");

} else if (level > 1) {

if (leftToRight) {

printLevel(node.left, level - 1, leftToRight);

printLevel(node.right, level - 1, leftToRight);

} else {

printLevel(node.right, level - 1, leftToRight);

printLevel(node.left, level - 1, leftToRight);

}

public static void main(String[] args) {

SpiralZigzagTreeRecursive tree = new SpiralZigzagTreeRecursive();

// Creating a binary tree

Node rootNode=createBinaryTree();

System.out.println("Spiral Zigzag Order traversal of binary tree is:");

tree.printSpiral(rootNode);

}

public static TreeNode createBinaryTree()

{

TreeNode rootNode =new TreeNode(1);

TreeNode node2=new TreeNode(2);

TreeNode node3=new TreeNode(3);

TreeNode node4=new TreeNode(4);

TreeNode node5=new TreeNode(5);

TreeNode node6=new TreeNode(6);

TreeNode node7=new TreeNode(7);

TreeNode node8=new TreeNode(8);

TreeNode node9=new TreeNode(9);

TreeNode node10=new TreeNode(10);

TreeNode node11=new TreeNode(11);

TreeNode node12=new TreeNode(12);

TreeNode node13=new TreeNode(13);

TreeNode node14=new TreeNode(14);

TreeNode node15=new TreeNode(15);

rootNode.left=node2;

rootNode.right=node3;

node2.left=node4;

node2.right=node5;

node3.left=node6;

node3.right=node7;

node4.left=node8;

node4.right=node9;

node5.right=node10;

node5.left=node11;

node6.left=node12;

node6.right=node13;

node7.right=node14;

node7.left=node15;

return rootNode;

}

Explanation

TreeNode Class:

Represents a node in the binary tree with data, left, and right fields.

printSpiral(TreeNode node):

Determines the height of the tree using the getHeight method.
Alternates the leftToRight flag for each level and calls printLevel for each level.

getHeight(TreeNode node):

Recursively calculates the height of the tree.

printLevel(TreeNode node, int level, boolean leftToRight):

Prints nodes at the given level in the specified order (left-to-right or right-to-left).
If the level is 1, it prints the node data.
If the level is greater than 1, it recursively calls itself for the left and right subtrees in the appropriate order based on the leftToRight flag.

main Method:

Constructs a sample binary tree using createBinaryTree method.
Calls printSpiral to print the tree in spiral zigzag order.

Output

For the provided binary tree, the output will be:

Spiral Zigzag Order traversal of binary tree is:

3 2

4 5 6 7

15 14 13 12 11 10 9 8

Conclusion

This program effectively prints a binary tree in a spiral zigzag order using a recursive approach. Adjust the tree structure in the main method to test with different binary trees. This implementation provides a clear demonstration of the recursive strategy for alternating level order traversal.