590. N-ary Tree Postorder Traversal - Explanation

Description

You are given the root of an n-ary tree, return the postorder 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: [5,6,3,2,4,1]

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: [2,6,14,11,7,3,12,8,4,13,9,10,5,1]

Constraints:

0 <= number of nodes in the tree <= 10,000
0 <= Node.val <= 10,000
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?

Topics

Company Tags

Please upgrade to NeetCode Pro to view company tags.

Prerequisites

Before attempting this problem, you should be comfortable with:

Tree Data Structures - Understanding how N-ary trees differ from binary trees (nodes can have multiple children)
Recursion - The recursive DFS solution relies on understanding how recursive calls process children before the parent
Stack - The iterative solution uses a stack to simulate recursion and manage traversal order

1. Depth First Search

Intuition

Postorder traversal means we visit all children of a node before visiting the node itself. For an N-ary tree, this translates to recursively processing each child subtree from left to right, then adding the current node's value to the result. The recursive approach naturally handles this ordering since the node's value is appended only after all recursive calls on its children have completed.

Algorithm

Create an empty res list.
Define a recursive helper function dfs(node):
- If the node is null, return immediately.
- For each child of the node, recursively call dfs(child).
- After processing all children, append the node's value to the res list.
Call dfs(root) and return the res list.

"""
# Definition for a Node.
class Node:
    def __init__(self, val: Optional[int] = None, children: Optional[List['Node']] = None):
        self.val = val
        self.children = children
"""

class Solution:
    def postorder(self, root: 'Node') -> List[int]:
        res = []

        def dfs(node):
            if not node:
                return

            for child in node.children:
                dfs(child)
            res.append(node.val)

        dfs(root)
        return res

/*
// Definition for a Node.
class Node {
    public int val;
    public List<Node> children;

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, List<Node> _children) {
        val = _val;
        children = _children;
    }
}
*/

public class Solution {
    public List<Integer> postorder(Node root) {
        List<Integer> res = new ArrayList<>();

        dfs(root, res);
        return res;
    }

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

/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val) {
        val = _val;
    }

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};
*/

class Solution {
public:
    vector<int> postorder(Node* root) {
        vector<int> res;
        dfs(root, res);
        return res;
    }

    void dfs(Node* node, vector<int>& res) {
        if (!node) return;
        for (auto child : node->children) {
            dfs(child, res);
        }
        res.push_back(node->val);
    }
};

/**
 * Definition for a binary tree node.
 * class Node {
 *     constructor(val = 0, children = []) {
 *         this.val = val;
 *         this.children = children;
 *     }
 * }
 */
class Solution {
    /**
     * @param {Node|null} root
     * @return {number[]}
     */
    postorder(root) {
        const res = [];

        const dfs = (node) => {
            if (!node) return;
            for (let child of node.children) {
                dfs(child);
            }
            res.push(node.val);
        };

        dfs(root);
        return res;
    }
}

/*
// Definition for a Node.
public class Node {
    public int val;
    public List<Node> children;

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, IList<Node> _children) {
        val = _val;
        children = _children;
    }
}
*/

public class Solution {
    public List<int> Postorder(Node root) {
        List<int> res = new List<int>();
        Dfs(root, res);
        return res;
    }

    private void Dfs(Node node, List<int> res) {
        if (node == null) return;
        foreach (var child in node.children) {
            Dfs(child, res);
        }
        res.Add(node.val);
    }
}

/**
 * Definition for a Node.
 * type Node struct {
 *     Val int
 *     Children []*Node
 * }
 */

func postorder(root *Node) []int {
    res := []int{}

    var dfs func(node *Node)
    dfs = func(node *Node) {
        if node == nil {
            return
        }
        for _, child := range node.Children {
            dfs(child)
        }
        res = append(res, node.Val)
    }

    dfs(root)
    return res
}

/**
 * Definition for a Node.
 * class Node(var `val`: Int) {
 *     var children: List<Node?> = listOf()
 * }
 */

