LeetCode 590: N-ary Tree Postorder Traversal Solution

Master LeetCode problem 590 (N-ary Tree Postorder Traversal), a easy challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

590. N-ary Tree Postorder Traversal

Easy

Stack Tree Depth-First Search

Problem Explanation

Explanation

To perform postorder traversal of an n-ary tree iteratively, we can use a stack data structure. The idea is to visit each node and push its children onto the stack in reverse order. Then we pop each child node from the stack and repeat the process until all nodes are visited.

Algorithm:

Initialize a stack to hold nodes and a result list to store the postorder traversal.
Push the root node onto the stack.
While the stack is not empty, pop a node from the stack.
Add the node's value to the beginning of the result list.
Push all the children of the node onto the stack in reverse order.
Repeat steps 3-5 until the stack is empty.
Return the result list in reverse order to get the postorder traversal.

Time complexity: O(n) - we visit each node once. Space complexity: O(n) - the stack can hold up to n nodes in the worst case.

Solution Code

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

        Stack<Node> stack = new Stack<>();
        stack.push(root);

        while (!stack.isEmpty()) {
            Node node = stack.pop();
            result.add(0, node.val);

            for (Node child : node.children) {
                stack.push(child);
            }
        }

        return result;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 590 (N-ary Tree Postorder Traversal)?

This page provides optimized solutions for LeetCode problem 590 (N-ary Tree Postorder Traversal) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 590 (N-ary Tree Postorder Traversal)?

The time complexity for LeetCode 590 (N-ary Tree Postorder Traversal) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 590 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 590 in Java, C++, or Python.

Back to LeetCode Solutions