Level Order Traversal in Zig Zag pattern

To implement a recursive solution for the Zig Zag Level Order Traversal in Java, we can use a depth-first approach where we keep track of the current level and add nodes to the result in a zigzag pattern. This approach involves maintaining a list of lists, where each list corresponds to a level in the binary tree. We alternate the order of insertion for each level.

Zig Zag Level Order Traversal (Iteration) Implementation

import java.util.*;

class Node<T> {

T data;

Node<T> left, right;

Node(T item) {

data = item;

left = right = null;

}

public class ZigZagTraversal {

public static <T> List<List<T>> zigzagLevelOrder(Node<T> root) {

List<List<T>> result = new ArrayList<>();

if (root == null) {

return result;

}

Deque<Node<T>> currentLevel = new ArrayDeque<>();

currentLevel.offer(root);

boolean leftToRight = true;

while (!currentLevel.isEmpty()) {

int size = currentLevel.size();

List<T> currentLevelResult = new ArrayList<>(size);

Deque<Node<T>> nextLevel = new ArrayDeque<>();

for (int i = 0; i < size; i++) {

Node<T> currentNode;

if (leftToRight) {

currentNode = currentLevel.pollFirst();

currentLevelResult.add(currentNode.data);

if (currentNode.left != null) {

nextLevel.offerLast(currentNode.left);

}

if (currentNode.right != null) {

nextLevel.offerLast(currentNode.right);

}

} else {

currentNode = currentLevel.pollLast();

currentLevelResult.add(currentNode.data);

if (currentNode.right != null) {

nextLevel.offerFirst(currentNode.right);

}

if (currentNode.left != null) {

nextLevel.offerFirst(currentNode.left);

}

result.add(currentLevelResult);

currentLevel = nextLevel;

leftToRight = !leftToRight; // Toggle direction

}

return result;

}

public static void main(String[] args) {

Node<Integer> 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);

root.right.left = new Node<>(6);

root.right.right = new Node<>(7);

List<List<Integer>> result = zigzagLevelOrder(root);

System.out.println("Zigzag Level Order Traversal:");

for (List<Integer> level : result) {

System.out.println(level);

}

Explanation

Node Class: A simple Node class to represent nodes in the binary tree, where each node contains data and references to left and right child nodes.
zigzagLevelOrder Method:

The method returns a list of lists where each sublist contains the nodes at a particular level, traversed in the zigzag pattern.
A Deque (double-ended queue) is used to allow efficient removal from both ends depending on the current direction of traversal.
The method toggles the direction (left to right or right to left) after processing each level.

Traversal Logic:

If traversing from left to right:

Nodes are removed from the front of the queue.
Children are added to the end of the queue.

If traversing from right to left:

Nodes are removed from the back of the queue.
Children are added to the front of the queue.

Zig Zag Level Order Traversal (Recursive) Implementation

Here’s how you can implement the Zig Zag Level Order Traversal recursively:

java

import java.util.*;

class Node<T> {

T data;

Node<T> left, right;

Node(T item) {

data = item;

left = right = null;

}

public class ZigZagTraversalRecursive {

public static <T> List<List<T>> zigzagLevelOrder(Node<T> root) {

List<List<T>> result = new ArrayList<>();

zigzagLevelOrderHelper(root, result, 0);

return result;

}

private static <T> void zigzagLevelOrderHelper(Node<T> node, List<List<T>> result, int level) {

if (node == null) {

return;

}

// Ensure the result list has a sublist for the current level

if (level >= result.size()) {

result.add(new LinkedList<>()); // Using LinkedList to efficiently add at the beginning

}

// Add the current node's value to the list at this level

if (level % 2 == 0) {

// Even level, add to the end (left-to-right)

result.get(level).add(node.data);

} else {

// Odd level, add to the beginning (right-to-left)

result.get(level).add(0, node.data);

}

// Recur for left and right children

zigzagLevelOrderHelper(node.left, result, level + 1);

zigzagLevelOrderHelper(node.right, result, level + 1);

}

public static void main(String[] args) {

Node<Integer> 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);

root.right.left = new Node<>(6);

root.right.right = new Node<>(7);

List<List<Integer>> result = zigzagLevelOrder(root);

System.out.println("Zigzag Level Order Traversal (Recursive):");

for (List<Integer> level : result) {

System.out.println(level);

}

Explanation

Node Class: The Node class represents each node in the binary tree, holding the data and pointers to the left and right children.
zigzagLevelOrder Method:

This is the main method that initializes the result list and calls the helper method zigzagLevelOrderHelper to perform the traversal.

zigzagLevelOrderHelper Method:

Base Case: If the current node is null, the recursion stops.
Current Level Handling:

If the level is even, it adds the node's data to the end of the list corresponding to that level.
If the level is odd, it adds the node's data to the beginning of the list for that level (to achieve the right-to-left order).

Recursive Calls: The method recursively processes the left and right subtrees, increasing the level by 1 for each recursive call.

Example Output

For the tree:

text

/ \

2 3

/ \ / \

4 5 6 7

The Zig Zag Level Order Traversal output will be:

text

Zigzag Level Order Traversal (Recursive):

[1]

[3, 2]

[4, 5, 6, 7]

Summary

This recursive solution efficiently handles the Zig Zag Level Order Traversal by leveraging the recursive depth-first search (DFS) approach. It alternates between adding elements to the front and the back of each level's list based on whether the level is odd or even, respectively. This ensures that the zigzag pattern is maintained throughout the traversal.