Vultr DocsLatest Content

N-ary Tree Level Order Traversal

Updated on 27 June, 2025
N-ary Tree Level Order Traversal header image

Problem Statement

In the problem at hand, we need to perform a level order traversal on an n-ary tree, where each node can have more than two children. Level order traversal, also known as breadth-first traversal, involves visiting all the nodes at the present depth prior to moving on to nodes at the next level of depth. The given n-ary trees are described using a serialization method where children of a node are denoted by subsequent values followed by a 'null' value indicating the end of a particular level or branch. The challenge thus revolves around correctly parsing this structure and retrieving values in the specified order.

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]

Approach and Intuition

  1. Interpret the serialized n-ary tree structure:

    • The serialization format splits nodes and their respective children by a 'null' value. This formatting helps indicate transitions between levels of the n-ary tree.

  2. Implement BFS (Breadth-First Search) using a queue:

    • A queue can be utilized effectively here for visiting nodes layer by layer. Starting from the root node, enqueue it.
    • Process each node by dequeuing it, recording its value, and enqueueing all its children. This processing is continued until the queue is empty.
    • The main loop runs while the queue has elements, ensuring that each level is completely processed before moving to the next.

  3. Handle edge cases:

    • The tree could be empty, represented by an empty serialization, in which case the output should be an empty list as well.

Based on the problem description and the constraints provided (an n-ary tree with the height of up to 1000 and up to 10^4 nodes), the proposed breadth-first search approach should handle the typical cases efficiently, considering modern compute capacities.

Solutions

  • Java
  • Python
java 
class Solution {
    
    private List<List<Integer>> levels = new ArrayList<>();
    
    public List<List<Integer>> levelOrder(Node root) {
        if (root != null) {
            processNode(root, 0);
        }
        return levels;
    }
    
    private void processNode(Node node, int depth) {
        if (levels.size() <= depth) {
            levels.add(new ArrayList<>());
        }
        levels.get(depth).add(node.val);
        for (Node child : node.children) {
            processNode(child, depth + 1);
        }
    }
}

The provided Java solution implements an N-ary Tree Level Order Traversal using a recursive approach. Here's how the traversal process works:

  • Define a private List of List of integers (levels) to store the values of the tree nodes at each level.
  • Implement a public levelOrder method which initiates the traversal:
    • Check if the root is not null, then start processing from the root.
    • Return the levels list which contains the values of each level.
  • Detail a private processNode method:
    • Ensure the list for the current depth is created if it does not exist.
    • Add the node's value to the appropriate level in levels.
    • Iterate over each child of the current node and recursively call processNode for each child, increasing the depth by 1.

This approach ensures that the tree is traversed level by level and the values are stored in a list corresponding to their depth from the root. This is an effective way to perform level order traversal on a tree with any number of children per node.

python 
class Solution:
    def traverse_levels(self, start: Optional['Node']) -> List[List[int]]:
    
        def process_node(current_node, current_depth):
            if len(levels) == current_depth:
                levels.append([])
            levels[current_depth].append(current_node.val)
            for child in current_node.children:
                process_node(child, current_depth + 1)
    
        levels = []
    
        if start is not None:
            process_node(start, 0)
        return levels

This Python solution performs a level order traversal on an N-ary tree, returning the values of the nodes grouped by their depth levels. This approach utilizes a recursive helper function process_node to explore each node and its children. The core mechanism of the solution involves the following steps:

  1. Define the recursive function process_node which:

    • Checks if the current depth is represented within levels. If not, a new sublist is created.
    • Appends the current node's value to the respective sublist of levels.
    • Recursively calls itself for each of the node's children, increasing the depth by one for each call.

  2. Initialize the levels list which will store the values of nodes at each depth level.

  3. Execute the recursive function starting from the tree's root node if it is not None.

  4. Return the levels list which now contains the node values arranged level-wise. This method ensures all nodes at the same depth are grouped together, facilitating a clear and organized traversal of the tree structure.

Comments

No comments yet.