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 node struct Node { int val; vector<Node*> child; }; // Function to create a new node Node* newNode( int key) { Node* temp = new Node; temp->val = key; return temp; } // Function to perform zig zag traversal // of the given tree void 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 Code int 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 approach import 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 node class Node: def __init__( self , key): self .val = key self .child = [] # Function to create a new node def newNode(key): temp = Node(key) return temp # Function to perform zig zag traversal # of the given tree def 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 Call zigzagLevelOrder(root) # This code is contributed by decode2207. |
C#
// C# program for the above approach using 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> |
1 3 2 4 5 6 7 8
Time Complexity: O(N)
Auxiliary Space: O(N)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!