Given a Generic Tree consisting of N nodes, the task is to find the ZigZag Level Order Traversal of the given tree.
Examples:
Input:
Output:
1
3 2
4 5 6 7 8
Approach: The given problem can be solved by using BFS Traversal. The approach is very similar to the Level Order Traversal of the N-ary Tree. It can be observed that on reversing the order of the even levels during the Level Order Traversal, the obtained sequence is a ZigZag traversal. Based on these observations, below are the steps to follow :
- During the BFS Traversal, store the nodes of each level into a vector, say curLevel[].
- For each respective level store curLevel into a vector of vectors, say result[].
- Reverse the vectors present at even positions in result[].
- After completing the above steps, all the vectors stored in the result[] the required result.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Structure of a tree nodestruct Node { int val; vector<Node*> child;};// Function to create a new nodeNode* newNode(int key){ Node* temp = new Node; temp->val = key; return temp;}// Function to perform zig zag traversal// of the given treevoid zigzagLevelOrder(Node* root){ if (root == NULL) return; // Stores the vectors containing nodes // in each level of tree respectively vector<vector<int> > result; // Create a queue for BFS queue<Node*> q; // Enqueue Root of the tree q.push(root); // Standard Level Order Traversal // code using queue while (!q.empty()) { int size = q.size(); // Stores the element in the // current level vector<int> curLevel; // Iterate over all nodes of // the current level for (int i = 0; i < size; i++) { Node* node = q.front(); q.pop(); curLevel.push_back(node->val); // Insert all children of the // current node into the queue for (int j = 0; j < node->child.size(); j++) { q.push(node->child[j]); } } // Insert curLevel into result result.push_back(curLevel); } // Loop to Print the ZigZag Level order // Traversal of the given tree for (int i = 0; i < result.size(); i++) { // If i+1 is even reverse the order // of nodes in the current level if ((i + 1) % 2 == 0) { reverse(result[i].begin(), result[i].end()); } // Print the node of ith level for (int j = 0; j < result[i].size(); j++) { cout << result[i][j] << " "; } cout << endl; }}// Driver Codeint main(){ Node* root = newNode(1); (root->child).push_back(newNode(2)); (root->child).push_back(newNode(3)); (root->child[0]->child).push_back(newNode(4)); (root->child[0]->child).push_back(newNode(5)); (root->child[1]->child).push_back(newNode(6)); (root->child[1])->child.push_back(newNode(7)); (root->child[1]->child).push_back(newNode(8)); // Function Call zigzagLevelOrder(root); return 0;} |
Java
// Java program for the above approachimport java.util.*;public class Main{ // Class containing left and // right child of current // node and key value static class Node { public int val; public Vector<Node> child; public Node(int key) { val = key; child = new Vector<Node>(); } } // Function to create a new node static Node newNode(int key) { Node temp = new Node(key); return temp; } // Function to perform zig zag traversal // of the given tree static void zigzagLevelOrder(Node root) { if (root == null) return; // Stores the vectors containing nodes // in each level of tree respectively Vector<Vector<Integer>> result = new Vector<Vector<Integer>>(); // Create a queue for BFS Vector<Node> q = new Vector<Node>(); // Enqueue Root of the tree q.add(root); // Standard Level Order Traversal // code using queue while(q.size() > 0) { int size = q.size(); // Stores the element in the // current level Vector<Integer> curLevel = new Vector<Integer>(); // Iterate over all nodes of // the current level for(int i = 0; i < size; i++) { Node node = q.get(0); q.remove(0); curLevel.add(node.val); // Insert all children of the // current node into the queue for(int j = 0; j < (node.child).size(); j++) q.add(node.child.get(j)); } // Insert curLevel into result result.add(curLevel); } // Loop to Print the ZigZag Level order // Traversal of the given tree for(int i = 0; i < result.size(); i++) { // If i+1 is even reverse the order // of nodes in the current level if ((i + 1) % 2 == 0) { Collections.reverse(result.get(i)); } // Print the node of ith level for(int j = 0; j < result.get(i).size(); j++) System.out.print(result.get(i).get(j) + " "); System.out.println(); } } public static void main(String[] args) { Node root = newNode(1); (root.child).add(newNode(2)); (root.child).add(newNode(3)); (root.child.get(0).child).add(newNode(4)); (root.child.get(0).child).add(newNode(5)); (root.child.get(1).child).add(newNode(6)); (root.child.get(1)).child.add(newNode(7)); (root.child.get(1).child).add(newNode(8)); // Function Call zigzagLevelOrder(root); }}// This code is contributed by divyesh072019. |
Python3
# Python3 program for the above approach# Structure of a tree nodeclass Node: def __init__(self, key): self.val = key self.child = []# Function to create a new nodedef newNode(key): temp = Node(key) return temp # Function to perform zig zag traversal# of the given treedef zigzagLevelOrder(root): if (root == None): return # Stores the vectors containing nodes # in each level of tree respectively result = [] # Create a queue for BFS q = [] # Enqueue Root of the tree q.append(root) # Standard Level Order Traversal # code using queue while len(q) > 0: size = len(q) # Stores the element in the # current level curLevel = [] # Iterate over all nodes of # the current level for i in range(size): node = q[0] q.pop(0) curLevel.append(node.val) # Insert all children of the # current node into the queue for j in range(len(node.child)): q.append(node.child[j]) # Insert curLevel into result result.append(curLevel) # Loop to Print the ZigZag Level order # Traversal of the given tree for i in range(len(result)): # If i+1 is even reverse the order # of nodes in the current level if ((i + 1) % 2 == 0): result[i].reverse() # Print the node of ith level for j in range(len(result[i])): print(result[i][j], end = " ") print()root = newNode(1)(root.child).append(newNode(2))(root.child).append(newNode(3))(root.child[0].child).append(newNode(4))(root.child[0].child).append(newNode(5))(root.child[1].child).append(newNode(6))(root.child[1]).child.append(newNode(7))(root.child[1].child).append(newNode(8))# Function CallzigzagLevelOrder(root)# This code is contributed by decode2207. |
C#
// C# program for the above approachusing System;using System.Collections.Generic;class GFG { // Structure of a tree node class Node { public int val; public List<Node> child; public Node(int key) { val = key; child = new List<Node>(); } } // Function to create a new node static Node newNode(int key) { Node temp = new Node(key); return temp; } // Function to perform zig zag traversal // of the given tree static void zigzagLevelOrder(Node root) { if (root == null) return; // Stores the vectors containing nodes // in each level of tree respectively List<List<int>> result = new List<List<int>>(); // Create a queue for BFS List<Node> q = new List<Node>(); // Enqueue Root of the tree q.Add(root); // Standard Level Order Traversal // code using queue while(q.Count > 0) { int size = q.Count; // Stores the element in the // current level List<int> curLevel = new List<int>(); // Iterate over all nodes of // the current level for(int i = 0; i < size; i++) { Node node = q[0]; q.RemoveAt(0); curLevel.Add(node.val); // Insert all children of the // current node into the queue for(int j = 0; j < (node.child).Count; j++) q.Add(node.child[j]); } // Insert curLevel into result result.Add(curLevel); } // Loop to Print the ZigZag Level order // Traversal of the given tree for(int i = 0; i < result.Count; i++) { // If i+1 is even reverse the order // of nodes in the current level if ((i + 1) % 2 == 0) { result[i].Reverse(); } // Print the node of ith level for(int j = 0; j < result[i].Count; j++) Console.Write(result[i][j] + " "); Console.WriteLine(); } } static void Main() { Node root = newNode(1); (root.child).Add(newNode(2)); (root.child).Add(newNode(3)); (root.child[0].child).Add(newNode(4)); (root.child[0].child).Add(newNode(5)); (root.child[1].child).Add(newNode(6)); (root.child[1]).child.Add(newNode(7)); (root.child[1].child).Add(newNode(8)); // Function Call zigzagLevelOrder(root); }}// This code is contributed by suresh07. |
Javascript
<script> // Javascript program for the above approach // Structure of a tree node class Node { constructor(key) { this.child = []; this.val = key; } } // Function to create a new node function newNode(key) { let temp = new Node(key); return temp; } // Function to perform zig zag traversal // of the given tree function zigzagLevelOrder(root) { if (root == null) return; // Stores the vectors containing nodes // in each level of tree respectively let result = []; // Create a queue for BFS let q = []; // Enqueue Root of the tree q.push(root); // Standard Level Order Traversal // code using queue while(q.length > 0) { let size = q.length; // Stores the element in the // current level let curLevel = []; // Iterate over all nodes of // the current level for(let i = 0; i < size; i++) { let node = q[0]; q.shift(); curLevel.push(node.val); // Insert all children of the // current node into the queue for(let j = 0; j < (node.child).length; j++) q.push(node.child[j]); } // Insert curLevel into result result.push(curLevel); } // Loop to Print the ZigZag Level order // Traversal of the given tree for(let i = 0; i < result.length; i++) { // If i+1 is even reverse the order // of nodes in the current level if ((i + 1) % 2 == 0) { result[i].reverse(); } // Print the node of ith level for(let j = 0; j < result[i].length; j++) document.write(result[i][j] + " "); document.write("</br>"); } } let root = newNode(1); (root.child).push(newNode(2)); (root.child).push(newNode(3)); (root.child[0].child).push(newNode(4)); (root.child[0].child).push(newNode(5)); (root.child[1].child).push(newNode(6)); (root.child[1]).child.push(newNode(7)); (root.child[1].child).push(newNode(8)); // Function Call zigzagLevelOrder(root); // This code is contributed by divyeshrabadiya07.</script> |
Output:
1 3 2 4 5 6 7 8
Time Complexity: O(N)
Auxiliary Space: O(N)
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!
