Level order traversal by converting N-ary Tree into adjacency list representation with K as root node

0 0 7 minutes read

Given the root node of an N-ary tree and an integer K, the task is to convert the given tree into adjacency list representation and print the level order traversal considering vertex K as the root node.

Example:

Input: Tree in the image below, K = 5

Output:
5
1 9 10 11
2 3 4
6 7 8

Input: Tree in the image below, K = 5

Output:
5
1
2 3 4
7 8

Approach: The given problem can be solved by using the DFS Traversal on the N-ary tree and storing the relation of all the edges into an adjacency list according to the adjacency list representation. The created adjacency list can be used to print the Level Order Traversal with K as the root node. This can be done using BFS traversal which is discussed in this article.

Below is the implementation of the above approach:

C++

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// A binary tree node
struct Node {
    int data;
    vector<Node*> child;
};
 
// Function to create a new tree node
Node* newNode(int key)
{
    Node* temp = new Node;
    temp->data = key;
    return temp;
}
 
// Adjacency list to store the Tree
vector<vector<int> > adj;
 
// Function to perform the DFS traversal
// of the N-ary tree using the given
// pointer to the root node of the tree
void DFS(struct Node* node)
{
    // Traverse all child of node
    for (auto x : node->child) {
        if (x != NULL) {
 
            // Insert the pair of vertices
            // into the adjacency list
            adj[node->data].push_back(x->data);
            adj[x->data].push_back(node->data);
 
            // Recursive call for DFS on x
            DFS(x);
        }
    }
}
 
// Function to print the level order
// traversal of the given tree with
// s as root node
void levelOrderTrav(int s, int N)
{
    // Create a queue for Level
    // Order Traversal
    queue<int> q;
 
    // Stores if the current
    // node is visited
    vector<bool> visited(N);
 
    q.push(s);
 
    // -1 marks the end of level
    q.push(-1);
    visited[s] = true;
    while (!q.empty()) {
 
        // Dequeue a vertex from queue
        int v = q.front();
        q.pop();
 
        // If v marks the end of level
        if (v == -1) {
            if (!q.empty())
                q.push(-1);
 
            // Print a newline character
            cout << endl;
            continue;
        }
 
        // Print current vertex
        cout << v << " ";
 
        // Add the child vertices of
        // the current node in queue
        for (int u : adj[v]) {
            if (!visited[u]) {
                visited[u] = true;
                q.push(u);
            }
        }
    }
}
 
// Driver Code
int main()
{
    Node* root = newNode(1);
    (root->child).push_back(newNode(2));
    (root->child).push_back(newNode(3));
    (root->child).push_back(newNode(4));
    (root->child).push_back(newNode(5));
    (root->child[0]->child).push_back(newNode(6));
    (root->child[0]->child).push_back(newNode(7));
    (root->child[2]->child).push_back(newNode(8));
    (root->child[3]->child).push_back(newNode(9));
    (root->child[3]->child).push_back(newNode(10));
    (root->child[3]->child).push_back(newNode(11));
    int N = 11;
    int K = 5;
    adj.resize(N + 1, vector<int>());
 
    DFS(root);
    levelOrderTrav(5, 11);
 
    return 0;
}

Java

// Java program for the above approach
import java.util.*;
 
class Node {
    int data;
    ArrayList<Node> child;
    Node(int data)
    {
        this.data = data;
        this.child = new ArrayList<>();
    }
}
 
class Main {
 
    // Adjacency list to store the Tree
    static List<List<Integer> > adj = new ArrayList<>();
    // Function to perform the DFS traversal
    // of the N-ary tree using the given
    // pointer to the root node of the tree
    static void DFS(Node node)
    {
        for (Node x : node.child) {
            if (x != null) {
                // Insert the pair of vertices
                // into the adjacency list
                adj.get(node.data).add(x.data);
                adj.get(x.data).add(node.data);
                // Recursive call for DFS on x
                DFS(x);
            }
        }
    }
    // Function to print the level order
    // traversal of the given tree with
    // s as root node
    static void levelOrderTrav(int s, int N)
    {
        // Create a queue for Level
        // Order Traversal
        Queue<Integer> q = new LinkedList<>();
        // Stores if the current
        // node is visited
        boolean[] visited = new boolean[N + 1];
 
        q.offer(s);
        // -1 marks the end of level
        q.offer(-1);
        visited[s] = true;
        while (!q.isEmpty()) {
            int v = q.poll();
            if (v == -1) {
                if (!q.isEmpty())
                    q.offer(-1);
                System.out.println();
                continue;
            }
            // Print current vertex
            System.out.print(v + " ");
            // Add the child vertices of
            // the current node in queue
            for (int u : adj.get(v)) {
                if (!visited[u]) {
                    visited[u] = true;
                    q.offer(u);
                }
            }
        }
    }
 
