Problem

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)

Examples

Example 1:

graph TD
  1 --- A[3] & B[2] & C[4]
  A --- 5 & 6

(have to use A, B, C in mermaid to make the ordering of nodes better)

Input: root = [1,null,3,2,4,null,5,6]
Output: [5,6,3,2,4,1]

Example 2:

graph TD
  1 --- 2 & 3 & 4 & 5
  3 --- 6 & 7
  7 --- 11
  11 --- 14
  4 --- 8
  8 --- 12
  5 --- 9 & 10
  9 --- 13
  
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]

Solution

Postorder traversal involves visiting all the children of a node before visiting the node itself.

Video Explanation

Here is the video explanation:

Method 1 - Recursive DFS

Define a recursive function helper that traverses the tree in postorder and accumulates the result in a list

Code

Java
public List<Integer> postorder(Node root) {
	List<Integer> ans = new ArrayList<>();
	if (root == null) {
		return ans;
	}

	helper(root, ans);

	return ans;
}

private void helper(Node root, List<Integer> ans) {

	for (Node child : root.children) {
		helper(child, ans);
	}

	ans.add(root.val);
}

Complexity

  • ⏰ Time complexity: O(n), where n is number of nodes in tree
  • 🧺 Space complexity: O(h) assuming recursion stack

Method 2 - Iterative

Here are the steps we can take:

  1. Use Stack for Nodes:
    • Push the root node onto the stack initially.
    • Pop a node from the stack, process it, and push all its children onto the stack.
    • This ensures the children are visited before the node itself (as required by postorder).
  2. Reverse Postorder by Prepend:
    • Instead of adding the processed node values to the end of a list, we add them to the front of a LinkedList (which allows efficient addition to the front).
    • This effectively reverses the preorder sequence of the nodes seen.

Code

Java
public class Solution {
    public List<Integer> postorder(Node root) {
        List<Integer> ans = new LinkedList<>();
        if (root == null) {
            return ans;
        }


        Deque<Node> stack = new ArrayDeque<>();
        stack.push(root);

        while (!stack.isEmpty()) {
            Node current = stack.pop();
            ans.addFirst(current.val);

            for (Node child : current.children) {
                stack.push(child);
            }
        }

        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n), where n is number of nodes in tree
  • 🧺 Space complexity: O(n) using recursion stack