# N-ary Tree Level Order Traversal Solution Python C++

N-Ary Tree level Order Traversal is a very frequently asked question in the Coding Interview Question. It tests your knowledge related to Bread First Search if the question is asked to be solved using the iteration method.

Otherwise, if the interview asked you to solve using DFS, you need to solve it using recursion. In this post, I will discuss the most efficient solution you can come up with to solve this question in Python, C++, or any other language you want.

You can also find this question on popular interview websites such as LeetCode, InterviewBit, and Hackerrank.

Given an n-ary tree, return the level order traversal of its nodes’ values.

Nary-Tree input serialization is represented in their level order traversal, each group of children is separated by the null value (See examples).

Example 1:

```Input: root = [1,null,3,2,4,null,5,6]
Output: [,[3,2,4],[5,6]]
```

Example 2:

```Input: root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
Output: [,[2,3,4,5],[6,7,8,9,10],[11,12,13],]
```

Constraints:

• The height of the n-ary tree is less than or equal to `1000`
• The total number of nodes is between `[0, 104]`

## Solution: Algorithm and Code in C++ (Iterative)

To solve this interview question using the iterative method, you need to use the Breadth-First Search method.

You need to use a queue to store the nodes. And you need to keep on poping the front node of the queue and pushing the children of the root unless the queue becomes empty in the end. And Meanwhile adding all the elements in the vector in a level order manner.

```//This Solution is Lengthy but It is the fastest.
/*
// Definition for a Node.
class Node {
public:
int val;
vector<Node*> children;

Node() {}

Node(int _val) {
val = _val;
}

Node(int _val, vector<Node*> _children) {
val = _val;
children = _children;
}
};
*/

class Solution {
public:
vector<vector<int>> levelOrder(Node* root) {
if(!root) return {};
int lvl=0;
int lvltmp = 1;
queue<Node*> getQueue;
getQueue.push(root);
vector<vector<int>> ans;
vector<int> initial;
while(!getQueue.empty()){
Node* getTmpRoot = getQueue.front();
getQueue.pop();
lvltmp--;
initial.push_back(getTmpRoot->val);
if(!getTmpRoot->children.size()==0)
lvl += getTmpRoot->children.size();
int i=0;
while(i<getTmpRoot->children.size()){
getQueue.push(getTmpRoot->children[i]);
i++;
}
if(lvltmp==0){
ans.push_back(initial);
initial.clear();
lvltmp = lvl;
lvl = 0;
}
}
return ans;
}
};```

Runtime Analysis: As taken from LeetCode you can find the efficiency of the above code below the image.

Below is the Cleanest and Easiest to understand Code but not as efficient as the above one.

```/*
// Definition for a Node.
class Node {
public:
int val;
vector<Node*> children;

Node() {}

Node(int _val) {
val = _val;
}

Node(int _val, vector<Node*> _children) {
val = _val;
children = _children;
}
};
*/

class Solution {
public:
vector<vector<int>> levelOrder(Node* root) {
if(!root) return {};
queue<Node*> getQueue;
getQueue.push(root);
vector<vector<int>> level;
while(!getQueue.empty()){
level.emplace_back();
for(int i=getQueue.size();i>0;--i){
Node* getTmpNodeRoot = getQueue.front();
getQueue.pop();
level.back().push_back(getTmpNodeRoot->val);
for(Node* child:getTmpNodeRoot->children){
getQueue.push(child);
}
}

}
return level;
}
};```

Runtime Analysis: The Runtime Analysis of the above cleanest code is as displayed in the image below. Note that this code is running a little slow. This can be we are changing the size of the queue in each iteration that might be taking a lot of time.

You Can find the Python Solution for this question below as well.

```class Solution:
def levelOrder(self, root: 'Node') -> List[List[int]]:
if root == None: return []
getQueue = deque([root])
ans = []
while getQueue:
level = []
for _ in range(len(getQueue)):
curr = getQueue.popleft()
level.append(curr.val)
for child in curr.children:
getQueue.append(child)
ans.append(level)
return ans```

## N-ary Tree Level Order Traversal Solution: Depth First Search (Recursive)

Below is the code to solve this problem in a recursive manner. Here DFS is used to get the level order solution for the problem.

```class Solution:
def levelOrder(self, root: 'Node') -> List[List[int]]:
def depthFirstSearch(root, level):
if root == None: return
if level == len(ans):
ans.append([])
ans[level].append(root.val)
for child in root.children:
depthFirstSearch(child, level + 1)

ans = []
depthFirstSearch(root, 0)
return ans```

That is all for the solution for N-ary Tree Level Order Traversal. For more interview-related questions please keep visiting my website. We keep on adding new programming-related tutorials weekly.