# N-ary Tree Level Order Traversal
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/n-ary-tree-level-order-traversal)
Canonical: https://scaleengineer.com/dsa/problems/n-ary-tree-level-order-traversal
**Algorithms:** [Breadth-First Search](https://scaleengineer.com/algorithms/breadth-first-search)
**Data structures:** Tree
---
## Problem
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:**

![](https://assets.glich.co/dsa/n-ary-tree-level-order-traversal/image0.png)

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

**Example 2:**

![](https://assets.glich.co/dsa/n-ary-tree-level-order-traversal/image1.png)

**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]`

# Approaches
## Recursive Depth-First Search (DFS)
This approach uses recursion to traverse the tree. A helper function is defined which takes the current node and its level as arguments. We build the result list level by level as we traverse down the tree.
**Time:** O(N), where N is the total number of nodes in the tree. This is because we visit each node exactly once. · **Space:** O(H), where H is the height of the tree. This space is used by the recursion call stack. In the worst-case scenario of a skewed tree (like a linked list), the height H can be equal to N, leading to O(N) space complexity. This does not include the space for the output list.
**Pros:** The code is often shorter and can be more intuitive to write for those comfortable with recursion.; It follows a natural tree traversal pattern.
**Cons:** Can lead to a `StackOverflowError` if the tree is very deep.; The space complexity is dependent on the height of the tree, which can be O(N) in the worst case.
### Explanation
The core idea is to perform a preorder traversal (or any DFS traversal) of the tree while keeping track of the current depth or level. We use a list of lists to store the final result.

When we visit a node at a certain `level`, we check if our result list has an entry for that level yet.
- If `result.size() == level`, it means we are visiting this level for the first time. We create a new list for this level and add it to our result list.
- Then, we add the current node's value to the list corresponding to its level: `result.get(level).add(node.val)`.
- Finally, we make recursive calls for all the children of the current node, incrementing the level by one for each call.

The process starts by calling the helper function with the root node at level 0.

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

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, List<Node> _children) {
        val = _val;
        children = _children;
    }
};
*/
class Solution {
    public List<List<Integer>> levelOrder(Node root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) {
            return result;
        }
        dfs(root, 0, result);
        return result;
    }

    private void dfs(Node node, int level, List<List<Integer>> result) {
        if (result.size() == level) {
            result.add(new ArrayList<>());
        }
        
        result.get(level).add(node.val);
        
        for (Node child : node.children) {
            dfs(child, level + 1, result);
        }
    }
}
```
### Algorithm
- Create a main list `result` to store the lists of node values for each level.
- If the `root` is `null`, return the empty `result` list.
- Call a recursive helper function, say `dfs(node, level, result)` with `root`, `0`, and `result`.
- In the `dfs` function:
  - a. If the current `level` is equal to the size of the `result` list, it implies we've reached a new level. Create a new empty list and add it to `result`.
  - b. Add the current `node.val` to the list at index `level` in `result`.
  - c. Iterate through the `children` of the current `node` and for each `child`, recursively call `dfs(child, level + 1, result)`.

## Iterative Breadth-First Search (BFS) with a Queue
This is the classic and most direct approach for level order traversal. It uses a queue to keep track of nodes to visit. We process the tree level by level, and for each level, we iterate through all the nodes at that level, adding their children to the queue for the next level's processing.
**Time:** O(N), where N is the total number of nodes. Each node is enqueued and dequeued exactly once. · **Space:** O(W), where W is the maximum width (maximum number of nodes at any single level) of the tree. This space is required for the queue. In the worst case, for a complete N-ary tree, the last level can contain a large number of nodes, and W can be close to N. For example, a star graph with one root and N-1 children has a width of N-1, leading to O(N) space complexity.
**Pros:** It's the canonical approach for level-order traversal and is generally more intuitive for this specific problem.; Avoids potential stack overflow issues that can occur with deep recursion.; Space complexity is proportional to the tree's width, which can be more efficient than the DFS approach for deep, narrow trees.
**Cons:** Can be less space-efficient than the recursive DFS approach for very wide, shallow trees, although both can be O(N) in their respective worst cases.
### Explanation
We use a queue data structure, which is perfect for BFS.

1. Initialize an empty queue and add the `root` node to it.
2. While the queue is not empty, we process one level at a time.
3. To process a level, we first find out how many nodes are in the queue (`levelSize = queue.size()`). These are all the nodes for the current level.
4. We create a new list, `currentLevel`, to store the values of the nodes at this level.
5. We then loop `levelSize` times. In each iteration, we dequeue a node, add its value to the `currentLevel` list, and then enqueue all of its children.
6. After the inner loop finishes, `currentLevel` contains all node values for that level, and the queue contains all the nodes for the *next* level. We add `currentLevel` to our final result list.
7. We repeat this process until the queue becomes empty.

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

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, List<Node> _children) {
        val = _val;
        children = _children;
    }
};
*/
class Solution {
    public List<List<Integer>> levelOrder(Node root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) {
            return result;
        }

