590. N-ary Tree Postorder Traversal

Problem Description

The given problem requires us to conduct a postorder traversal on a given n-ary tree and return a list of the values of its nodes. In postorder traversal, we visit the nodes in a left-right-root order for binary trees, which extends to child1-child2-...-childN-root order in the case of n-ary trees, where N can be any number of children a node can have.

N-ary trees differ from regular binary trees as they can have more than two children. In the serialization of such a tree for level order traversal, each set of children is denoted, and then a null value is used to separate them, indicating the end of one level and the beginning of another.

Flowchart Walkthrough

Let's analyze the problem using the Flowchart. Here's how to arrive at using the Depth-First Search pattern for LeetCode 590. N-ary Tree Postorder Traversal:

Is it a graph?

Yes: The problem explicitly involves traversing an N-ary tree, which is a type of graph structure.

Is it a tree?

Yes: The problem specifies traversing an N-ary tree, which confirms that the graph is indeed a tree.

Is the problem related to directed acyclic graphs (DAGs)?

Yes: A tree is a special kind of directed acyclic graph where each child node points only to its parent, forming no cycles and always having a directional (parent to child) connection.

Is the problem related to topological sort?

No: The task is about traversing the tree to visit all nodes in a specific order (postorder), not sorting them topologically.

Conclusion: The initial parts of the flowchart lead us to notice that the structure in question is a tree and part of a directed acyclic graph type, which typically employs Depth-First Search (DFS) for traversal due to the hierarchical nature of trees. Hence, Depth-First Search (DFS) is the appropriate pattern to use for N-ary Tree Postorder Traversal.

Intuition

To solve this problem, we can utilize a stack to simulate the postorder traversal by considering the following points:

A stack data structure follows last in, first out (LIFO) principle, which can be leveraged to visit nodes in the required postorder.
We start by pushing the root node onto the stack.
When popping from the stack, we add the node's value to the answer list and then push all of its children onto the stack. This push operation is done in the original children order, which means when we pop them, they will be in reversed order because of the LIFO property of the stack.
The traversal continues until the stack is empty.
After we've traversed all nodes and have our answer list, it will be in root-childN-...-child1 order. To obtain the postorder traversal, we need to reverse this list before returning it. The reversal step is essential to have the nodes in the child1-child2-...-childN-root order.

By following the described steps, we visit each node's children before visiting the node itself (as per postorder traversal rules) by effectively leveraging the stack's characteristics to traverse the n-ary tree non-recursively.

Learn more about Stack, Tree and Depth-First Search patterns.

Solution Approach

The implementation of the postorder traversal for an n-ary tree is done using a stack to keep track of the nodes. The following steps break down the solution approach:

Initialization:
- We define a list named ans to store the postorder traversal.
- Then, we check if the given root is None and immediately return ans if true, as there are no nodes to traverse.
Stack Preparation:
- We initialize a stack named stk and push the root node into it.
Traversal:
- We enter a while loop that continues as long as stk is not empty.
- Inside the loop, we pop the topmost node from the stack and append its value to list ans.
- We then iterate over the children of the popped node in their given order and push each onto the stack stk.
- Since the stack follows LIFO order, children are appended to the list ans in reverse order with respect to how they were added to the stack.
Final Step:
- Upon completion of the while loop (when the stack stk is empty), we have all the node values in ans but in the reverse order of the required postorder traversal.
- To fix this, we simply reverse ans using ans[::-1] and then return it.

By using this approach, we avoid recursion, which can be helpful in environments where the call stack size is limited. The use of a stack allows us to control the processing order of nodes, thereby enabling the simulation of post-order traversal in an iterative fashion.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's illustrate the solution approach with a simple n-ary tree example:

        1
      / | \
     2  3  4
    /      / \
   5      6   7

In this tree, node 1 is the root, node 2 has one child 5, node 3 has no children, node 4 has two children 6 and 7.

Following the solution steps:

Initialization:
- Define a list ans to store the postorder traversal.
- Check if the root is None. If it is, return ans.
Stack Preparation:
- Initialize a stack stk and push the root node 1 onto it.
Traversal:
- Start the while loop since stk is not empty.
- Pop the topmost node from stk, which is node 1. Add its value to list ans.
- Push the children of node 1 (4, 3, 2) onto the stack. Note: Push in reverse order of the children as stated in the Intuition, so node 2 is on top.
- Pop node 2 from stk, add its value to ans, and push its child onto the stack (5).
- Pop node 5 from stk, add its value to ans. No children to add here.
- Pop node 3 from stk, add its value to ans. No children to add here.
- Pop node 4 from stk, add its value to ans, and push its children (7, 6) onto the stack.
- Pop node 7 from stk, add its value to ans. No children to add here.
- Pop node 6 from stk, add its value to ans. No children to add here.
- Now the stk is empty, exit the while loop.
Final Step:
- At this point, ans is in reverse order of the required post-order traversal: [1, 4, 7, 6, 3, 2, 5].
- Reverse ans to get the correct postorder traversal: [5, 2, 6, 7, 4, 3, 1].
- Return the reversed list.

So using the stated steps, we successfully performed an iterative postorder traversal on the n-ary tree and the final output is [5, 2, 6, 7, 4, 3, 1].

Solution Implementation

1class Node:
2    def __init__(self, val=None, children=None):
3        self.val = val
4        self.children = children if children is not None else []
5
6
7class Solution:
8    def postorder(self, root: 'Node') -> list[int]:
9        # List to store the postorder traversal result
10        postorder_result = []
11
12        # If the tree is empty, return an empty list
13        if root is None:
14            return postorder_result
15
16        # Stack to keep track of nodes to visit
17        stack = [root]
18
19        # Continue processing nodes until stack is empty
20        while stack:
21            # Pop a node from the stack
22            current_node = stack.pop()
23
24            # Add the current node's value to the traversal result
25            postorder_result.append(current_node.val)
26
27            # Push all children of the current node to the stack
28            # Note: We push children in the order as they are in the list so that they are processed
29            # in reverse order when popped (because stack is LIFO), which is needed for postorder.
30            for child in current_node.children:
31                stack.append(child)
32
33        # Return the result reversed, as we need to process children before their parent
34        # This reverse operation gives us the correct order of postorder traversal
35        return postorder_result[::-1]
36

1import java.util.Deque;       // Import the Deque interface
2import java.util.LinkedList;  // Import the LinkedList class
3import java.util.List;        // Import the List interface
4
5class Solution {
6    public List<Integer> postorder(Node root) {
7        LinkedList<Integer> result = new LinkedList<>(); // Use 'result' instead of 'ans' for clarity
8        if (root == null) {
9            // If the root is null, return an empty list
10            return result;
11        }
12
13        Deque<Node> stack = new ArrayDeque<>(); // Use 'stack' to represent the deque of nodes
14        stack.offerLast(root); // Start with the root node
15
16        while (!stack.isEmpty()) {
17            // While there are nodes in the stack
18            Node current = stack.pollLast(); // Get the last node
19            result.addFirst(current.val); // Add the node value to the front of the result list (for postorder)
20
21            // Iterate through children of the current node
22            for (Node child : current.children) {
23                stack.offerLast(child); // Add each child to the stack for processing
24            }
25        }
26        return result; // Return the populated list as the result
27    }
28}
29
30// Definition for a Node.
31class Node {
32    public int val;
33    public List<Node> children;
34
35    // Constructors
36    public Node() {}
37
38    public Node(int _val) {
39        val = _val;
40    }
41
42    public Node(int _val, List<Node> _children) {
43        val = _val;
44        children = _children;
45    }
46}
47

