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
Please leave a comment below if you like this post or found some errors, it will help me to improve my content.

Comments

Popular Posts from this Blog

Shell Script to find sum, product and average of given numbers - The Coding Shala

Shell Script to Create a Simple Calculator - The Coding Shala

Add two numbers in Scala - The Coding Shala

New Year Chaos Solution - The Coding Shala

Richest Customer Wealth LeetCode Solution - The Coding Shala