        Queue<Node> queue = new LinkedList<>();
        queue.add(root);

        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            List<Integer> currentLevel = new ArrayList<>();
            for (int i = 0; i < levelSize; i++) {
                Node currentNode = queue.poll();
                currentLevel.add(currentNode.val);
                for (Node child : currentNode.children) {
                    queue.add(child);
                }
            }
            result.add(currentLevel);
        }

        return result;
    }
}
```
### Algorithm
- Create a main list `result` to store the final output.
- If `root` is `null`, return the empty `result` list.
- Initialize a `Queue` and add the `root` node to it.
- Loop as long as the `queue` is not empty:
  - a. Get the number of nodes at the current level: `levelSize = queue.size()`.
  - b. Create a new list `currentLevel` to store node values for this level.
  - c. Loop `levelSize` times:
     - i. Dequeue a node: `currentNode = queue.poll()`.
     - ii. Add `currentNode.val` to the `currentLevel` list.
     - iii. For each `child` in `currentNode.children`, enqueue the `child` into the queue.
  - d. After the inner loop, add the `currentLevel` list to the `result` list.
- Return the `result` list.

# Solutions
### Java

```java
/* // Definition for a Node. class Node { public int val; public List<Node> children; public Node() {} public Node(int _val) { val = _val; } public Node(int _val, List<Node> _children) { val = _val; children = _children; } }; */ class Solution { public List < List < Integer >> levelOrder ( Node root ) { List < List < Integer >> ans = new ArrayList <>(); if ( root == null ) { return ans ; } Deque < Node > q = new ArrayDeque <>(); q . offer ( root ); while (! q . isEmpty ()) { List < Integer > t = new ArrayList <>(); for ( int n = q . size (); n > 0 ; -- n ) { root = q . poll (); t . add ( root . val ); q . addAll ( root . children ); } ans . add ( t ); } return ans ; } }
```

### CPP

```cpp
/* // 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 ) { vector < vector < int >> ans ; if ( ! root ) return ans ; queue < Node *> q { { root } }; while ( ! q . empty ()) { vector < int > t ; for ( int n = q . size (); n > 0 ; -- n ) { root = q . front (); q . pop (); t . push_back ( root -> val ); for ( auto & child : root -> children ) q . push ( child ); } ans . push_back ( t ); } return ans ; } };
```

### Python

```python
""" # Definition for a Node. class Node: def __init__(self, val=None, children=None): self.val = val self.children = children """ class Solution : def levelOrder ( self , root : 'Node' ) -> List [ List [ int ]]: ans = [] if root is None : return ans q = deque ([ root ]) while q : t = [] for _ in range ( len ( q )): root = q . popleft () t . append ( root . val ) q . extend ( root . children ) ans . append ( t ) return ans
```