N-ary Tree Preorder Traversal

easy tree dfs

Problem

Given the root of an n-ary tree, return the preorder traversal of its nodes' values — visit the root, then recurse into each child left-to-right.

Inputroot = [1, null, 3, 2, 4, null, 5, 6] // level-order with null separators

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

Each child list is exhausted before moving to the next sibling.

tree (parent:children;..., e.g. "1:3,2,4; 3:5,6")

def preorder(root):
    out = []
    def dfs(node):
        if not node:
            return
        out.append(node.val)
        for c in node.children:
            dfs(c)
    dfs(root)
    return out

function preorder(root) {
  const out = [];
  function dfs(node) {
    if (!node) return;
    out.push(node.val);
    for (const c of node.children) dfs(c);
  }
  dfs(root);
  return out;
}

class Solution {
    public List<Integer> preorder(Node root) {
        List<Integer> out = new ArrayList<>();
        dfs(root, out);
        return out;
    }
    private void dfs(Node node, List<Integer> out) {
        if (node == null) return;
        out.add(node.val);
        for (Node c : node.children) dfs(c, out);
    }
}

vector<int> preorder(Node* root) {
    vector<int> out;
    function<void(Node*)> dfs = [&](Node* node) {
        if (!node) return;
        out.push_back(node->val);
        for (auto* c : node->children) dfs(c);
    };
    dfs(root);
    return out;
}

Explanation

Pre-order means a node is recorded before any of its children. The rule is tiny: emit the node first, then recurse into each child left-to-right.

The function dfs(node) runs out.push(node.val) right away, then loops over node.children and recurses into each. Because the node is added before the loop, parents always show up ahead of their descendants.

This gives a natural top-down order: you see the root, then fully explore its first child's subtree, then the next child's subtree, and so on.

Example: root 1 with children 3, 2, 4, where 3 has children 5, 6. We emit 1, then dive into 3 and emit it, then its children 5 and 6, then back up to 2 and 4 — giving [1, 3, 5, 6, 2, 4].

Each node is touched exactly once, and the recursion stack only ever holds the chain of ancestors of the current node.

Time: O(n) Space: O(h) recursion stack