DSA SheetEasy
EditorialPractice

BINARY TREE › N-ARY TREE

N-ary Tree Postorder Traversal

EasyEditorial · 8 minGenerated by gpt-5.6-luna · Aug 20

Open — the attempt gate is not wired up yet

This editorial is meant to unlock after you have run the problem at least once, with the worked solution behind one further deliberate click. That needs per-learner unlock state nothing stores today, so for now the whole article is open.

Try it yourself first →

Intuitionthe definition already gives the traversal order

Postorder has one rule: a node is recorded only after all of its children have been recorded. For an n-ary node, apply that rule to every child from left to right. Each child is itself the root of another n-ary subtree, so the same instruction repeats until a leaf has no children left to visit.

The serialized input uses null as a boundary between child groups. After creating the root, process nodes in a queue. For each queued node, every value before the next null is one of its children, and each newly created child joins the queue so its own group can be parsed later. Once the tree exists, postorder is a direct depth-first traversal.

An n-ary tree and its level-order serializationThe picture places the root at the top and its children below it from left to right. Beside the tree, a level-order sequence shows a run of child values followed by null; the null is drawn as a boundary before the next parent's child group. A queue contains nodes waiting for their own groups to be read. A traversal path finishes each lower subtree before marking its parent, making the child-before-parent rule visible.ABCDABCDnullBCDBCDAlevel-order serializationroot: first parsednull ends this child groupqueue: pending child groupsA's children: B, C, Dpostorder pathleft-to-right subtrees complete before the parent is recorded
The null separators describe groups during parsing; they do not appear in the traversal result.

Approachbuild the tree once, then apply the definition

  1. Return an empty vector for null or an empty bracketed input, because there is no root from which either parsing or traversal can begin.
  2. Remove the outer brackets and split the remaining text at commas, trimming spaces from each token so numeric values and null separators can be compared reliably.
  3. Create the first numeric token as the root and put it in a queue, because level order tells you which node's child group must be read next.
  4. Take one node from the queue and consume tokens until null. Create each numeric token as a child, append it to that node's children, and enqueue it so its own children will be parsed later; stopping at null prevents the next group from being attached to the wrong parent.
  5. Skip the null separator and continue until every queued node has been processed. Without advancing past the separator, the next node would appear to have an empty group even when it has children.
  6. Run a recursive postorder walk from the root. Visit every child in stored left-to-right order before pushing the current node's value, because moving the push above the child loop changes the result to preorder.
  7. Return the result vector after the walk finishes, since every node has then been recorded exactly once and no separate reordering step is needed.

Complexityparsing and traversal together

MEASUREBOUNDWHY
TimeO(n)Parsing examines each serialized token once, creates each node once, and traversing follows each child edge once before recording each node. The parsing queue and traversal do not revisit a completed node, so the total work is linear in the tree size.
SpaceO(n) extraThe returned vector is required output and is excluded. The token list, allocated tree, parsing queue, and recursion stack use O(n) extra space; the stack itself is O(h), which becomes O(n) for a chain-shaped tree, the worst possible shape.
Here n is the number of tree nodes and h is the tree height, measured as the maximum number of nodes on a root-to-leaf path.

Annotated solutionC++ · recursive traversal with level-order parsing

CPPParse each null-terminated child group, then recurse through children before appending the node.
#include <queue>
#include <sstream>
#include <string>
#include <vector>
using namespace std;

struct Node {
    int val;
    vector<Node*> children;

    Node(int value) : val(value) {}
};

