Write a function to print ZigZag order traversal of a binary tree. For the below binary tree the zigzag order traversal will be 1 3 2 7 6 5 4
This problem can be solved using two stacks. Assume the two stacks are current: currentlevel and nextlevel. We would also need a variable to keep track of the current level order(whether it is left to right or right to left). We pop from the currentlevel stack and print the nodes value. Whenever the current level order is from left to right, push the nodes left child, then its right child to the stack nextlevel. Since a stack is a LIFO(Last-In-First_out) structure, next time when nodes are popped off nextlevel, it will be in the reverse order. On the other hand, when the current level order is from right to left, we would push the nodes right child first, then its left child. Finally, do-not forget to swap those two stacks at the end of each level(i.e., when current level is empty)
Below is the implementation of the above approach:
C++
// C++ implementation of a O(n) time method for // Zigzag order traversal #include <iostream> #include <stack> using namespace std; // Binary Tree node struct Node { int data; struct Node *left, *right; }; // function to print the zigzag traversal void zizagtraversal(struct Node* root) { // if null then return if (!root) return; // declare two stacks stack<struct Node*> currentlevel; stack<struct Node*> nextlevel; // push the root currentlevel.push(root); // check if stack is empty bool lefttoright = true; while (!currentlevel.empty()) { // pop out of stack struct Node* temp = currentlevel.top(); currentlevel.pop(); // if not null if (temp) { // print the data in it cout << temp->data << " "; // store data according to current // order. if (lefttoright) { if (temp->left) nextlevel.push(temp->left); if (temp->right) nextlevel.push(temp->right); } else { if (temp->right) nextlevel.push(temp->right); if (temp->left) nextlevel.push(temp->left); } } if (currentlevel.empty()) { lefttoright = !lefttoright; swap(currentlevel, nextlevel); } } } // A utility function to create a new node struct Node* newNode(int data) { struct Node* node = new struct Node; node->data = data; node->left = node->right = NULL; return (node); } // driver program to test the above function int main() { // create tree struct Node* root = newNode(1); root->left = newNode(2); root->right = newNode(3); root->left->left = newNode(7); root->left->right = newNode(6); root->right->left = newNode(5); root->right->right = newNode(4); cout << "ZigZag Order traversal of binary tree is
"; zizagtraversal(root); return 0; } |
Java
// Java implementation of a O(n) time // method for Zigzag order traversal import java.util.*; // Binary Tree node class Node { int data; Node leftChild; Node rightChild; Node(int data) { this.data = data; } } class BinaryTree { Node rootNode; // function to print the // zigzag traversal void printZigZagTraversal() { // if null then return if (rootNode == null) { return; } // declare two stacks Stack<Node> currentLevel = new Stack<>(); Stack<Node> nextLevel = new Stack<>(); // push the root currentLevel.push(rootNode); boolean leftToRight = true; // check if stack is empty while (!currentLevel.isEmpty()) { // pop out of stack Node node = currentLevel.pop(); // print the data in it System.out.print(node.data + " "); // store data according to current // order. if (leftToRight) { if (node.leftChild != null) { nextLevel.push(node.leftChild); } if (node.rightChild != null) { nextLevel.push(node.rightChild); } } else { if (node.rightChild != null) { nextLevel.push(node.rightChild); } if (node.leftChild != null) { nextLevel.push(node.leftChild); } } if (currentLevel.isEmpty()) { leftToRight = !leftToRight; Stack<Node> temp = currentLevel; currentLevel = nextLevel; nextLevel = temp; } } } } public class zigZagTreeTraversal { // driver program to test the above function public static void main(String[] args) { BinaryTree tree = new BinaryTree(); tree.rootNode = new Node(1); tree.rootNode.leftChild = new Node(2); tree.rootNode.rightChild = new Node(3); tree.rootNode.leftChild.leftChild = new Node(7); tree.rootNode.leftChild.rightChild = new Node(6); tree.rootNode.rightChild.leftChild = new Node(5); tree.rootNode.rightChild.rightChild = new Node(4); System.out.println("ZigZag Order traversal of binary tree is"); tree.printZigZagTraversal(); } } // This Code is contributed by Harikrishnan Rajan. |
Python3
# Python Program to print zigzag traversal # of binary tree # Binary tree node class Node: # Constructor to create a new node def __init__(self, data): self.data = data self.left = self.right = None # function to print zigzag traversal of # binary tree def zizagtraversal(root): # Base Case if root is None: return # Create two stacks to store current # and next level currentLevel = [] nextLevel = [] # if ltr is true push nodes from # left to right otherwise from # right to left ltr = True # append root to currentlevel stack currentLevel.append(root) # Check if stack is empty while len(currentLevel) > 0: # pop from stack temp = currentLevel.pop(-1) # print the data print(temp.data, " ", end="") if ltr: # if ltr is true push left # before right if temp.left: nextLevel.append(temp.left) if temp.right: nextLevel.append(temp.right) else: # else push right before left if temp.right: nextLevel.append(temp.right) if temp.left: nextLevel.append(temp.left) if len(currentLevel) == 0: # reverse ltr to push node in # opposite order ltr = not ltr # swapping of stacks currentLevel, nextLevel = nextLevel, currentLevel # Driver program to check above function root = Node(1) root.left = Node(2) root.right = Node(3) root.left.left = Node(7) root.left.right = Node(6) root.right.left = Node(5) root.right.right = Node(4) print("Zigzag Order traversal of binary tree is") zizagtraversal(root) # This code is contributed by Shweta Singh |
C#
// C# implementation of a O(n) time // method for Zigzag order traversal using System; using System.Collections.Generic; // Binary Tree node public class Node { public int data; public Node leftChild; public Node rightChild; public Node(int data) { this.data = data; } } class GFG { public Node rootNode; // function to print the // zigzag traversal public virtual void printZigZagTraversal() { // if null then return if (rootNode == null) { return; } // declare two stacks Stack<Node> currentLevel = new Stack<Node>(); Stack<Node> nextLevel = new Stack<Node>(); // push the root currentLevel.Push(rootNode); bool leftToRight = true; // check if stack is empty while (currentLevel.Count > 0) { // pop out of stack Node node = currentLevel.Pop(); // print the data in it Console.Write(node.data + " "); // store data according to current // order. if (leftToRight) { if (node.leftChild != null) { nextLevel.Push(node.leftChild); } if (node.rightChild != null) { nextLevel.Push(node.rightChild); } } else { if (node.rightChild != null) { nextLevel.Push(node.rightChild); } if (node.leftChild != null) { nextLevel.Push(node.leftChild); } } if (currentLevel.Count == 0) { leftToRight = !leftToRight; Stack<Node> temp = currentLevel; currentLevel = nextLevel; nextLevel = temp; } } } } public class zigZagTreeTraversal { // Driver Code public static void Main(string[] args) { GFG tree = new GFG(); tree.rootNode = new Node(1); tree.rootNode.leftChild = new Node(2); tree.rootNode.rightChild = new Node(3); tree.rootNode.leftChild.leftChild = new Node(7); tree.rootNode.leftChild.rightChild = new Node(6); tree.rootNode.rightChild.leftChild = new Node(5); tree.rootNode.rightChild.rightChild = new Node(4); Console.WriteLine("ZigZag Order traversal " + "of binary tree is"); tree.printZigZagTraversal(); } } // This code is contributed by Shrikant13 |
Output:
ZigZag Order traversal of binary tree is 1 3 2 7 6 5 4
Time Complexity: O(n)
Space Complexity: O(n)+(n)=O(n)
leave a comment
0 Comments