1. Introduction

Given the root of an n-ary tree, return the postorder traversal of its nodes’ values.

This article is part of Binary Tree-Traversals. Read more about Binary Tree traversals here.

2. Content

I have explained the Postorder traversal in Binary Tree in this article. I would recommend you to read that first.

We can do Postorder traversal in n-ary tree‌:

1. Visit the root node
2. Recursively traverse its children

Postorder Traversal Result: [2,6,14,11,7,3,12,8,4,13,9,10,5,1]

3. Postorder using Recursion

Recursion code is very simple. We will recurse all the children of the root node. Once that is done, we will visit the nodes.

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

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

Time and Space complexity nomenclature: n where n is the total number of nodes in the tree.

Time Complexity: O(n) because we traverse the entire tree.

Space Complexity: O(n) because we save all the nodes in the auxiliary result.

4. Postorder using Iteration

Postorder traversal using Iteration is a little complicated as we need to maintain the nodes that are already traversed. 

public List<Integer> postorderIterative(Node root) {
   if (root == null)
       return List.of();
   List<Integer> result = new ArrayList();
   Set<Node> visited = new HashSet<>();
   Deque<Node> stack = new ArrayDeque<>();
   stack.push(root);

   while (!stack.isEmpty()) {
       Node curr = stack.peek();
       // If no children exist for this node, then visit it.
       if (curr.children.isEmpty()) {
           stack.pop();
           result.add(curr.val);
       } else {
           // If we already visited this node, then insert in
           // result.
           if (visited.contains(curr)) {
               stack.pop();
               result.add(curr.val);
               continue;
           }
           // Push all children in reverse into stack so
           // We can access them from left to right.
           for (int i = curr.children.size() - 1; i >= 0; i--) {
               stack.push(curr.children.get(i));
           }
           // Once this node is visited, then push it into the visited set
           // so we won't visit it again.
           visited.add(curr);
       }
   }
   return result;
}

Time Complexity: O(n) because we traverse the entire tree.

Space Complexity: O(n) because we save all the nodes in the auxiliary result.

5. Conclusion:

In this article, we saw Postorder Traversal of the n-ary Tree using Recursion and Iteration.

GitHub link: https://github.com/savanibharat/justamonad-tutorials/blob/master/justamonad-tutorials-leetcode/src/main/java/com/justamonad/tutorials/leetcode/tree/NAryTreePostorderTraversal.java