N-ary Tree Preorder Traversal

Problem Statement

In this problem, we are dealing with an n-ary tree where each node can have multiple children. The task is to perform a preorder traversal of the tree and return the values of the nodes. Preorder traversal is a type of depth-first traversal where the node is processed before its children.

The n-ary tree is given in a serialized form following the level order traversal. The serialization distinguishes between different levels of children using a null value. Your function will take the root of the tree as input and should output a list representing the preorder traversal of the tree nodes.

Examples

Example 1

Input:

root = [1,null,3,2,4,null,5,6]

Output:

[1,3,5,6,2,4]

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,6,7,11,14,4,8,12,5,9,13,10]

Constraints

• The number of nodes in the tree is in the range [0, 104].
• 0 <= Node.val <= 104
• The height of the n-ary tree is less than or equal to 1000.

Approach and Intuition

The problem of performing a preorder traversal on an n-ary tree can be approached both recursively and iteratively.

1. Recursive Approach:

   • Start from the root and process the node's value.
   • Recurse over each child of the node and repeat the process. The children are visited in the order they appear.

   The recursive approach aligns intuitively with the definition of preorder traversal, which is to process the node itself followed by recursively processing the children from left to right.

2. Iterative Approach using a Stack:

   • Initialize a stack with the root node.
   • While the stack is not empty, pop the top node, process it, and push its children onto the stack in reverse order (rightmost child pushed first). This ensures that when popped, the leftmost child is processed before the rightmost child.
   • Continue this process until all nodes have been processed and the stack is empty.

   The use of a stack helps simulate the recursive calls of preorder traversal in an iterative manner. The aim is to process each node and then its children from left to right, which is achieved by controlling the order of nodes placed in the stack.

• Input Management:
  • The serialization of n-ary trees uses null values to represent boundaries between levels or children groups, important to structure the tree correctly before traversal.

The traversal of an n-ary tree, requires considering all direct children of each node, which makes the preorder traversal particularly well-suited, as it inherently starts processing from the root, moving downwards and leftwards recursively or iteratively, ensuring all nodes are accessed in the required order.

Solutions

class Solution {
  public List<Integer> getPreorder(Node rootNode) {
    LinkedList<Node> nodeStack = new LinkedList<>();
    LinkedList<Integer> traversalResult = new LinkedList<>();
    if (rootNode == null) {
      return traversalResult;
    }
    
    nodeStack.add(rootNode);
    while (!nodeStack.isEmpty()) {
      Node currentNode = nodeStack.pollLast();
      traversalResult.add(currentNode.val);
      Collections.reverse(currentNode.children);
      for (Node childNode : currentNode.children) {
        nodeStack.add(childNode);
      }
    }
    return traversalResult;
  }
}