589. N-ary Tree Preorder Traversal

Problem Description

The problem requires writing a function that performs a preorder traversal of an n-ary tree and returns a list of the values of the nodes visited. In an n-ary tree, each node can have zero or more children, unlike binary trees where each node has at most two children. The ‘preorder’ part of the request means that the traversal should follow this order: visit the current node first, and then proceed recursively with the preorder traversal of the children, from left to right, if any. The input serialized n-ary tree representation uses level order traversal where each group of children is separated by the value null.

Intuition

The intuition behind solving a tree traversal problem, especially for preorder traversal, is to follow the pattern of visiting each node before its children. For an n-ary tree, we need to visit the current node, then visit each of the children in order. This approach naturally suggests using recursion or iteration with a stack to maintain the order of nodes to visit.

We choose an iterative approach using a stack to avoid potential issues with recursion, such as stack overflow when dealing with very deep trees. We start by pushing the root node onto the stack. Then, as long as the stack is not empty, we pop the top element from the stack, which is the current node to visit, and append its value to the result list. Next, we need to ensure that we visit the children of the current node in the correct order. Since a stack is a last-in, first-out (LIFO) structure, we reverse the children before pushing them onto the stack to maintain the left-to-right traversal order.

This way, when we continue to the next iteration of the while loop, we pop the nodes in preorder (parent before children, leftmost children first).

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

Solution Approach

The solution to the n-ary tree preorder traversal problem involves an iterative approach using a stack data structure. In computer science, a stack is a collection that follows the last-in, first-out (LIFO) principle. The algorithm proceeds as follows:

1. Initialize an empty list named ans to store the preorder traversal result.
2. If the root of the tree is None, return the empty list immediately, as there is nothing to traverse.
3. Start by creating a stack named stk and push the root node onto it.
4. While the stack is not empty, execute the following steps:
   • Pop the node at the top of the stack. This node is the current node being visited.
   • Append the value of the current node to the ans list.
   • Iterate through the children of the current node in reverse order. Reversing is crucial because we want the leftmost child to be processed first, and the stack, being LIFO, would process the last pushed item first.
   • For each child in the reversed children list, push the child onto the stack to visit it in subsequent iterations.

By repeating this process, we traverse the tree in a preorder fashion, visiting each node and its children in the correct order. The algorithm terminates when the stack is empty, which happens after we have visited all the nodes in the tree.

The key algorithm pattern used here is the iterative depth-first search (DFS). This pattern is particularly suited for preorder traversal because it allows us to visit the current node before exploring each subtree rooted at its children.

The time complexity of this algorithm is O(N), where N is the number of nodes in the n-ary tree, because every node and child relationship is examined exactly once. The space complexity is also O(N), assuming the worst-case scenario where the tree is heavily unbalanced and resembles a linked list, the stack would hold all nodes.

Here is the implementation of the algorithm referenced above:

1class Node:
2    def __init__(self, val=None, children=None):
3        self.val = val
4        self.children = children
5
6class Solution:
7    def preorder(self, root: 'Node') -> List[int]:
8        ans = []
9        if root is None:
10            return ans
11        stk = [root]
12        while stk:
13            node = stk.pop()
14            ans.append(node.val)
15            for child in node.children[::-1]:
16                stk.append(child)
17        return ans

Example Walkthrough

Let's consider a small n-ary tree example to illustrate how the solution approach works. Here we have an n-ary tree with the following structure:

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

The expected preorder traversal of this tree is [1, 2, 5, 6, 3, 7, 4].

According to our algorithm:

1. We initialize ans as an empty list.
2. The root is not None, so we proceed by creating a stack stk with the root node (1) in it.

Now the stk looks like [1].

3. As long as stk is not empty, we continue with the following steps:

Step 1:

• We pop the top of the stack, so node is 1.
• We append 1 to ans, so now ans is [1].
• We push the children of node 1 which are 4, 3, and 2 onto the stack in reverse order. The reversal ensures that we will visit the leftmost child (node 2) next.

Now stk looks like [2, 3, 4].

Step 2:

• We pop the top of the stack, so node is 2.
• We append 2 to ans, so now ans is [1, 2].
• We push the children of node 2 which are 6 and 5 onto the stack in reverse order.

Now stk looks like [5, 6, 3, 4].

Step 3:

• We pop the top of the stack, so node is 5.
• We append 5 to ans, so now ans is [1, 2, 5].
• Node 5 has no children, so we don't push anything onto the stack.

Now stk looks like [6, 3, 4].

Step 4:

• We pop the top of the stack, so node is 6.
• We append 6 to ans, so now ans is [1, 2, 5, 6].
• Node 6 has no children, so we don't push anything onto the stack.

Now stk looks like [3, 4].

Step 5:

• We pop the top of the stack, so node is 3.
• We append 3 to ans, so now ans is [1, 2, 5, 6, 3].
• We push the child of node 3 which is 7 onto the stack.

Now stk looks like [7, 4].

Step 6:

• We pop the top of the stack, so node is 7.
• We append 7 to ans, so now ans is [1, 2, 5, 6, 3, 7].
• Node 7 has no children, so we don't push anything onto the stack.

Now stk looks like [4].

Step 7:

• We pop the top of the stack, so node is 4.
• We append 4 to ans, so now ans is [1, 2, 5, 6, 3, 7, 4].
• Node 4 has no children, so no further action is necessary.

Finally, stk is empty, so we finish the loop. The ans list now contains the preorder traversal of our tree: [1, 2, 5, 6, 3, 7, 4]. This is exactly the order we expected.

Solution Implementation

Time and Space Complexity

The time complexity of the given preorder traversal algorithm is O(N), where N is the total number of nodes in the tree. This is because the algorithm visits each node exactly once.

The space complexity is also O(N), which in the worst-case scenario is the space needed for the stack when the tree degenerates into a linked list (e.g., each node has only one child). However, in the average case where the tree is more balanced, the space complexity would be proportional to the height of the tree, which could be much less than N.

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