590. N-ary Tree Postorder Traversal

EasyStackTreeDepth-First Search
Leetcode Link

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.

Intuition

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

  1. A stack data structure follows last in, first out (LIFO) principle, which can be leveraged to visit nodes in the required postorder.
  2. We start by pushing the root node onto the stack.
  3. 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.
  4. The traversal continues until the stack is empty.
  5. 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.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece๏ผš

Given a sorted array of integers and an integer called target, find the element that equals to the target and return its index. Select the correct code that fills the ___ in the given code snippet.

1def binary_search(arr, target):
2    left, right = 0, len(arr) - 1
3    while left ___ right:
4        mid = (left + right) // 2
5        if arr[mid] == target:
6            return mid
7        if arr[mid] < target:
8            ___ = mid + 1
9        else:
10            ___ = mid - 1
11    return -1
12
1public static int binarySearch(int[] arr, int target) {
2    int left = 0;
3    int right = arr.length - 1;
4
5    while (left ___ right) {
6        int mid = left + (right - left) / 2;
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16
1function binarySearch(arr, target) {
2    let left = 0;
3    let right = arr.length - 1;
4
5    while (left ___ right) {
6        let mid = left + Math.trunc((right - left) / 2);
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16

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:

  1. 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.

  2. Stack Preparation:

    • We initialize a stack named stk and push the root node into it.

  3. 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.

  4. 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.

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

Problem: Given a list of tasks and a list of requirements, compute a sequence of tasks that can be performed, such that we complete every task once while satisfying all the requirements.

Which of the following method should we use to solve this problem?

Example Walkthrough

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

1        1
2      / | \
3     2  3  4
4    /      / \
5   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:

  1. Initialization:

    • Define a list ans to store the postorder traversal.
    • Check if the root is None. If it is, return ans.

  2. Stack Preparation:

    • Initialize a stack stk and push the root node 1 onto it.

  3. 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.

  4. 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
Not Sure What to Study? Take the 2-min Quiz๏ผš

What is the worst case running time for finding an element in a binary tree (not necessarily binary search tree) of size n?

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.

Fast Track Your Learning with Our Quick Skills Quiz:

Suppose k is a very large integer(2^64). Which of the following is the largest as n grows to infinity?

Recommended Readings

Stack Intro

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

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

DFS Fundamentals

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

Got a question?ย Ask the Teaching Assistantย anything you don't understand.

Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.

โ†
โ†‘TA ๐Ÿ‘จโ€๐Ÿซ