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
isNone
and immediately returnans
if true, as there are no nodes to traverse.
- We define a list named
-
Stack Preparation:
- We initialize a stack named
stk
and push the root node into it.
- We initialize a stack named
-
Traversal:
- We enter a
while
loop that continues as long asstk
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.
- We enter a
-
Final Step:
- Upon completion of the
while
loop (when the stackstk
is empty), we have all the node values inans
but in the reverse order of the required postorder traversal. - To fix this, we simply reverse
ans
usingans[::-1]
and then return it.
- Upon completion of the
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 EvaluatorExample 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, returnans
.
- Define a list
-
Stack Preparation:
- Initialize a stack
stk
and push the root node1
onto it.
- Initialize a stack
-
Traversal:
- Start the while loop since
stk
is not empty. - Pop the topmost node from
stk
, which is node1
. Add its value to listans
. - 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 node2
is on top. - Pop node
2
fromstk
, add its value toans
, and push its child onto the stack (5
). - Pop node
5
fromstk
, add its value toans
. No children to add here. - Pop node
3
fromstk
, add its value toans
. No children to add here. - Pop node
4
fromstk
, add its value toans
, and push its children (7
,6
) onto the stack. - Pop node
7
fromstk
, add its value toans
. No children to add here. - Pop node
6
fromstk
, add its value toans
. No children to add here. - Now the
stk
is empty, exit the while loop.
- Start the while loop since
-
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.
- At this point,
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 letC
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 toC
children) will be processed. Therefore, the time complexity isO(N * C)
. However, since every node is visited once, and C is a constant factor, the time complexity simplifies toO(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 theN
nodes in the worst-case scenario. The listans
also storesN
node values. Hence, when considering the output list, the total space complexity remainsO(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.
Which algorithm should you use to find a node that is close to the root of the tree?
Recommended Readings
Stack Intro Imagine you have a pile of books on your desk If you want to add a new book you place it on top If you want to read a book you take it from the top And if you simply want to see which book is on the top you
Everything About Trees A tree is a type of graph data structure composed of nodes and edges Its main properties are It is acyclic doesn't contain any cycles There exists a path from the root to any node Has N 1 edges where N is the number of nodes in the tree and
https algomonster s3 us east 2 amazonaws com cover_photos dfs svg Depth First Search Prereqs Recursion Review problems recursion_intro Trees problems tree_intro With a solid understanding of recursion under our belts we are now ready to tackle one of the most useful techniques in coding interviews Depth First Search DFS
Want a Structured Path to Master System Design Too? Donāt Miss This!