590. N-ary Tree Post order Traversal | n Array Tree Post Order Traversal LeetCode Solution in Java

Introduction :

N-ary trees are a type of tree data structure in which each node can have multiple children, as opposed to binary trees where each node has at most two children. Traversing an N-ary tree can be a bit more challenging than a binary tree, but fear not! In this blog post, we will explore the N-ary Tree Postorder Traversal problem on LeetCode and provide a comprehensive Java solution.

Problem Description :

The problem, “N-ary Tree Postorder Traversal,” requires us to perform a postorder traversal of an N-ary tree and return the traversal result as an array. Postorder traversal means that we visit the children of a node before visiting the node itself. This traversal is essential in various applications, such as expression evaluation, where we need to evaluate subtrees before their parent node.

Example :

Let’s start with a simple example to illustrate the problem. Consider the following N-ary tree:

      1
    / | \
   3  2  4
  / \
 5   6

The postorder traversal of this tree would be [5, 6, 3, 2, 4, 1]. We visit the children of each node before the node itself, and we start from the leftmost child.

Now, let’s dive into the Java solution to solve this problem step by step.

Java Solution :

Node Class

First, we’ll create a Node class to represent the nodes of the N-ary tree. This class will have two fields: val, which stores the value of the node, and children, which is a list of its children nodes.

class Node {
    public int val;
    public List<Node> children;

    public Node() {}

    public Node(int val) {
        this.val = val;
    }

    public Node(int val, List<Node> children) {
        this.val = val;
        this.children = children;
    }
}

Postorder Traversal Function

Next, we’ll implement the postorder traversal function that takes the root of the N-ary tree as input and returns the postorder traversal as an array.

class Solution {
    public List<Integer> postorder(Node root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) {
            return result;
        }
        postorderTraversal(root, result);
        return result;
    }

    private void postorderTraversal(Node node, List<Integer> result) {
        if (node == null) {
            return;
        }

        // Traverse children first
        for (Node child : node.children) {
            postorderTraversal(child, result);
        }

        // Add the current node's value after its children
        result.add(node.val);
    }
}

In this solution, we use a recursive approach to perform the postorder traversal. We start from the root node and visit its children recursively before adding the current node’s value to the result list.

Testing the Solution

Let’s test our solution with the example N-ary tree we discussed earlier:

public static void main(String[] args) {
    // Create the N-ary tree
    Node root = new Node(1);
    root.children = new ArrayList<>();
    root.children.add(new Node(3));
    root.children.add(new Node(2));
    root.children.add(new Node(4));
    root.children.get(0).children = new ArrayList<>();
    root.children.get(0).children.add(new Node(5));
    root.children.get(0).children.add(new Node(6));

    // Create a solution instance
    Solution solution = new Solution();

    // Perform postorder traversal
    List<Integer> postorderTraversal = solution.postorder(root);

    // Print the result
    System.out.println(postorderTraversal);
}

Running this code will produce the expected output: [5, 6, 3, 2, 4, 1], which is the postorder traversal of the given N-ary tree.

Complexity Analysis:

• Time Complexity: The time complexity of this solution is O(N), where N is the number of nodes in the N-ary tree. This is because we visit each node exactly once in a postorder traversal.
• Space Complexity: The space complexity is also O(N) due to the space required for the result list and the recursive call stack. In the worst case, when the tree is a linear chain, the call stack can reach a depth of N.

Conclusion :

In this blog post, we explored the N-ary Tree Postorder Traversal problem on LeetCode and provided a detailed Java solution. We defined a Node class to represent the nodes of the N-ary tree and implemented a recursive postorder traversal function. We also discussed the time and space complexity of our solution.

Postorder traversal is a fundamental operation in tree data structures, and understanding how to perform it on N-ary trees is essential for various algorithmic tasks. With the provided Java solution and example, you should now have a clear understanding of how to solve this problem and apply it in your own projects. Happy coding!

Thank You!

Read More –

234. Palindrome Linked List | Palindromic Linked List LeetCode Solution in Java | Code with Kamlesh – https://kamleshsingad.com/234-palindrome-linked-list-and-leetcode-solution-in-java/

Valid Palindrome and LeetCode Solution in Java: A Detailed Guide – https://kamleshsingad.com/valid-palindrome-and-leetcode-solution-in-java-a-detailed-guide/

118. Pascal’s Triangle | Pascal’s Triangle LeetCode Solution in Java | Code with Kamlesh – https://kamleshsingad.com/118-pascals-triangle-pascals-triangle-leetcode-solution-in-java/