Blog

Introduction

• In this article, we will solve Leetcode 590 problem which good problem to practice tree data structure
• We will also look at stack based solution for this problem along with the recursive solution.

Problem Statement

• We have been given N-ary tree and we need to return post-order traversal of it’s node value.
• Input tree represented has null value that is basically depicts the separation of children from parent.

Example

• In this example , we can see input has null which means there is children for the given parent and its separated by null.
• Post order traversal means we first cover left child and then right child, but since our tree is n-ary that means we will travel from left to right for the post order.
• So post order would be left -> right children + parent node.
• Below example,[[5,6,3], [ 2], [4], 1]

Solution

Intuition

• We will traverse each child’s node at first and then make a recursive call until we reach a stage where the node doesn’t have any children.
• Once we have that case we can return our call and add that node to our result.

• Once we finish traversing all the child node now we can finally add root node to the list.

Code

• Below is the entire recursion code.

/*
// Definition for a Node.
class Node {
    public int val;
    public List<Node> children;
    public Node() {}
    public Node(int _val) {
        val = _val;
    }
    public Node(int _val, List<Node> _children) {
        val = _val;
        children = _children;
    }
};
*/
class Solution {
    List<Integer> result = new ArrayList<>();
    
    public List<Integer> postorder(Node root) {
        if(root==null) return result;
        sol1(root);
        result.add(root.val);
        return result;
    }


private void sol1(Node root){
        if(root.children==null){
            return;
        }
        
        for(Node node:root.children){
            sol1(node);
            result.add(node.val);
        }
}
}

• We can also use stack-based approach to add each children into stack while traversing the node.
• We can keep children in the stack as we visit them.

• One thing to keep in mind here is that for stack we are moving from left to right so right would be popped first and added to the list as first contrast to what we want.
• We want left child to be executed first.
• Hence we need to reverse the result list at the end.

Here is the entire code:

/*
// Definition for a Node.
class Node {
    public int val;
    public List<Node> children;
    public Node() {}
    public Node(int _val) {
        val = _val;
    }
    public Node(int _val, List<Node> _children) {
        val = _val;
        children = _children;
    }
};
*/
class Solution {
    List<Integer> result = new ArrayList<>();
    
    public List<Integer> postorder(Node root) {
        sol2(root);
        return result;
    }


     private void sol2(Node root){
        if(root.children==null){
            return;
        }
        Stack<Node> stack = new Stack<>();
        stack.push(root);
        while(!stack.isEmpty()){
         Node curr = stack.pop();
         result.add(curr.val);
         for(Node node: curr.children){
           stack.push(node);  
         }
        }
        
        Collections.reverse(result); 
    }
}

Result

• Our solution is accepted by Leetcode.

Complexity

• Time Complexity: O(N) where N is the number of nodes in the tree
• Space complexity: O(H) where H is height of the tree

Conclusion

• In this article we solved Leetcode 590 solution which help us to understand n-ary tree and how we can traverse it in post order.
• We also discussed stack based solution as variation.

Bonus Tip

• If you want to upskill your coding interview game, you can definitely check out this bestseller course ( this is in Java )