N-ary Tree Preorder Traversal

Given the root of an n-ary tree, return the preorder 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,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.

Follow up: Recursive solution is trivial, could you do it iteratively?

Approach: Iterative with a Stack (Reverse Children Order)

Algorithm

1. In preorder, visit a node, then traverse all of its children from left to right
2. Push the root onto a stack and loop while the stack is not empty
3. Pop a node and add its value to the result
4. Push the node’s children onto the stack in reverse order, so the leftmost child ends up on top and is popped first
5. Repeat until every node has been visited

Time & Space Complexity

• Time Complexity: O(n) - every node is pushed and popped exactly once
• Space Complexity: O(n) - the stack can hold up to O(n) nodes in the worst case

Java Implementation

import java.util.ArrayList;
import java.util.Collections;
import java.util.Deque;
import java.util.ArrayDeque;
import java.util.List;

public class NaryTreePreorderTraversal {

    public static List<Integer> preorder(Node root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) {
            return result;
        }
        Deque<Node> stack = new ArrayDeque<>();
        stack.push(root);

        while (!stack.isEmpty()) {
            Node node = stack.pop();
            result.add(node.val);
            List<Node> children = node.children;
            for (int i = children.size() - 1; i >= 0; i--) {
                stack.push(children.get(i));
            }
        }
        return result;
    }

    public static class Node {
        public int val;
        public List<Node> children;

        public Node() {}

        public Node(int val) {
            this.val = val;
        }

        public Node(int val, List<Node> children) {
            this.val = val;
            this.children = children;
        }
    }

    // Test method
    public static void main(String[] args) {
        Node n5 = new Node(5);
        Node n6 = new Node(6);
        Node n3 = new Node(3, new ArrayList<>(List.of(n5, n6)));
        Node n2 = new Node(2);
        Node n4 = new Node(4);
        Node root = new Node(1, new ArrayList<>(List.of(n3, n2, n4)));

        System.out.println("Input: root = [1,null,3,2,4,null,5,6]");
        System.out.println("Output: " + preorder(root)); // Expected: [1, 3, 5, 6, 2, 4]
    }
}

Recursive Implementation

public List<Integer> preorderRecursive(Node root) {
    List<Integer> result = new ArrayList<>();
    helper(root, result);
    return result;
}

private void helper(Node node, List<Integer> result) {
    if (node == null) {
        return;
    }
    result.add(node.val);
    for (Node child : node.children) {
        helper(child, result);
    }
}

Example Walkthrough

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

1. Push 1. Pop 1 -> result [1], push children in reverse: 4, 2, 3 (top is 3)
2. Pop 3 -> result [1, 3], push children in reverse: 6, 5 (top is 5)
3. Pop 5 -> result [1, 3, 5]; pop 6 -> result [1, 3, 5, 6]
4. Pop 2 -> result [1, 3, 5, 6, 2]; pop 4 -> result [1, 3, 5, 6, 2, 4]

Key Points

1. Parent Before Children: A node’s value is always added before any of its descendants
2. Reverse Push Order: Children are pushed in reverse so the leftmost child is processed first
3. n-ary vs Binary: The same stack idea as binary preorder, extended to an arbitrary number of children
4. Edge Cases: A null root returns an empty list
5. O(n) Time: Every node is visited exactly once