class Solution {
    fun postorder(root: Node?): List<Int> {
        val res = mutableListOf<Int>()

        fun dfs(node: Node?) {
            if (node == null) return
            for (child in node.children) {
                dfs(child)
            }
            res.add(node.`val`)
        }

        dfs(root)
        return res
    }
}

/**
 * Definition for a Node.
 * public class Node {
 *     public var val: Int
 *     public var children: [Node]
 *     public init(_ val: Int) {
 *         self.val = val
 *         self.children = []
 *     }
 * }
 */

class Solution {
    func postorder(_ root: Node?) -> [Int] {
        var res = [Int]()

        func dfs(_ node: Node?) {
            guard let node = node else { return }
            for child in node.children {
                dfs(child)
            }
            res.append(node.val)
        }

        dfs(root)
        return res
    }
}

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$ for the recursion stack.

2. Iterative DFS

Intuition

To convert the recursive solution to an iterative one, we use a stack. The key challenge is ensuring we process a node only after all its children have been processed. We achieve this by pushing each node onto the stack twice: once to signal that its children should be explored, and once to signal that it should be added to the result. A visited flag distinguishes between these two cases. When we pop a node that has been visited, we add it to the result. When we pop an unvisited node, we mark it as visited, push it back, then push all its children in reverse order.

Algorithm

If the root is null, return an empty list.
Initialize a stack with the pair (root, false), where false indicates the node has not been visited.
While the stack is not empty:
- Pop a pair (node, visited).
- If visited is true, add node.val to the result.
- Otherwise, push (node, true) back onto the stack, then push all children in reverse order as (child, false).
Return the result list.

"""
# Definition for a Node.
class Node:
    def __init__(self, val: Optional[int] = None, children: Optional[List['Node']] = None):
        self.val = val
        self.children = children
"""

class Solution:
    def postorder(self, root: 'Node') -> List[int]:
        res = []
        if not root:
            return res
        
        stack = [(root, False)]
        while stack:
            node, visited = stack.pop()
            if visited:
                res.append(node.val)
            else:
                stack.append((node, True))
                for child in reversed(node.children):
                    stack.append((child, False))
        return res

/*
// Definition for a Node.
class Node {
    public int val;
    public List<Node> children;

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, List<Node> _children) {
        val = _val;
        children = _children;
    }
}
*/

public class Solution {
    public List<Integer> postorder(Node root) {
        List<Integer> res = new ArrayList<>();
        if (root == null) return res;

        Stack<Pair<Node, Boolean>> stack = new Stack<>();
        stack.push(new Pair<>(root, false));

        while (!stack.isEmpty()) {
            Pair<Node, Boolean> p = stack.pop();
            Node node = p.getKey();
            boolean visited = p.getValue();

            if (visited) {
                res.add(node.val);
            } else {
                stack.push(new Pair<>(node, true));
                for (int i = node.children.size() - 1; i >= 0; i--) {
                    stack.push(new Pair<>(node.children.get(i), false));
                }
            }
        }

        return res;
    }
}

/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val) {
        val = _val;
    }

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};
*/

class Solution {
public:
    vector<int> postorder(Node* root) {
        vector<int> res;
        if (!root) return res;

        stack<pair<Node*, bool>> st;
        st.push({root, false});

        while (!st.empty()) {
            auto [node, visited] = st.top();
            st.pop();

            if (visited) {
                res.push_back(node->val);
            } else {
                st.push({node, true});
                for (int i = (int)node->children.size() - 1; i >= 0; i--) {
                    st.push({node->children[i], false});
                }
            }
        }

        return res;
    }
};

/**
 * Definition for a binary tree node.
 * class Node {
 *     constructor(val = 0, children = []) {
 *         this.val = val;
 *         this.children = children;
 *     }
 * }
 */