    public static void main(String[] args)
    {
        Node root = new Node(1);
        root.child.add(new Node(2));
        root.child.add(new Node(3));
        root.child.add(new Node(4));
        root.child.add(new Node(5));
        root.child.get(0).child.add(new Node(6));
        root.child.get(0).child.add(new Node(7));
        root.child.get(2).child.add(new Node(8));
        root.child.get(3).child.add(new Node(9));
        root.child.get(3).child.add(new Node(10));
        root.child.get(3).child.add(new Node(11));
        int N = 11;
        int K = 5;
        for (int i = 0; i <= N; i++)
            adj.add(new ArrayList<>());
 
        DFS(root);
        levelOrderTrav(K, N);
    }
}

Python

# Python program for the above approach
from collections import defaultdict, deque
 
# A binary tree node
class Node:
    def __init__(self, data):
        self.data = data
        self.child = []
 
# Function to create a new tree node
def newNode(key):
    temp = Node(key)
    return temp
 
# Adjacency list to store the Tree
adj = defaultdict(list)
 
# Function to perform the DFS traversal
# of the N-ary tree using the given
# pointer to the root node of the tree
def DFS(node):
    # Traverse all child of node
    for x in node.child:
        if x:
            # Insert the pair of vertices
            # into the adjacency list
            adj[node.data].append(x.data)
            adj[x.data].append(node.data)
            # Recursive call for DFS on x
            DFS(x)
 
# Function to print the level order
# traversal of the given tree with
# s as root node
 
 
def levelOrderTrav(s, N):
    # Create a queue for Level
    # Order Traversal
    q = deque()
    # Stores if the current
    # node is visited
    visited = [False] * (N+1)
 
    q.append(s)
    # -1 marks the end of level
    q.append(-1)
    visited[s] = True
    while q:
        # Dequeue a vertex from queue
        v = q.popleft()
        # If v marks the end of level
        if v == -1:
            if q:
                q.append(-1)
            # Print a newline character
             
            continue
        # Print current vertex
        print(v)
        # Add the child vertices of
        # the current node in queue
        for u in adj[v]:
            if not visited[u]:
                visited[u] = True
                q.append(u)
 
# Driver Code
if __name__ == "__main__":
    root = newNode(1)
    root.child.append(newNode(2))
    root.child.append(newNode(3))
    root.child.append(newNode(4))
    root.child.append(newNode(5))
    root.child[0].child.append(newNode(6))
    root.child[0].child.append(newNode(7))
    root.child[2].child.append(newNode(8))
    root.child[3].child.append(newNode(9))
    root.child[3].child.append(newNode(10))
    root.child[3].child.append(newNode(11))
    N = 11
    K = 5
    DFS(root)
    levelOrderTrav(5, 11)
 
    # This code is contributed by aadityamaharshi21.

C#

using System;
using System.Collections.Generic;
 
// Node class definition
class Node {
    // Data members
    public int data;
    public List<Node> child;
 
    // Constructor
    public Node(int data)
    {
        this.data = data;
        this.child = new List<Node>();
    }
}
 
class GFG {
    // Adjacency list to store the Tree
    static List<List<int> > adj = new List<List<int> >();
 
    // Function to perform the DFS traversal
    // of the N-ary tree using the given
    // pointer to the root node of the tree
    static void DFS(Node node)
    {
        foreach(Node x in node.child)
        {
            if (x != null) {
                // Insert the pair of vertices
                // into the adjacency list
                adj[node.data].Add(x.data);
                adj[x.data].Add(node.data);
                // Recursive call for DFS on x
                DFS(x);
            }
        }
    }
 
