Lecture 179:-Zig-Zag Traversal

Zig-zag traversal, also known as the spiral traversal, of a binary tree involves traversing the tree in a zig-zag pattern, switching direction at each level. For example, you start at the root, then move to the right child, then to the left child of the right child, and so on. On the next level, you start at the left child, then move to the right child of the left child, and so on.

Here's a Python implementation of the zig-zag traversal of a binary tree:

pythonCopy code

class TreeNode: def __init__(self, data): self.data = data self.left = None self.right = None def zigzag_traversal(root): if root is None: return current_level = [root] reverse_order = False while current_level: next_level = [] for node in current_level: print(node.data, end=" ") if reverse_order: if node.left: next_level.append(node.left) if node.right: next_level.append(node.right) else: if node.right: next_level.append(node.right) if node.left: next_level.append(node.left) reverse_order = not reverse_order current_level = next_level print() # Example usage root = TreeNode(1) root.left = TreeNode(2) root.right = TreeNode(3) root.left.left = TreeNode(4) root.left.right = TreeNode(5) root.right.left = TreeNode(6) root.right.right = TreeNode(7) print("Zig-Zag Traversal:") zigzag_traversal(root)

In this example, the TreeNode class represents nodes of the binary tree. The zigzag_traversal function performs the zig-zag traversal of the binary tree. It uses two lists, current_level and next_level, to keep track of nodes in the current and next levels, respectively. The reverse_order variable is used to determine whether to reverse the order of child nodes at each level.

The zig-zag traversal starts with the root node. For each node in the current level, it prints the node's value and enqueues its child nodes in the appropriate order based on the reverse_order flag. After processing all nodes in the current level, it toggles the reverse_order flag and updates the current_level to the next_level for the next iteration.

This implementation correctly handles the zig-zag traversal of a binary tree and prints the nodes in the zig-zag pattern as described. Keep in mind that this traversal can be used to achieve a different order of visiting nodes compared to traditional traversals like in-order, pre-order, and post-order.