Header Ads Widget

Responsive Advertisement

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:

  1. Define the structure of the binary tree.
  2. 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

  1. TreeNode Class:
    • Represents a node in the binary tree with data, left, and right fields.
  2. 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.
  3. 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:

  1. Determine the height of the tree.
  2. 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

  1. TreeNode Class:
    • Represents a node in the binary tree with data, left, and right fields.
  2. 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.
  3. getHeight(TreeNode node):
    • Recursively calculates the height of the tree.
  4. 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.
  5. 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:

1

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.

 




Spiral or Zigzag level order traversal of binary tree
Spiral or Zigzag level order traversal of binary tree









Post a Comment

0 Comments