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

Please leave a comment below if you like this post or found some errors, it will help me to improve my content.