589 · N-ary Tree Preorder Traversal

The binary preorder you already know, with node.left and node.right replaced by a loop over node.children. Nothing about the order changes — a node is still visited before any of its descendants — only the number of branches does. The one detail worth slowing down for is the iterative version's reversed push.

1 — The problem

Given the root of an N-ary tree, return the preorder traversal of its nodes' values. Each node carries a List<Node> children instead of two fixed slots, and that list is simply empty at a leaf — so unlike the binary case there is no null child to guard against inside the loop. The only null check you need is on the root itself.

The example tree throughout this page is LeetCode's [1,null,3,2,4,null,5,6]: root 1 with children 3, 2, 4, and 3 in turn with children 5 and 6. The expected answer is [1,3,5,6,2,4].

2 — Recursive

The visit line sits before the loop. That single placement is what makes this preorder; move it after the loop and you have 590.

void dfs(Node nd, List<Integer> out) {    if (nd == null) return;    out.add(nd.val);                  // visit on the way IN    for (Node c : nd.children) dfs(c, out);}

Watch the call stack: 1 stays open for the entire traversal, because it cannot finish until every one of its three subtrees has. The output, though, recorded it immediately — visiting early and finishing late are independent, and that gap is the whole idea behind preorder.

3 — Iterative, with an explicit stack

Replace the call stack with a real one. Pop a node, output it, push its children — but push them in reverse.

Deque<Node> st = new ArrayDeque<>();st.push(root);while (!st.isEmpty()) {    Node nd = st.pop();    out.add(nd.val);    for (int i = nd.children.size() - 1; i >= 0; i--)        st.push(nd.children.get(i));  // reverse: leftmost ends up on top}

The reversal is not decoration. A stack is last-in-first-out, so whichever child you push last comes off first. Pushing 3, 2, 4 in natural order would pop 4 next and produce [1,4,2,...] — a valid depth-first walk, but not the preorder the problem asks for. Pushing 4, 2, 3 puts 3 on top, which is what you want. In the binary version this is the familiar "push right, then left"; here it is the same rule stated as a backwards loop.

4 — Complexity and edge cases

• Time: O(n) — each node is visited once and each child reference is followed once.
• Space: O(h) for the recursion, where h is the height. For the iterative version the stack can hold up to O(n) in the worst case: a root with n − 1 children puts all of them on the stack at once, which a binary tree can never do.
• Empty root: return an empty list; guard before the first push, or st.push(root) will seed the loop with null.
• A leaf: children is an empty list, not null — the for loop simply doesn't run, so no special case is needed.
• Deep, narrow trees are the recursion's failure mode; wide, shallow ones are the explicit stack's. Neither is a concern at LeetCode's limits.

5 — Reference implementations

public List<Integer> preorder(Node root) {
    List<Integer> out = new ArrayList<>();
    dfs(root, out);
    return out;
}

private void dfs(Node nd, List<Integer> out) {
    if (nd == null) return;
    out.add(nd.val);                        // visit on the way in
    for (Node c : nd.children) dfs(c, out);
}

public List<Integer> preorder(Node root) {
    List<Integer> out = new ArrayList<>();
    if (root == null) return out;
    Deque<Node> st = new ArrayDeque<>();
    st.push(root);
    while (!st.isEmpty()) {
        Node nd = st.pop();
        out.add(nd.val);
        for (int i = nd.children.size() - 1; i >= 0; i--) {
            st.push(nd.children.get(i));    // reverse — leftmost must land on top
        }
    }
    return out;
}

If this felt like a re-run of 144, that is the correct reaction — and the reason this problem is optional. Solve it only if the generalisation from two children to a list wasn't already obvious.