Scale Engineer

N-ary Tree Level Order Traversal

Med
#0416Time: 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.
Algorithms
Breadth-First Search
Data structures
Tree

Prompt

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, 104]

Approaches

2 approaches with complexity analysis and trade-offs.

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.

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).

Walkthrough

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.

/*// 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);        }    }}

Complexity

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.

Trade-offs

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.

Solutions

/* // 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 ; } }

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem