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 nodestruct Node { int data; struct Node *left, *right;};// function to print the zigzag traversalvoid zigzagtraversal(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 nodestruct 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 functionint 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 \n"; zigzagtraversal(root); return 0;} |
Java
// Java implementation of a O(n) time // method for Zigzag order traversalimport java.util.*;// Binary Tree nodeclass Node{int data;Node leftChild;Node rightChild;Node(int data){ this.data = data; }}class BinaryTree {Node rootNode;// function to print the// zigzag traversalvoid 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 functionpublic 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 nodeclass 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 treedef zigzagtraversal(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 functionroot = 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")zigzagtraversal(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 Codepublic 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 |
Javascript
<script> // JavaScript implementation of a O(n) time // method for Zigzag order traversal class Node { constructor(data) { this.leftChild = null; this.rightChild = null; this.data = data; } } let rootNode; // function to print the // zigzag traversal function printZigZagTraversal() { // if null then return if (rootNode == null) { return; } // declare two stacks let currentLevel = []; let nextLevel = []; // push the root currentLevel.push(rootNode); let leftToRight = true; // check if stack is empty while (currentLevel.length > 0) { // pop out of stack let node = currentLevel.pop(); // print the data in it document.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.length == 0) { leftToRight = !leftToRight; let temp = currentLevel; currentLevel = nextLevel; nextLevel = temp; } } } rootNode = new Node(1); rootNode.leftChild = new Node(2); rootNode.rightChild = new Node(3); rootNode.leftChild.leftChild = new Node(7); rootNode.leftChild.rightChild = new Node(6); rootNode.rightChild.leftChild = new Node(5); rootNode.rightChild.rightChild = new Node(4); document.write("ZigZag Order traversal of binary tree is" + "</br>"); printZigZagTraversal();</script> |
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)
Recursive Approach: The approach used here is the observable similarity to the level order traversal. Here we need to include an extra parameter to keep a track of printing each level in left-right or right-left way.
Implementation:
C++
//Initial Template for C++#include <bits/stdc++.h>using namespace std;struct Node { int data; Node *left; Node *right; Node(int val) { data = val; left = right = NULL; }};// Function to Build TreeNode* buildTree(string str){ // Corner Case if(str.length() == 0 || str[0] == 'N') return NULL; // Creating vector of strings from input // string after splitting by space vector<string> ip; istringstream iss(str); for(string str; iss >> str; ) ip.push_back(str); // Create the root of the tree Node* root = new Node(stoi(ip[0])); // Push the root to the queue queue<Node*> queue; queue.push(root); // Starting from the second element int i = 1; while(!queue.empty() && i < ip.size()) { // Get and remove the front of the queue Node* currNode = queue.front(); queue.pop(); // Get the current node's value from the string string currVal = ip[i]; // If the left child is not null if(currVal != "N") { // Create the left child for the current node currNode->left = new Node(stoi(currVal)); // Push it to the queue queue.push(currNode->left); } // For the right child i++; if(i >= ip.size()) break; currVal = ip[i]; // If the right child is not null if(currVal != "N") { // Create the right child for the current node currNode->right = new Node(stoi(currVal)); // Push it to the queue queue.push(currNode->right); } i++; } return root;}// Function to calculate height of treeint treeHeight(Node *root){ if(!root) return 0; int lHeight = treeHeight(root->left); int rHeight = treeHeight(root->right); return max(lHeight, rHeight) + 1;}// Helper Function to store the zig zag order traversal// of tree in a list recursivelyvoid zigZagTraversalRecursion(Node* root, int height, bool lor, vector<int> &ans){ // Height = 1 means the tree now has only one node if(height <= 1){ if(root) ans.push_back(root->data); } // When Height > 1 else{ if(lor){ if(root->left) zigZagTraversalRecursion(root->left, height - 1, lor, ans); if(root->right) zigZagTraversalRecursion(root->right, height - 1, lor, ans); } else{ if(root->right) zigZagTraversalRecursion(root->right, height - 1, lor, ans); if(root->left) zigZagTraversalRecursion(root->left, height - 1, lor, ans); } }}// Function to traverse tree in zig zag ordervector <int> zigZagTraversal(Node* root){ vector<int> ans; bool leftOrRight = true; int height = treeHeight(root); for(int i = 1; i <= height; i++){ zigZagTraversalRecursion(root, i, leftOrRight, ans); leftOrRight = !leftOrRight; } return ans;}int main(){ // Tree: // 1 // / \ // / \ // / \ // 2 3 // / \ / \ // 4 5 6 7 // / \ / \ / \ / \ //8 9 10 11 12 13 14 15 string s = "1 2 3 4 5 6 7 8 9 10 11 12 13 14 15"; Node* root = buildTree(s); vector <int> res = zigZagTraversal(root); cout<<"ZigZag traversal of binary tree is:"<<endl; for (int i = 0; i < res.size (); i++) cout << res[i] << " "; cout<<endl; return 0;}// Code By Angshuman Sengupta |
Java
// Java code for the above approachimport java.io.*;import java.util.*;class Node { int data; Node left, right; public Node(int val) { data = val; left = null; right = null; }}class GFG { static Node root = null; // Function to Build Tree static Node buildTree(String s) { // Corner Case if (s.length() == 0 || s.charAt(0) == 'N') { return null; } // Creating list of strings from input // string after spliting by space String[] ip = s.split(" "); // Create the root of the tree root = new Node(Integer.parseInt(ip[0])); int size = 0; Deque<Node> q = new LinkedList<>(); // Push the root to the queue q.add(root); size++; // Starting from the second element int i = 1; while (size > 0 && i < ip.length) { // Get and remove the front of the queue Node currNode = q.peek(); q.pop(); size--; // Get the current node's value from the string String currVal = ip[i]; // If the left child is not null if (!currVal.equals("N")) { // Create the left child for the current // node currNode.left = new Node(Integer.parseInt(currVal)); // Push it to the queue q.add(currNode.left); size++; } // For the right child i++; if (i >= ip.length) { break; } currVal = ip[i]; // If the right child is not null if (!currVal.equals("N")) { // Create the right child for the current // node currNode.right = new Node(Integer.parseInt(currVal)); // Push it to the queue q.add(currNode.right); size++; } i++; } return root; } // Function to calculate height of tree static int treeHeight(Node root) { if (root == null) { return 0; } int lHeight = treeHeight(root.left); int rHeight = treeHeight(root.right); return Math.max(lHeight, rHeight) + 1; } // Helper function to store the zig zag order traversal // of tree in a list recursively static void zigZagTraversalRecursion(Node root, int height, boolean lor, ArrayList<Integer> ans) { // Height = 1 means the tree now has only one node if (height <= 1) { if (root != null) ans.add(root.data); } // When Height > 1 else { if (lor) { if (root.left != null) zigZagTraversalRecursion( root.left, height - 1, lor, ans); if (root.right != null) zigZagTraversalRecursion( root.right, height - 1, lor, ans); } else { if (root.right != null) zigZagTraversalRecursion( root.right, height - 1, lor, ans); if (root.left != null) zigZagTraversalRecursion( root.left, height - 1, lor, ans); } } } // Function to traverse tree in zig zag order static ArrayList<Integer> zigZagTraversal(Node root) { ArrayList<Integer> ans = new ArrayList<Integer>(); boolean leftOrRight = true; int height = treeHeight(root); for (int i = 1; i <= height; i++) { zigZagTraversalRecursion(root, i, leftOrRight, ans); leftOrRight = !leftOrRight; } return ans; } public static void main(String[] args) { // Tree: // 1 // / \ // / \ // / \ // 2 3 // / \ / \ // 4 5 6 7 // / \ / \ / \ / \ // 8 9 10 11 12 13 14 15 String s = "1 2 3 4 5 6 7 8 9 10 11 12 13 14 15"; Node root = buildTree(s); List<Integer> res = zigZagTraversal(root); System.out.print( "ZigZag traversal of binary tree is:"); for (int i = 0; i < res.size(); i++) { System.out.print(res.get(i) + " "); } System.out.println(); }}// This code is contributed by lokesh. |
Python3
# Python code for recursive approachfrom collections import defaultdictfrom collections import dequeclass Node: def __init__(self, val): self.data = val self.left = None self.right = None# Function to Build Treedef buildTree(s): # Corner Case if(len(s) == 0 or s[0] == "N"): return None # Creating list of strings from input # string after spliting by space ip = list(map(str, s.split())) # Create the root of the tree root = Node(int(ip[0])) size = 0 q = deque() # Push the root to the queue q.append(root) size = size+1 # Starting from the second element i = 1 while(size > 0 and i < len(ip)): # Get and remove the front of the queue currNode = q[0] q.popleft() size = size-1 # Get the current node's value from the string currVal = ip[i] # If the left child is not null if(currVal != "N"): # Create the left child for the current node currNode.left = Node(int(currVal)) # Push it to the queue q.append(currNode.left) size = size+1 # For the right child i = i+1 if(i >= len(ip)): break currVal = ip[i] # If the right child is not null if(currVal != "N"): # Create the right child for the current node currNode.right = Node(int(currVal)) # Push it to the queue q.append(currNode.right) size = size+1 i = i+1 return root# Function to calculate height of treedef treeHeight(root): if not root: return 0 lHeight = treeHeight(root.left) rHeight = treeHeight(root.right) return max(lHeight, rHeight) + 1 # Helper Function to store the zig zag order traversal# of tree in a list recursivelydef zigZagTraversalRecursion(root, height, lor, ans): # Height = 1 means the tree now has only one node if height <= 1: if root: ans.append(root.data) # When Height > 1 else: if lor: if root.left: zigZagTraversalRecursion(root.left, height - 1, lor, ans) if root.right: zigZagTraversalRecursion(root.right, height - 1, lor, ans) else: if root.right: zigZagTraversalRecursion(root.right, height - 1, lor, ans) if root.left: zigZagTraversalRecursion(root.left, height - 1, lor, ans)# Function to traverse tree in zig zag orderdef zigZagTraversal(root): ans = [] leftOrRight = True height = treeHeight(root) for i in range(1, height + 1): zigZagTraversalRecursion(root, i, leftOrRight, ans) leftOrRight = not leftOrRight return ansif __name__ == '__main__': # Tree: # 1 # / \ # / \ # / \ # 2 3 # / \ / \ # 4 5 6 7 # / \ / \ / \ / \ # 8 9 10 11 12 13 14 15 s = "1 2 3 4 5 6 7 8 9 10 11 12 13 14 15" root = buildTree(s) res = zigZagTraversal(root) print("ZigZag traversal of binary tree is:") for i in range(len(res)): print(res[i], end=" ") print()# This code is contributed by Tapesh (tapeshdua420) |
C#
using System;using System.Collections.Generic;public class Node { public int data; public Node left; public Node right; public Node(int val) { data = val; left = right = null; }}public class Gfg { static Node buildTree(string str) { if (str.Length == 0 || str[0] == 'N') return null; var ip = new List<string>(str.Split(' ')); // Create the root of the tree Node root = new Node(int.Parse(ip[0])); // Push the root to the queue Queue<Node> queue = new Queue<Node>(); queue.Enqueue(root); // Starting from the second element int i = 1; while (queue.Count != 0 && i < ip.Count) { // Get and remove the front of the queue Node currNode = queue.Dequeue(); // Get the current node's value from the string string currVal = ip[i]; // If the left child is not null if (currVal != "N") { // Create the right child for the current node currNode.left = new Node(int.Parse(currVal)); // Push it to the queue queue.Enqueue(currNode.left); } // For the right child i++; if (i >= ip.Count) break; currVal = ip[i]; // If the right child is not null if (currVal != "N") { // Create the right child for the current node currNode.right = new Node(int.Parse(currVal)); // Push it to the queue queue.Enqueue(currNode.right); } i++; } return root; } // Function to calculate height of tree static int treeHeight(Node root) { if (root == null) return 0; int lHeight = treeHeight(root.left); int rHeight = treeHeight(root.right); return Math.Max(lHeight, rHeight) + 1; } // Helper Function to store the zig zag order traversal // of tree in a list recursively static void zigZagTraversalRecursion(Node root, int height, bool lor, List<int> ans) { // Height = 1 means the tree now has only one node if (height <= 1) { if (root != null) ans.Add(root.data); } // When Height > 1 else { if (lor) { if (root.left != null) zigZagTraversalRecursion(root.left, height - 1, lor, ans); if (root.right != null) zigZagTraversalRecursion(root.right, height - 1, lor, ans); } else { if (root.right != null) zigZagTraversalRecursion(root.right, height - 1, lor, ans); if (root.left != null) zigZagTraversalRecursion(root.left, height - 1, lor, ans); } } } // Function to traverse tree in zig zag order static List<int> zigZagTraversal(Node root) { List<int> ans = new List<int>(); bool leftOrRight = true; int height = treeHeight(root); for (int i = 1; i <= height; i++) { zigZagTraversalRecursion(root, i, leftOrRight, ans); leftOrRight = !leftOrRight; } return ans; } static void Main() { // Tree: // 1 // / \ // / \ // / \ // 2 3 // / \ / \ // 4 5 6 7 // / \ / \ / \ / \ //8 9 10 11 12 13 14 15 string s = "1 2 3 4 5 6 7 8 9 10 11 12 13 14 15"; Node root = buildTree(s); List<int> res = zigZagTraversal(root); Console.WriteLine("ZigZag traversal of binary tree is:"); foreach (int val in res) { Console.Write(val + " "); } Console.WriteLine(); }} |
Javascript
class Node { constructor(val) { this.data = val; this.left = null; this.right = null; }}// Function to Build Treefunction buildTree(str) { // Corner Case if (str.length === 0 || str[0] === 'N') { return null; } // Creating vector of strings from input // string after splitting by space let ip = str.split(" "); // Create the root of the tree let root = new Node(Number(ip[0])); // Push the root to the queue let queue = []; queue.push(root); // Starting from the second element let i = 1; while (queue.length > 0 && i < ip.length) { // Get and remove the front of the queue let currNode = queue.shift(); // Get the current node's value from the string let currVal = ip[i]; // If the left child is not null if (currVal !== "N") { // Create the left child for the current node currNode.left = new Node(Number(currVal)); // Push it to the queue queue.push(currNode.left); } // For the right child i++; if (i >= ip.length) { break; } currVal = ip[i]; // If the right child is not null if (currVal !== "N") { // Create the right child for the current node currNode.right = new Node(Number(currVal)); // Push it to the queue queue.push(currNode.right); } i++; } return root;}// Function to calculate height of treefunction treeHeight(root) { if (!root) return 0; let lHeight = treeHeight(root.left); let rHeight = treeHeight(root.right); return Math.max(lHeight, rHeight) + 1;}// Helper Function to store the zig zag order traversal// of tree in a list recursivelyfunction zigZagTraversalRecursion(root, height, lor, ans) { // Height = 1 means the tree now has only one node if (height <= 1) { if (root) ans.push(root.data); } // When Height > 1 else { if (lor) { if (root.left) zigZagTraversalRecursion(root.left, height - 1, lor, ans); if (root.right) zigZagTraversalRecursion(root.right, height - 1, lor, ans); } else { if (root.right) zigZagTraversalRecursion(root.right, height - 1, lor, ans); if (root.left) zigZagTraversalRecursion(root.left, height - 1, lor, ans); } }}// Function to traverse tree in zig// zag orderfunction zigZagTraversal(root) { let ans = []; let leftOrRight = true; let height = treeHeight(root); for (let i = 1; i <= height; i++) { zigZagTraversalRecursion(root, i, leftOrRight, ans); leftOrRight = !leftOrRight; } return ans;}// Tree:// 1// / \// / \// / \// 2 3// / \ / \// 4 5 6 7// / \ / \ / \ / \//8 9 10 11 12 13 14 15let s = "1 2 3 4 5 6 7 8 9 10 11 12 13 14 15";let root = buildTree(s);let res=zigZagTraversal(root);document.write("ZigZag traversal of binary tree is:");for(let i=0; i<res.length; i++) document.write(res[i]+" "); |
Output
ZigZag traversal of binary tree is: 1 3 2 4 5 6 7 15 14 13 12 11 10 9 8
Another Approach: In this approach, use a deque to solve the problem. Push and pop in different ways depending on if the level is odd or level is even.
Below is the implementation of the above approach:
C++
// C++ implementation of a O(n) time method for// Zigzag order traversal#include <bits/stdc++.h>#include <iostream>using namespace std;// Binary Tree nodeclass Node {public: int data; Node *left, *right;};// Function to print the zigzag traversalvector<int> zigZagTraversal(Node* root){ deque<Node*> q; vector<int> v; q.push_back(root); v.push_back(root->data); Node* temp; // set initial level as 1, because root is // already been taken care of. int l = 1; while (!q.empty()) { int n = q.size(); for (int i = 0; i < n; i++) { // popping mechanism if (l % 2 == 0) { temp = q.back(); q.pop_back(); } else { temp = q.front(); q.pop_front(); } // pushing mechanism if (l % 2 != 0) { if (temp->right) { q.push_back(temp->right); v.push_back(temp->right->data); } if (temp->left) { q.push_back(temp->left); v.push_back(temp->left->data); } } else if (l % 2 == 0) { if (temp->left) { q.push_front(temp->left); v.push_back(temp->left->data); } if (temp->right) { q.push_front(temp->right); v.push_back(temp->right->data); } } } l++; // level plus one } return v;}// A utility function to create a new nodestruct 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 functionint main(){ // vector to store the traversal order. vector<int> v; // 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 \n"; v = zigZagTraversal(root); for (int i = 0; i < v.size(); i++) { // to print the order cout << v[i] << " "; } return 0;}// This code is contributed by Ritvik Mahajan |
Java
// Java implementation of a O(n) time method for// Zigzag order traversalimport java.util.*;public class Main{ // Class containing left and // right child of current // node and key value static class Node { public int data; public Node left, right; public Node(int data) { this.data = data; left = right = null; } } // A utility function to create a new node static Node newNode(int data) { Node node = new Node(data); return node; } // Function to print the zigzag traversal static Vector<Integer> zigZagTraversal(Node root) { Deque<Node> q = new LinkedList<Node>(); Vector<Integer> v = new Vector<Integer>(); q.add(root); v.add(root.data); Node temp; // set initial level as 1, because root is // already been taken care of. int l = 1; while (q.size() > 0) { int n = q.size(); for (int i = 0; i < n; i++) { // popping mechanism if (l % 2 == 0) { temp = q.peekLast(); q.pollLast(); } else { temp = q.peekFirst(); q.pollFirst(); } // pushing mechanism if (l % 2 != 0) { if (temp.right != null) { q.add(temp.right); v.add(temp.right.data); } if (temp.left != null) { q.add(temp.left); v.add(temp.left.data); } } else if (l % 2 == 0) { if (temp.left != null) { q.offerFirst(temp.left); v.add(temp.left.data); } if (temp.right != null) { q.offerFirst(temp.right); v.add(temp.right.data); } } } l++; // level plus one } return v; } public static void main(String[] args) { // vector to store the traversal order. Vector<Integer> v; // create tree 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); System.out.println("ZigZag Order traversal of binary tree is"); v = zigZagTraversal(root); for (int i = 0; i < v.size(); i++) { // to print the order System.out.print(v.get(i) + " "); } }}// This code is contributed by divyesh072019. |
Python3
# Python3 implementation of a O(n) time method for# Zigzag order traversalfrom collections import deque # Binary Tree nodeclass Node: def __init__(self, data): self.data = data self.left = None self.right = None# Function to print the zigzag traversaldef zigZagTraversal(root): q = deque([]) v = [] q.append(root) v.append(root.data) # set initial level as 1, because root is # already been taken care of. l = 1 while len(q) > 0: n = len(q) for i in range(n): # popping mechanism if (l % 2 == 0): temp = q[-1] q.pop() else: temp = q[0] q.popleft() # pushing mechanism if (l % 2 != 0): if (temp.right): q.append(temp.right) v.append(temp.right.data) if (temp.left): q.append(temp.left) v.append(temp.left.data) elif (l % 2 == 0): if (temp.left): q.appendleft(temp.left) v.append(temp.left.data) if (temp.right): q.appendleft(temp.right) v.append(temp.right.data) l+=1 # level plus one return v# vector to store the traversal order.v = []# create treeroot = 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")v = zigZagTraversal(root)for i in range(len(v)): print(v[i], end = " ") # This code is contributed by suresh07. |
C#
// C# implementation of a O(n) time method for// Zigzag order traversalusing System;using System.Collections.Generic;// Binary Tree nodepublic class Node { public int data; public Node left, right; public Node(int data) { this.data = data; left = right = null; }}// Class to store the zigzag traversalpublic class ZigZagTraversal { public static List<int> zigZagTraversal(Node root) { var q = new LinkedList<Node>(); var v = new List<int>(); q.AddLast(root); v.Add(root.data); Node temp; // set initial level as 1, because root is // already been taken care of. int l = 1; while (q.Count > 0) { int n = q.Count; for (int i = 0; i < n; i++) { // popping mechanism if (l % 2 == 0) { temp = q.Last.Value; q.RemoveLast(); } else { temp = q.First.Value; q.RemoveFirst(); } // pushing mechanism if (l % 2 != 0) { if (temp.right != null) { q.AddLast(temp.right); v.Add(temp.right.data); } if (temp.left != null) { q.AddLast(temp.left); v.Add(temp.left.data); } } else if (l % 2 == 0) { if (temp.left != null) { q.AddFirst(temp.left); v.Add(temp.left.data); } if (temp.right != null) { q.AddFirst(temp.right); v.Add(temp.right.data); } } } l++; // level plus one } return v; } // Driver program to test // the above function static void Main(string[] args) { // vector to store the traversal order. List<int> v = new List<int>(); // create tree Node root = new Node(1); root.left = new Node(2); root.right = new Node(3); root.left.left = new Node(7); root.left.right = new Node(6); root.right.left = new Node(5); root.right.right = new Node(4); Console.WriteLine("ZigZag Order traversal of binary tree is"); v = zigZagTraversal(root); for (int i = 0; i < v.Count; i++) { // to print the order Console.Write(v[i] + " "); } }} |
Javascript
// Javascript program to print zigzag traversal// binary tree// Binary tree nodeclass Node{ constructor(data){ this.left = null; this.right = null; this.data = data; }} let root;// function to print the zigzag traversalfunction zigZagTraversal(){ let deque = []; deque.push(root); console.log(root.data + " "); let temp; // set initial level as 1, becuase root is // already been taken care of. let l = 1; while(deque.length > 0){ let n = deque.length; for(let i = 0; i<n; i++){ // Popping mechanism if(l%2 == 0){ temp = deque.pop(); }else{ temp = deque.shift(); } // Pushing Mechanism if(l%2 != 0){ if(temp.right != null){ deque.push(temp.right); console.log(temp.right.data + " "); } if(temp.left != null){ deque.push(temp.left); console.log(temp.left.data + " "); } } else if(l%2 == 0){ if(temp.left != null){ deque.unshift(temp.left); console.log(temp.left.data + " "); } if(temp.right != null){ deque.unshift(temp.right); console.log(temp.right.data + " "); } } } l++; //level plus one }}root = new Node(1);root.left = new Node(2);root.right = new Node(3);root.left.left = new Node(7);root.left.right = new Node(6);root.right.left = new Node(5);root.right.right = new Node(4);console.log("ZigZag Order Traversal of binary tree is : ");zigZagTraversal();// This code is contributed by Yash Agarwal(yashagarwal2852002) |
Output
ZigZag Order traversal of binary tree is 1 3 2 7 6 5 4
Time Complexity: O(N)
Auxiliary Space: O(N) for deque data structure
Another Approach: We can use a queue just like we used in Level Order Traversal. But in this case, we can also maintain a flag variable which keeps track of alternate level to reverse the order of the corresponding level traversal.flag==true implies we have to insert from left to right and flag==false means we have to insert element from right to left our answer arraylist.
Implementation:
C++
// C++ implementation of a O(n) time method for// Zigzag order traversal#include <bits/stdc++.h>#include <iostream>using namespace std;// Binary Tree nodeclass Node {public: int data; Node *left, *right;};// Function to print the zigzag traversalvector<int> zigZagTraversal(Node* root) { if(root == NULL){return { } ; } vector<int > ans ; queue<Node*> q ; q.push(root) ; bool flag = false ; while(!q.empty()){ int size = q.size() ; vector<int> level ; for(int i=0 ; i < size ; i++){ Node* node = q.front() ; q.pop() ; level.push_back(node->data) ; if(node->left != NULL) {q.push(node->left) ;} if(node->right != NULL) {q.push(node->right) ;} } flag = !flag ; if(flag == false){ reverse(level.begin() , level.end()) ; } for(int i = 0 ; i < level.size() ; i++){ ans.push_back(level[i]) ; } } return ans ;}// A utility function to create a new nodestruct 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 functionint main(){ // vector to store the traversal order. vector<int> v; // 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 \n"; v = zigZagTraversal(root); for (int i = 0; i < v.size(); i++) { // to print the order cout << v[i] << " "; } return 0;} |
Java
// Java implementation of a O(n) time method for// Zigzag order traversalimport java.util.*;public class Main { // Class containing left and // right child of current // node and key value static class Node { public int data; public Node left, right; public Node(int data) { this.data = data; left = right = null; } } // A utility function to create a new node static Node newNode(int data) { Node node = new Node(data); return node; } // Function to print the zigzag traversal static ArrayList<Integer> zigZagTraversal(Node root) { ArrayList<Integer> ans = new ArrayList<Integer>(); // if there is no element in the tree,return empty // arraylist if (root == null) return ans; Queue<Node> q = new LinkedList<Node>(); q.add(root); // this variable helps to check if elements are to // be added from left to right or right to left boolean leftToRight = true; while (q.size() > 0) { int size = q.size(); // this arraylist is used to store element at // current level ArrayList<Integer> temp = new ArrayList<>(); for (int i = 0; i < size; i++) { Node curr = q.poll(); if (curr.left != null) q.add(curr.left); if (curr.right != null) q.add(curr.right); temp.add(curr.data); } if (leftToRight) // at current level,add element // from left to right to our // answer { // do nothing } // we have to add element from to right to left // and this can be done by reversing our temp // arraylist else { Collections.reverse(temp); } // add element form temp arraylist to our ans // arraylist for (int i = 0; i < temp.size(); i++) { ans.add(temp.get(i)); } // change the value of leftToRight from true to // false or false to true for next iteration. leftToRight = !(leftToRight); } // return our ans arraylist return ans; } public static void main(String[] args) { // Arraylist to store the traversal order. ArrayList<Integer> ans; // create tree 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); System.out.println( "ZigZag Order traversal of binary tree is"); ans = zigZagTraversal(root); for (int i = 0; i < ans.size(); i++) { // to print the order System.out.print(ans.get(i) + " "); } }}// this is contributed by akshita29320 |
Python3
# Python Program to print zigzag traversal# of binary tree# Binary tree nodeclass 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 treedef zigzagtraversal(root): # Base Case if root is None: return ans = [] # store the traversal in the ans array queue = [root] # use list as queue flag = False while len(queue) != 0: n = len(queue) level = [] for i in range(n): node = queue[0] queue.pop(0) level.append(node.data) if node.left: queue.append(node.left) if node.right: queue.append(node.right) flag = not flag if flag == False: level = level[::-1] for i in range(n): ans.append(level[i]) return ans# Driver program to check above functionroot = 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")v = zigzagtraversal(root)for i in v: print(i,end = " ")#This Code is Contributed By Vivek Maddeshiya |
C#
using System;using System.Collections.Generic;class GFG { // Binary Tree node public class Node { public int data; public Node left; public Node right; public Node(int data) { this.data = data; this.left=null; this.right=null; } }; // Function to print the zigzag traversal static List<int> zigZagTraversal(Node root) { List<int > ans =new List<int>(); if(root == null) { return ans ; } Queue<Node> q = new Queue<Node>(); q.Enqueue(root) ; int flag = 0 ; while(q.Count>0){ int size = q.Count ; List<int> level =new List<int>(); for(int i=0 ; i < size ; i++){ Node node = q.Peek() ; q.Dequeue() ; level.Add(node.data) ; if(node.left != null) q.Enqueue(node.left) ; if(node.right != null) q.Enqueue(node.right) ; } flag = 1-flag ; if(flag == 0){ level.Reverse(); } for(int i = 0 ; i < level.Count ; i++){ ans.Add(level[i]) ; } } return ans ; } // 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 public static void Main() { // vector to store the traversal order. List<int> v=new List<int>(); // create tree Node root = new Node(1); root.left = new Node(2); root.right = new Node(3); root.left.left = new Node(7); root.left.right = new Node(6); root.right.left = new Node(5); root.right.right = new Node(4); Console.Write("ZigZag Order traversal of binary tree is \n"); v = zigZagTraversal(root); for (int i = 0; i < v.Count; i++) { // to print the order Console.Write(v[i] + " "); } }}// This code is contributed by poojaagarwal2. |
Javascript
// JavaScript implementation of a O(n) time method for// zigzag order traversalclass Node{ constructor(data){ this.data = data; this.left = null; this.right = null; }}// Function to print zigzag order traversalfunction zigZagTraversal(root){ let ans = []; if(root == null) return ans; let q = []; q.push(root); let flag = false; while(q.length != 0){ let size = q.length; let level = []; for(let i = 0; i<size; i++){ let node = q.shift(); level.push(node.data); if(node.left != null) q.push(node.left); if(node.right != null) q.push(node.right); } flag = !flag; if(flag == false){ level.reverse(); } for(let i = 0; i<level.length; i++){ ans.push(level[i]); } } return ans;}// Driver program to test the above functionlet root = new Node(1);root.left = new Node(2);root.right = new Node(3);root.left.left = new Node(7);root.left.right = new Node(6);root.right.left = new Node(5);root.right.right = new Node(4);document.write("ZigZag Order Traversal of binary tree is ");let v = zigZagTraversal(root);for(let i = 0; i<v.length; i++){ document.write(v[i] + " ");}// This code is contributed by Yash Agarwal(yashagarwal2852002) |
Output
ZigZag Order traversal of binary tree is 1 3 2 7 6 5 4
Time Complexity: O(N)
Auxiliary Space: O(N) for queue data structure
Below is a simple implementation of this problem. (video)
Level order traversal in spiral form
Another approach: Depth-First Search(DFS)
Follow the steps below to implement the above idea:-
- Create a function zigzagLevelOrder that takes a pointer to the root node of the binary tree as input and returns a vector of vectors of integers.
- Inside the zigzagLevelOrder function, create an empty result vector to store the nodes at each level of the binary tree.
- Perform a modified preorder traversal of the binary tree using DFS. To do this, create a recursive helper function traverse that takes the current node, its level, and the result vector as input. In the helper function, if the level is greater than or equal to the size of the result vector, create a new list for the current level in the result vector and add the current node to that list. Otherwise, simply add the current node to the list for the current level in the result vector. Then recursively call the traverse function on the left subtree and the right subtree of the current node, incrementing the level by 1 for each subtree.
- Once the traversal is complete, reverse the order of the lists at odd levels in the result vector to get the zigzag order.
Below is the implementation of the above approach:-
C++
#include <iostream>// C++ code to implement DFS approach#include <vector>#include<algorithm>using namespace std;// Definition for a binary tree node.struct TreeNode { int val; TreeNode* left; TreeNode* right; TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}};class Solution {public: vector<vector<int>> zigzagLevelOrder(TreeNode* root) { vector<vector<int>> result; dfs(root, 0, result); // Perform modified preorder traversal for (int i = 1; i < result.size(); i += 2) { // Reverse the order of nodes at odd levels reverse(result[i].begin(), result[i].end()); } return result; }private: void dfs(TreeNode* root, int level, vector<vector<int>>& result) { if (!root) return; if (level >= result.size()) { // If current level not yet stored, create new level result.push_back(vector<int>()); } result[level].push_back(root->val); // Store current node in its level dfs(root->left, level + 1, result); // Recursively traverse left subtree dfs(root->right, level + 1, result); // Recursively traverse right subtree }};// Driver codeint main() { /* Constructed binary tree is 1 / \ 2 3 / \ / \ 4 5 6 7 */ TreeNode* root = new TreeNode(1); root->left = new TreeNode(2); root->right = new TreeNode(3); root->left->left = new TreeNode(4); root->left->right = new TreeNode(5); root->right->left = new TreeNode(6); root->right->right = new TreeNode(7); Solution sol; vector<vector<int>> result = sol.zigzagLevelOrder(root); // Print zigzag level order traversal cout<<"zig-zag traversal of binary tree is:"<<endl; for (int i = 0; i < result.size(); i++) { for (int j = 0; j < result[i].size(); j++) { cout << result[i][j] << " "; } }cout << endl; return 0;}// This code is contributed by Veerendra_Singh_Rajpoot |
Java
// Java code to implement DFS approachimport java.util.*;// Definition for a binary tree node.class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int x) { val = x; }}class Solution { public List<List<Integer> > zigzagLevelOrder(TreeNode root) { List<List<Integer> > result = new ArrayList<>(); dfs(root, 0, result); // Perform modified preorder traversal for (int i = 1; i < result.size(); i += 2) { // Reverse the order of nodes at odd // levels Collections.reverse(result.get(i)); } return result; } private void dfs(TreeNode root, int level, List<List<Integer> > result) { if (root == null) return; if (level >= result.size()) { // If current level not yet // stored, create new level result.add(new ArrayList<Integer>()); } result.get(level).add( root.val); // Store current node in its level dfs(root.left, level + 1, result); // Recursively traverse left subtree dfs(root.right, level + 1, result); // Recursively traverse right subtree }}// Driver codepublic class Main { public static void main(String[] args) { /* Constructed binary tree is 1 / \ 2 3 / \ / \ 4 5 6 7 */ TreeNode root = new TreeNode(1); root.left = new TreeNode(2); root.right = new TreeNode(3); root.left.left = new TreeNode(4); root.left.right = new TreeNode(5); root.right.left = new TreeNode(6); root.right.right = new TreeNode(7); Solution sol = new Solution(); List<List<Integer> > result = sol.zigzagLevelOrder(root); // Print zigzag level order traversal System.out.println( "zig-zag traversal of binary tree is:"); for (int i = 0; i < result.size(); i++) { for (int j = 0; j < result.get(i).size(); j++) { System.out.print(result.get(i).get(j) + " "); } } System.out.println(); }}// This code is contributed by rutikbhosale |
Python3
# Python code to implement DFS approachfrom typing import List# Definition for a binary tree node.class TreeNode: def __init__(self, x): self.val = x self.left = None self.right = Noneclass Solution: def zigzagLevelOrder(self, root: TreeNode) -> List[List[int]]: result = [] self.dfs(root, 0, result) # Perform modified preorder traversal for i in range(1, len(result), 2): # Reverse the order of nodes at odd levels result[i] = result[i][::-1] return result def dfs(self, root: TreeNode, level: int, result: List[List[int]]) -> None: if not root: return if level >= len(result): # If current level not yet stored, create new level result.append([]) result[level].append(root.val) # Store current node in its level self.dfs(root.left, level + 1, result) # Recursively traverse left subtree self.dfs(root.right, level + 1, result) # Recursively traverse right subtree# Driver codeif __name__ == '__main__': """ Constructed binary tree is 1 / \ 2 3 / \ / \ 4 5 6 7 """ 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) sol = Solution() result = sol.zigzagLevelOrder(root) # Print zigzag level order traversal print("zig-zag traversal of binary tree is:") for i in range(len(result)): for j in range(len(result[i])): print(result[i][j], end=' ') print() |
C#
using System;using System.Collections.Generic;using System.Linq;public class TreeNode{ public int val; public TreeNode left; public TreeNode right; public TreeNode(int x) { val = x; left = null; right = null; }}public class Solution{ public List<List<int>> ZigzagLevelOrder(TreeNode root) { List<List<int>> result = new List<List<int>>(); DFS(root, 0, result); // Perform modified preorder traversal for (int i = 1; i < result.Count; i += 2) { // Reverse the order of nodes at odd levels result[i].Reverse(); } return result; } private void DFS(TreeNode root, int level, List<List<int>> result) { if (root == null) return; if (level >= result.Count) { // If current level not yet stored, create a new level result.Add(new List<int>()); } result[level].Add(root.val); // Store current node in its level DFS(root.left, level + 1, result); // Recursively traverse left subtree DFS(root.right, level + 1, result); // Recursively traverse right subtree }}class Program{ static void Main() { /* Constructed binary tree is 1 / \ 2 3 / \ / \ 4 5 6 7 */ TreeNode root = new TreeNode(1); root.left = new TreeNode(2); root.right = new TreeNode(3); root.left.left = new TreeNode(4); root.left.right = new TreeNode(5); root.right.left = new TreeNode(6); root.right.right = new TreeNode(7); Solution sol = new Solution(); List<List<int>> result = sol.ZigzagLevelOrder(root); // Print zigzag level order traversal Console.WriteLine("Zig-zag traversal of binary tree is:"); foreach (List<int> level in result) { foreach (int val in level) { Console.Write(val + " "); } } }} |
Javascript
class TreeNode { constructor(val) { this.val = val; this.left = null; this.right = null; }}class Solution { zigzagLevelOrder(root) { const result = []; this.dfs(root, 0, result); // Perform modified preorder traversal for (let i = 1; i < result.length; i += 2) { // Reverse the order of nodes at odd levels result[i].reverse(); } return result; } dfs(root, level, result) { if (!root) { return; } if (level >= result.length) { // If current level not yet stored, create new level result.push([]); } result[level].push(root.val); // Store current node in its level this.dfs(root.left, level + 1, result); // Recursively traverse left subtree this.dfs(root.right, level + 1, result); // Recursively traverse right subtree }}// Driver codeconst root = new TreeNode(1);root.left = new TreeNode(2);root.right = new TreeNode(3);root.left.left = new TreeNode(4);root.left.right = new TreeNode(5);root.right.left = new TreeNode(6);root.right.right = new TreeNode(7);const sol = new Solution();const result = sol.zigzagLevelOrder(root);let temp = "";// Print zigzag level order traversalconsole.log("zig-zag traversal of binary tree is:");for (let i = 0; i < result.length; i++) { for (let j = 0; j < result[i].length; j++) { temp = temp + result[i][j] + ' '; }} console.log(temp); |
Output
zig-zag traversal of binary tree is: 1 3 2 4 5 6 7
Time Complexity: (N) , where n is the number of nodes in the binary tree,
Auxiliary Space: O(H) , where h is the height of the tree. The space complexity is O(h) because we are storing the nodes at each level in a separate list,
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
