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

N-Ary Tree level Order Traversal is a frequently asked question during a Coding Interview. It assesses your knowledge of Bread First Search by requiring you to solve the question using the iteration method.

Otherwise, if the interviewer asked you to solve it using DFS, you must use recursion. In this post, I’ll go over the most efficient way to solve this problem in Python, C++, or any other language you want.

This question can also be found 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: [[1],[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: [[1],[2,3,4,5],[6,7,8,9,10],[11,12,13],[14]]

Constraints:

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

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

You must use the Breadth-First Search method to solve this interview question iteratively.

You need to use a queue to store the nodes. And you must keep popping the front node of the queue and pushing the root’s children until the queue is empty. In the meantime, add all of the vector’s elements in level order.

//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: The efficiency of the above code, as taken from LeetCode, can be found below the image.

The code below is the cleanest and easiest to understand, but it is not as efficient as the one above.

/*
// 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 above cleanest code’s runtime analysis is shown in the image below. It’s worth noting that this code is a little sluggish. This could be due to the fact that we are changing the size of the queue in each iteration, which could take a long time.

You can also find the Python solution to this question below.

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)

The code to solve this problem in a recursive manner is provided below. DFS is used in this case to obtain the level order solution to 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 concludes the solution to the N-ary Tree Level Order Traversal problem. Please keep visiting my website for more interview-related questions. We continue to add new programming tutorials on a weekly basis.

If you liked the answer then please follow us on Facebook and Twitter. Let us know the questions and answer you want to cover in this blog.

Further Read:

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

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

Leave a Comment Cancel reply