ZigZag Level Order Traversal of an N-ary Tree

0 0 7 minutes read

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>

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 zambiatek!