1#include <vector>
2#include <stack>
3#include <algorithm>
4
5// Definition for a Node.
6class Node {
7public:
8    int val;
9    std::vector<Node*> children;
10
11    Node() {}
12
13    Node(int value) {
14        val = value;
15    }
16
17    Node(int value, std::vector<Node*> childNodes) {
18        val = value;
19        children = childNodes;
20    }
21};
22
23class Solution {
24public:
25    std::vector<int> postorder(Node* root) {
26        // Initialize an empty vector to store the postorder traversal.
27        std::vector<int> postorderTraversal;
28
29        // Return empty vector if the root is null.
30        if (!root) return postorderTraversal;
31
32        // Use a stack to hold the nodes during traversal.
33        std::stack<Node*> stack;
34        stack.push(root);
35
36        // Loop until the stack is empty.
37        while (!stack.empty()) {
38            // Get the top node from the stack.
39            root = stack.top();
40            stack.pop();
41
42            // Append the node's value to the traversal vector.
43            postorderTraversal.push_back(root->val);
44
45            // Push all children of the current node to the stack.
46            // We traverse from left to right, the stack is LIFO, so we need to reverse
47            // the postorder by reversing the relation at the end.
48            for (Node* child : root->children) {
49                stack.push(child);
50            }
51        }
52        // Reverse the order of the nodes to get the correct postorder.
53        std::reverse(postorderTraversal.begin(), postorderTraversal.end());
54
55        // Return the postorder traversal.
56        return postorderTraversal;
57    }
58};
59

1// Definition for the Node class. (Do not create a Node class since the instruction is to define everything globally)
2interface INode {
3    val: number;
4    children: INode[];
5}
6
7/**
8 * Post-order traversal function which returns an array of values.
9 * Post-order traversal means visiting the child nodes before the parent node.
10 * @param root - The root node of the tree or null if the tree is empty.
11 * @returns An array of node values in post-order.
12 */
13function postorder(root: INode | null): number[] {
14    // An array to store the result of the post-order traversal
15    const result: number[] = [];
16  
17    /**
18     * Helper function for depth-first search post-order traversal of the node tree.
19     * It recursively visits children first before the parent node then pushes the value to the result array.
20     * @param node - The current node being visited.
21     */
22    const depthFirstSearchPostOrder = (node: INode | null) => {
23        if (node == null) {
24            // If the node is null, i.e., either the tree is empty or we've reached the end of a branch, return
25            return;
26        }
27      
28        // Loop through each child of the current node and recursively perform a post-order traversal
29        for (const childNode of node.children) {
30            depthFirstSearchPostOrder(childNode);
31        }
32      
33        // After visiting the children, push the current node's value to the result array
34        result.push(node.val);
35    };
36
37    // Initiate the post-order traversal from the root of the tree
38    depthFirstSearchPostOrder(root);
39
40    // Return the result of the traversal
41    return result;
42}
43

Time and Space Complexity

The given code implements a post-order traversal of an n-ary tree iteratively using a stack. Analyzing the complexity:

Time Complexity: Each node is visited exactly once, and all its children are added to the stack. Assuming the tree has N nodes, and let C be the maximum number of children a node can have. In the worst case, every node will be pushed and popped from the stack once, and all of its children (up to C children) will be processed. Therefore, the time complexity is O(N * C). However, since every node is visited once, and C is a constant factor, the time complexity simplifies to O(N).
Space Complexity: The space complexity is determined by the size of the stack and the output list. In the worst case, if the tree is imbalanced, the stack could hold all nodes in one of its branches. Therefore, the space complexity is O(N) for storing the N nodes in the worst-case scenario. The list ans also stores N node values. Hence, when considering the output list, the total space complexity remains O(N).

Therefore, the overall time complexity of the code is O(N) and the space complexity is O(N).

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Is the following code DFS or BFS?

void search(Node root) {
  if (!root) return;
  visit(root);
  root.visited = true;
  for (Node node in root.adjacent) {
    if (!node.visited) {
      search(node);
    }
  }
}

Depth First Search

Breadth First Search

I don't know