Given a binary tree, the task is to print its Print Level Order Traversal in Spiral, also known as zigzag traversal. The traversal should alternate between left-to-right and right-to-left for each level of the tree.
What is the difference between Level Order Traversal and Level Order Traversal in Spiral
-
Level Order Traversal: This is the traversal where you visit all nodes at a given level before moving to the next level. Typically, this is done from left to right.
-
Spiral or Zigzag Order Traversal: In spiral order traversal, nodes at odd levels are printed from left to right, and nodes at even levels are printed from right to left. This alternates for each level.
Code Flow for Print Level Order Traversal in Spiral
-
-
Two stacks are created:
-
leftToRightStack: Used to process nodes in left-to-right order. -
rightToLeftStack: Used to process nodes in right-to-left order.
-
-
The root node is pushed onto
leftToRightStack.
-
-
Outer Loop:
-
The
whileloop runs as long as at least one of the stacks (leftToRightStackorrightToLeftStack) is not empty. This ensures that the entire tree is processed.
-
-
Processing Left to Right:
-
The first
whileloop inside the outer loop processes nodes fromleftToRightStack:-
A node is popped from
leftToRightStackand its data is printed (prefixed with->). -
If the current node has a left child, it is pushed onto
rightToLeftStack. -
If the current node has a right child, it is pushed onto
rightToLeftStack.
-
-
-
Processing Right to Left:
-
The second
whileloop inside the outer loop processes nodes fromrightToLeftStack:-
A node is popped from
rightToLeftStackand its data is printed (prefixed with<-). -
If the current node has a right child, it is pushed onto
leftToRightStack. -
If the current node has a left child, it is pushed onto
leftToRightStack.
-
-
-
Spiral Order:
-
The nodes are processed in a zigzag pattern where:
-
First, nodes are printed from left to right.
-
Then, nodes are printed from right to left.
-
-
This alternates as you move down each level of the tree.
-
Let's see the code now
package org.wesome.dsalgo;
import lombok.Data;
import java.util.Objects;
import java.util.Stack;
public class BinaryTree {
Node root;
public void PrintInSpiral(Node node) {
/* if root is null, meaning the tree is empty */
if (Objects.isNull(root)) {
return;
}
/* Used to process nodes in left-to-right order. */
Stack<Node> leftToRightStack = new Stack<>();
/* Used to process nodes in right-to-left order. */
Stack<Node> rightToLeftStack = new Stack<>();
/* the root node will be printed from left to right, hence pushing in leftToRightStack Stack */
leftToRightStack.push(node);
/* The while loop runs as long as at least one of the stacks (leftToRightStack or rightToLeftStack) is not empty. This ensures that the entire tree is processed. */
while (!leftToRightStack.isEmpty() || !rightToLeftStack.isEmpty()) {
while (!leftToRightStack.isEmpty()) {
/* A node is popped from leftToRightStack and its data is printed. */
Node leftToRightNode = leftToRightStack.pop();
System.out.print(" -> " + leftToRightNode.data);
/* If the current node has a left child, it is pushed onto rightToLeftStack. */
if (Objects.nonNull(leftToRightNode.left)) {
rightToLeftStack.push(leftToRightNode.left);
}
/* If the current node has a right child, it is pushed onto rightToLeftStack. */
if (Objects.nonNull(leftToRightNode.right)) {
rightToLeftStack.push(leftToRightNode.right);
}
}
System.out.println();
while (!rightToLeftStack.isEmpty()) {
Node rightToLeftNode = rightToLeftStack.pop();
System.out.print(rightToLeftNode.data + " <- ");
/* If the current node has a right child, it is pushed onto leftToRightStack. */
if (Objects.nonNull(rightToLeftNode.right)) {
leftToRightStack.push(rightToLeftNode.right);
}
/* If the current node has a left child, it is pushed onto leftToRightStack. */
if (Objects.nonNull(rightToLeftNode.left)) {
leftToRightStack.push(rightToLeftNode.left);
}
}
System.out.println();
}
}
void insert(int data) {
System.out.println("BinarySearchTree.insert data = " + data);
root = insert(root, data);
}
Node insert(Node root, int data) {
if (Objects.isNull(root)) {
Node tempNode = new Node(data);
return tempNode;
}
if (data > root.data) {
root.right = insert(root.right, data);
} else {
root.left = insert(root.left, data);
}
return root;
}
}
@Data
class Node {
int data;
Node left, right;
public Node(int data) {
this.data = data;
left = right = null;
}
}
package org.wesome.dsalgo;
import org.junit.jupiter.api.Test;
public class BinaryTest {
@Test
void testEmptyTree() {
// Test for an empty tree (null root)
BinaryTree tree = new BinaryTree();
tree.PrintInSpiral(null);
}
@Test
void testSingleNodeTree() {
// Test for a tree with a single node
BinaryTree tree = new BinaryTree();
tree.insert(10);
tree.PrintInSpiral(tree.root);
}
@Test
void testBalancedBinaryTree() {
// Test for a balanced binary tree
BinaryTree tree = new BinaryTree();
tree.insert(10);
tree.insert(5);
tree.insert(15);
tree.insert(2);
tree.insert(7);
tree.insert(12);
tree.insert(18);
tree.PrintInSpiral(tree.root);
}
@Test
void testUnbalancedBinaryTree() {
// Test for an unbalanced binary tree (sorted order insertion creating a right-skewed tree)
BinaryTree tree = new BinaryTree();
tree.insert(10);
tree.insert(20);
tree.insert(30);
tree.insert(40);
tree.insert(50);
tree.PrintInSpiral(tree.root);
}
@Test
void testTreeWithNegativeValues() {
// Test for a tree with negative values
BinaryTree tree = new BinaryTree();
tree.insert(-5);
tree.insert(-3);
tree.insert(-2);
tree.insert(-1);
tree.insert(-7);
tree.insert(-4);
tree.PrintInSpiral(tree.root);
}
@Test
void testLargeTree() {
// Test for a large tree with many nodes
BinaryTree tree = new BinaryTree();
for (int i = 1; i <= 1000; i++) {
tree.insert(i);
}
tree.PrintInSpiral(tree.root);
}
@Test
void testRightSkewedTree() {
// Constructing the following tree:
// 10
// \
// 20
// \
// 30
// \
// 40
// \
// 50
BinaryTree tree = new BinaryTree();
Node root = new Node(10);
root.right = new Node(20);
root.right.right = new Node(30);
root.right.right.right = new Node(40);
root.right.right.right.right = new Node(50);
tree.PrintInSpiral(root);
}
@Test
void testTreeWithDuplicateValues() {
// Constructing the following tree:
// 1
// / \
// 1 1
// / \ / \
// 1 1 1 1
BinaryTree tree = new BinaryTree();
Node root = new Node(1);
root.left = new Node(1);
root.right = new Node(1);
root.left.left = new Node(1);
root.left.right = new Node(1);
root.right.left = new Node(1);
root.right.right = new Node(1);
tree.PrintInSpiral(root);
}
@Test
void testTreeBinaryTreeValues() {
// Constructing the following tree:
// 1
// / \
// 2 3
// / \
// 4 5
BinaryTree tree = new BinaryTree();
Node root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.left.left = new Node(4);
root.left.right = new Node(5);
tree.PrintInSpiral(root);
}
}
plugins {
id("java")
id("io.freefair.lombok") version "8.13"
}
group = "org.wesome.dsalgo"
version = "1.0-SNAPSHOT"
repositories {
mavenCentral()
}
dependencies {
testImplementation(platform("org.junit:junit-bom:5.10.0"))
testImplementation("org.junit.jupiter:junit-jupiter")
}
tasks.test {
useJUnitPlatform()
}Complexity Analysis
Time Complexity
-
Time Complexity: O(N), where N is the number of nodes in the tree
Space Complexity
- Space Complexity: O(N), where N is the number of nodes in the tree, due to the use of stacks to store nodes at each level.
