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:

N-ary Tree Level Order Traversal
Input: root = [1,null,3,2,4,null,5,6]
Output: [[1],[3,2,4],[5,6]]

Example 2:

N-ary Tree Level Order Traversal
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, 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[1] 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.

N-ary Tree Level Order Traversal

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.

N-ary Tree Level Order Traversal

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.

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.

Wanna read more interview-related questions? Check Top Interview Questions category.


Share your love

One comment

Leave a Reply