    // Function to print the level order
    // traversal of the given tree with
    // s as root node
    static void LevelOrderTrav(int s, int N)
    {
        // Create a queue for Level
        // Order Traversal
        Queue<int> q = new Queue<int>();
        // Stores if the current
        // node is visited
        bool[] visited = new bool[N + 1];
 
        q.Enqueue(s);
        // -1 marks the end of level
        q.Enqueue(-1);
        visited[s] = true;
        while (q.Count > 0) {
            int v = q.Dequeue();
            if (v == -1) {
                if (q.Count > 0)
                    q.Enqueue(-1);
                Console.WriteLine();
                continue;
            }
            // Print current vertex
            Console.Write(v + " ");
            // Add the child vertices of
            // the current node in queue
            foreach(int u in adj[v])
            {
                if (!visited[u]) {
                    visited[u] = true;
                    q.Enqueue(u);
                }
            }
        }
    }
 
    // Driver code
    public static void Main(string[] args)
    {
        // Building the tree
        Node root = new Node(1);
        root.child.Add(new Node(2));
        root.child.Add(new Node(3));
        root.child.Add(new Node(4));
        root.child.Add(new Node(5));
        root.child[0].child.Add(new Node(6));
        root.child[0].child.Add(new Node(7));
        root.child[2].child.Add(new Node(8));
        root.child[3].child.Add(new Node(9));
        root.child[3].child.Add(new Node(10));
        root.child[3].child.Add(new Node(11));
        int N = 11;
        int K = 5;
        for (int i = 0; i <= N; i++)
            adj.Add(new List<int>());
 
        // Function calls
        DFS(root);
        LevelOrderTrav(K, N);
    }
}

Javascript

       // JavaScript code for the above approach
       // A class to represent a tree node
       class Node {
           constructor(data) {
               this.data = data;
               this.children = [];
           }
       }
 
       // Adjacency list to store the tree
       const adj = [];
 
       // Function to perform the DFS traversal
       // of the N-ary tree using the given
       // pointer to the root node of the tree
       function DFS(node) {
           // Traverse all children of node
           for (const child of node.children) {
               if (child != null) 
               {
                
                   // Insert the pair of vertices
                   // into the adjacency list
                   adj[node.data].push(child.data);
                   adj[child.data].push(node.data);
 
                   // Recursive call for DFS on child
                   DFS(child);
               }
           }
       }
 
       // Function to print the level order
       // traversal of the given tree with
       // s as root node
       function levelOrderTrav(s, N)
       {
        
           // Create a queue for Level
           // Order Traversal
           const q = [];
 
           // Stores if the current
           // node is visited
           const visited = new Array(N).fill(false);
 
           q.push(s);
 
           // -1 marks the end of level
           q.push(-1);
           visited[s] = true;
           while (q.length > 0) {
               // Dequeue a vertex from queue
               const v = q.shift();
 
               // If v marks the end of level
               if (v === -1) {
                   if (q.length > 0) {
                       q.push(-1);
                   }
 
                   // Print a newline character
                   document.write("<br>");
                   continue;
               }
 
               // Print current vertex
               document.write(v + " ");
 
               // Add the child vertices of
               // the current node in queue
               for (const u of adj[v]) {
                   if (!visited[u]) {
                       visited[u] = true;
                       q.push(u);
                   }
               }
           }
       }
 
       // Create the N-ary tree
       const root = new Node(1);
       root.children.push(new Node(2));
       root.children.push(new Node(3));
       root.children.push(new Node(4));
       root.children.push(new Node(5));
       root.children[0].children.push(new Node(6));
       root.children[0].children.push(new Node(7));
       root.children[2].children.push(new Node(8));
       root.children[3].children.push(new Node(9));
       root.children[3].children.push(new Node(10));
       root.children[3].children.push(new Node(11));
       const N = 11;
       const K = 5;
 
       // Initialize the adjacency list
       for (let i = 0; i <= N; i++) {
           adj.push([]);
       }
 
       // Perform DFS on the tree
       DFS(root);
 
       // Print the tree in level order traversal
       levelOrderTrav(5, 11);
 
// This code is contributed by Potta Lokesh.

Output:

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!