### 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));
}
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();
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