class Solution {
public:
    vector<int> postorder(string root) {
        if (root == "null" || root == "[]") {
            return {};
        }

        vector<string> tokens = splitTokens(root);
        if (tokens.empty() || tokens[0] == "null") {
            return {};
        }

        Node* rootNode = new Node(stoi(tokens[0]));
        queue<Node*> pending;
        pending.push(rootNode);

        int index = 1;
        while (!pending.empty() && index < static_cast<int>(tokens.size())) {
            Node* current = pending.front();
            pending.pop();

            while (index < static_cast<int>(tokens.size()) &&
                   tokens[index] != "null") {
                Node* child = new Node(stoi(tokens[index]));
                current->children.push_back(child);
                pending.push(child);
                ++index;
            }

            if (index < static_cast<int>(tokens.size()) &&
                tokens[index] == "null") {
                ++index;
            }
        }

        vector<int> result;
        walk(rootNode, result);
        return result;
    }

private:
    vector<string> splitTokens(const string& root) {
        string inside = root.substr(1, root.size() - 2);
        vector<string> tokens;
        string token;
        stringstream stream(inside);

        while (getline(stream, token, ',')) {
            size_t first = token.find_first_not_of(' ');
            size_t last = token.find_last_not_of(' ');
            if (first == string::npos) {
                tokens.push_back("");
            } else {
                tokens.push_back(token.substr(first, last - first + 1));
            }
        }
        return tokens;
    }

    void walk(Node* node, vector<int>& result) {
        if (node == nullptr) {
            return;
        }

        for (Node* child : node->children) {
            walk(child, result);
        }
        result.push_back(node->val);
    }
};

The queue is used only while decoding the string. It separates the input format from the traversal logic: once every child pointer is attached, the traversal never needs to know where a null appeared. In walk, the loop must come before result.push_back. That placement is the entire postorder guarantee, while the null guard makes the same helper safe for every child call.

The iterative alternativethe stack replaces recursive call frames, not the parsing work

You can avoid recursion by first producing a root-right-to-left order with one stack, then reversing it. Push children from left to right; because a stack removes the last pushed child first, the next subtree processed is the rightmost one. Reversing the complete sequence restores left-to-right children with each parent after its children. This is an alternative arrangement, not an asymptotic optimisation: both versions use O(n) extra space overall.

CPPUse a stack for root-right-to-left processing, then reverse the values into postorder.
#include <algorithm>
#include <queue>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
using namespace std;

struct Node {
    int val;
    vector<Node*> children;

    Node(int value) : val(value) {}
};

class Solution {
public:
    vector<int> postorder(string root) {
        if (root == "null" || root == "[]") {
            return {};
        }

        vector<string> tokens = splitTokens(root);
        if (tokens.empty() || tokens[0] == "null") {
            return {};
        }

        Node* rootNode = new Node(stoi(tokens[0]));
        queue<Node*> pending;
        pending.push(rootNode);

        int index = 1;
        while (!pending.empty() && index < static_cast<int>(tokens.size())) {
            Node* current = pending.front();
            pending.pop();

            while (index < static_cast<int>(tokens.size()) &&
                   tokens[index] != "null") {
                Node* child = new Node(stoi(tokens[index]));
                current->children.push_back(child);
                pending.push(child);
                ++index;
            }

            if (index < static_cast<int>(tokens.size()) &&
                tokens[index] == "null") {
                ++index;
            }
        }

        vector<int> result;
        stack<Node*> pendingTraversal;
        pendingTraversal.push(rootNode);

        while (!pendingTraversal.empty()) {
            Node* node = pendingTraversal.top();
            pendingTraversal.pop();
            result.push_back(node->val);

            for (Node* child : node->children) {
                pendingTraversal.push(child);
            }
        }

        reverse(result.begin(), result.end());
        return result;
    }

private:
    vector<string> splitTokens(const string& root) {
        string inside = root.substr(1, root.size() - 2);
        vector<string> tokens;
        string token;
        stringstream stream(inside);

        while (getline(stream, token, ',')) {
            size_t first = token.find_first_not_of(' ');
            size_t last = token.find_last_not_of(' ');
            if (first == string::npos) {
                tokens.push_back("");
            } else {
                tokens.push_back(token.substr(first, last - first + 1));
            }
        }
        return tokens;
    }
};

Common mistakestwo lines that change the meaning of the input or traversal

Previous · N-ary Tree