N-ary Tree Postorder Traversal

easy tree dfs

Problem

Given the root of an n-ary tree, return the postorder traversal of its nodes' values — recurse into each child left-to-right first, then emit the node's value.

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

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

Each subtree is fully processed before its root is emitted.

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

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

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

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

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

Explanation

Post-order means a node is recorded only after all of its children are done. The whole solution is one small recursive rule: visit every child first, then emit the node itself.

The function dfs(node) loops over node.children and recurses into each one left-to-right. Crucially, the line out.append(node.val) comes after that loop, so the node is added last among its own subtree.

This naturally produces a bottom-up order: the deepest leaves get written out first, and each parent appears right after its full group of descendants.

Example: with root 1 having children 3, 2, 4 and 3 having children 5, 6, we dive into 3 first, emit 5 and 6, then 3, then 2, then 4, and finally 1 — giving [5, 6, 3, 2, 4, 1].

Each node is visited once, and the recursion stack mirrors the path from the root down to wherever we currently are.

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