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!
