### Postorder Traversal of N-ary Tree - The Coding Shala

Last Updated: 26-Jan-2021

Home >> Data Structures >> Postorder Traversal of N-ary Tree
In this post, we will learn how to Traverse the N-ary Tree in Postorder and will write a Java program for Postorder Traversal.

## Postorder Traversal of N-ary Tree

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

For example, given a 3-ary tree:

1

/ | \

3 2 4

/ \

5 6

Return its postorder traversal as: [5,6,3,2,4,1].

## Postorder Traversal of N-ary Tree Java Program

**Approach 1**

Recursive Solution.

- step 1. if the root is null return list.
- step 2. The recursive call to all children.
- step 3. add root to list.
- step 4. return list.

**Java Program:**

/* // Definition for a Node. class Node { public int val; public List<Node> children; public Node() {} public Node(int _val,List<Node> _children) { val = _val; children = _children; } }; */ class Solution { List<Integer> postOrder = new ArrayList<Integer>(); public List<Integer> postorder(Node root) { if(root == null) return postOrder; //first recursive call on all the children for(int i=0; i<root.children.size(); i++){ postorder(root.children.get(i)); } //add the root postOrder.add(root.val); return postOrder; } }

**Approach 2**

The iterative solution, using stack.

- step 1. push root to the stack
- step 2. while the stack is not empty
- step 3. push all the node's children to stack
- step 4. reverse the list(to get postorder)

**Java Program:**

/* // Definition for a Node. class Node { public int val; public List<Node> children; public Node() {} public Node(int _val,List<Node> _children) { val = _val; children = _children; } }; */ class Solution { public List<Integer> postorder(Node root) { List<Integer> postOrder = new ArrayList<Integer>(); if(root == null) return postOrder; Stack<Node> st = new Stack<Node>(); st.push(root); while(!st.empty()){ root = st.pop(); postOrder.add(root.val); for(int i=0;i<root.children.size();i++){ st.push(root.children.get(i)); } } Collections.reverse(postOrder); return postOrder; } }

**Other Posts You May Like**

- Introduction to N-ary Tree
- Preorder Traversal of N-ary Tree
- Binary Tree Preorder Traversal
- Binary Tree Inorder Traversal
- Binary Tree Postorder Traversal

## Comments

## Post a Comment