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: 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.
0 Comments