class Solution {
    /**
     * @param {Node|null} root
     * @return {number[]}
     */
    postorder(root) {
        const res = [];
        if (!root) return res;

        const stack = [[root, false]];

        while (stack.length) {
            const [node, visited] = stack.pop();

            if (visited) {
                res.push(node.val);
            } else {
                stack.push([node, true]);
                for (let i = node.children.length - 1; i >= 0; i--) {
                    stack.push([node.children[i], false]);
                }
            }
        }

        return res;
    }
}

/*
// Definition for a Node.
public class Node {
    public int val;
    public List<Node> children;

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, IList<Node> _children) {
        val = _val;
        children = _children;
    }
}
*/

public class Solution {
    public List<int> Postorder(Node root) {
        List<int> res = new List<int>();
        if (root == null) return res;

        Stack<(Node, bool)> stack = new Stack<(Node, bool)>();
        stack.Push((root, false));

        while (stack.Count > 0) {
            var (node, visited) = stack.Pop();

            if (visited) {
                res.Add(node.val);
            } else {
                stack.Push((node, true));
                for (int i = node.children.Count - 1; i >= 0; i--) {
                    stack.Push((node.children[i], false));
                }
            }
        }

        return res;
    }
}

/**
 * Definition for a Node.
 * type Node struct {
 *     Val int
 *     Children []*Node
 * }
 */

func postorder(root *Node) []int {
    res := []int{}
    if root == nil {
        return res
    }

    type pair struct {
        node    *Node
        visited bool
    }

    stack := []pair{{root, false}}

    for len(stack) > 0 {
        p := stack[len(stack)-1]
        stack = stack[:len(stack)-1]

        if p.visited {
            res = append(res, p.node.Val)
        } else {
            stack = append(stack, pair{p.node, true})
            for i := len(p.node.Children) - 1; i >= 0; i-- {
                stack = append(stack, pair{p.node.Children[i], false})
            }
        }
    }

    return res
}

/**
 * Definition for a Node.
 * class Node(var `val`: Int) {
 *     var children: List<Node?> = listOf()
 * }
 */

class Solution {
    fun postorder(root: Node?): List<Int> {
        val res = mutableListOf<Int>()
        if (root == null) return res

        val stack = ArrayDeque<Pair<Node, Boolean>>()
        stack.addLast(Pair(root, false))

        while (stack.isNotEmpty()) {
            val (node, visited) = stack.removeLast()

            if (visited) {
                res.add(node.`val`)
            } else {
                stack.addLast(Pair(node, true))
                for (i in node.children.size - 1 downTo 0) {
                    node.children[i]?.let { stack.addLast(Pair(it, false)) }
                }
            }
        }

        return res
    }
}

/**
 * Definition for a Node.
 * public class Node {
 *     public var val: Int
 *     public var children: [Node]
 *     public init(_ val: Int) {
 *         self.val = val
 *         self.children = []
 *     }
 * }
 */

class Solution {
    func postorder(_ root: Node?) -> [Int] {
        var res = [Int]()
        guard let root = root else { return res }

        var stack: [(Node, Bool)] = [(root, false)]

        while !stack.isEmpty {
            let (node, visited) = stack.removeLast()

            if visited {
                res.append(node.val)
            } else {
                stack.append((node, true))
                for i in stride(from: node.children.count - 1, through: 0, by: -1) {
                    stack.append((node.children[i], false))
                }
            }
        }

        return res
    }
}

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

Common Pitfalls

Appending Node Value Before Processing Children

In postorder traversal, the node's value must be added to the result after all its children have been processed. A common mistake is appending the node's value before or during the iteration over children. This produces preorder output instead of postorder. Always ensure the res.append(node.val) statement comes after the loop that recursively processes all children.

Forgetting to Reverse Children Order in Iterative Approach

When using an explicit stack for iterative postorder traversal, children must be pushed in reverse order so that the leftmost child is processed first. If you push children in their natural order, the rightmost child will be popped and processed first, resulting in incorrect traversal order. Always iterate through children in reverse when adding them to the stack.