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.

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

What are the most two important steps in writing a depth first search function? (Select 2)

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
Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What's the output of running the following function using the following tree as input?

1def serialize(root):
2    res = []
3    def dfs(root):
4        if not root:
5            res.append('x')
6            return
7        res.append(root.val)
8        dfs(root.left)
9        dfs(root.right)
10    dfs(root)
11    return ' '.join(res)
12
1import java.util.StringJoiner;
2
3public static String serialize(Node root) {
4    StringJoiner res = new StringJoiner(" ");
5    serializeDFS(root, res);
6    return res.toString();
7}
8
9private static void serializeDFS(Node root, StringJoiner result) {
10    if (root == null) {
11        result.add("x");
12        return;
13    }
14    result.add(Integer.toString(root.val));
15    serializeDFS(root.left, result);
16    serializeDFS(root.right, result);
17}
18
1function serialize(root) {
2    let res = [];
3    serialize_dfs(root, res);
4    return res.join(" ");
5}
6
7function serialize_dfs(root, res) {
8    if (!root) {
9        res.push("x");
10        return;
11    }
12    res.push(root.val);
13    serialize_dfs(root.left, res);
14    serialize_dfs(root.right, res);
15}
16

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

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

Not Sure What to Study? Take the 2-min Quiz:

Which of the following shows the order of node visit in a Breadth-first Search?

Python Solution

1class Node:
2    """
3    Definition for a node in an N-ary tree.
4    Each node contains a value and a list of its children.
5    """
6    def __init__(self, val=None, children=None):
7        self.val = val
8        self.children = children if children is not None else []
9
10
11class Solution:
12    def preorder(self, root: 'Node') -> List[int]:
13        """
14        Perform preorder traversal on an N-ary tree and return a list of node values.
15      
16        :type root: Node
17        :rtype: List[int]
18        """
19        # Initialize an empty list to hold the traversal result.
20        traversal_result = []
21      
22        # If the tree is empty, return the empty result immediately.
23        if root is None:
24            return traversal_result
25      
26        # Initialize a stack with the root node to begin traversal.
27        stack = [root]
28
29        # Process nodes from the stack until it's empty.
30        while stack:
31            # Pop the top node from the stack.
32            current_node = stack.pop()
33          
34            # Append the current node's value to the traversal result.
35            traversal_result.append(current_node.val)
36          
37            # Reverse iterate through the current node's children and add them to the stack.
38            # Reversing ensures that the children are processed in the original order for preorder traversal.
39            for child in reversed(current_node.children):
40                stack.append(child)
41      
42        # Once all nodes are processed, return the traversal result.
43        return traversal_result
44

Java Solution

1import java.util.ArrayDeque;
2import java.util.ArrayList;
3import java.util.Collections;
4import java.util.Deque;
5import java.util.List;
6
7// Definition for a Node in an N-ary tree.
8class Node {
9    public int val;
10    public List<Node> children;
11
12    public Node() {}
13
14    // Constructor with node value
15    public Node(int val) {
16        this.val = val;
17    }
18
19    // Constructor with node value and list of children
20    public Node(int val, List<Node> children) {
21        this.val = val;
22        this.children = children;
23    }
24}
25
26class Solution {
27  
28    // Preorder traversal for an N-ary tree
29    public List<Integer> preorder(Node root) {
30        // If the tree is empty, return an empty list
31        if (root == null) {
32            return Collections.emptyList();
33        }
34
35        // List to store the preorder traversal
36        List<Integer> result = new ArrayList<>();
37      
38        // Use a stack to track the nodes for traversal
39        Deque<Node> stack = new ArrayDeque<>();
40      
41        // Initialize the stack with the root node
42        stack.push(root);
43
44        // Iterate while the stack is not empty
45        while (!stack.isEmpty()) {
46            // Pop the top node from the stack
47            Node currentNode = stack.pop();
48          
49            // Add the value of the current node to the result list
50            result.add(currentNode.val);
51          
52            // Retrieve the children of the current node
53            List<Node> childrenList = currentNode.children;
54          
55            // Iterate over the children in reverse order so that they
56            // are visited in the correct order when subsequently popped from the stack
57            for (int i = childrenList.size() - 1; i >= 0; --i) {
58                stack.push(childrenList.get(i));
59            }
60        }
61        // Return the final result containing the preorder traversal
62        return result;
63    }
64}
65

C++ Solution

1#include <vector>
2#include <stack>
3using namespace std;
4
5// Definition for a Node.
6class Node {
7public:
8    int val; // Holds the value of the node.
9    vector<Node*> children; // Vector of pointers to child nodes.
10
11    // Constructor initializes the node with default values.
12    Node() {}
13
14    // Constructor initializes the node with a value.
15    Node(int _val) {
16        val = _val;
17    }
18
19    // Constructor initializes the node with a value and the children.
20    Node(int _val, vector<Node*> _children) {
21        val = _val;
22        children = _children;
23    }
24};
25
26class Solution {
27public:
28    // This method performs a preorder traversal of an n-ary tree.
29    vector<int> preorder(Node* root) {
30        if (!root) return {}; // If root is null, return an empty vector.
31      
32        vector<int> result; // The vector to store the preorder traversal.
33        stack<Node*> nodes; // Stack to use for iterative traversal.
34        nodes.push(root); // Start with the root node.
35      
36        // Iterate as long as there are nodes on the stack.
37        while (!nodes.empty()) {
38            Node* current = nodes.top(); // Take the top node from the stack.
39            result.push_back(current->val); // Process the current node's value.
40            nodes.pop(); // Remove the processed node from stack.
41          
42            // Reverse iterate over the node's children and add them to the stack.
43            // This ensures that children are processed in the original order.
44            for (int i = current->children.size() - 1; i >= 0; --i) {
45                nodes.push(current->children[i]);
46            }
47        }
48        return result; // Return the completed preorder traversal vector.
49    }
50};
51

Typescript Solution

1// Node class type definition with value and children properties
2interface Node {
3    val: number;
4    children: Node[];
5}
6
7/**
8 * Performs a preorder traversal on an n-ary tree.
9 * @param root - The root of the n-ary tree.
10 * @returns An array of node values in preorder sequence.
11 */
12function preorder(root: Node | null): number[] {
13    // The array to store the preorder traversal
14    let traversalResult: number[] = [];
15
16    /**
17     * A helper function to perform a depth-first search (DFS) for the preorder traversal.
18     * @param currentNode - The current node being traversed in the n-ary tree.
19     */
20    const dfs = (currentNode: Node | null) => {
21        if (currentNode === null) {
22            return;
23        }
24        // Add the current node's value to the result array
25        traversalResult.push(currentNode.val);
26        // Recursively call dfs for each of the children of the current node
27        currentNode.children.forEach(childNode => {
28            dfs(childNode);
29        });
30    };
31
32    // Initiate the DFS with the root node of the tree
33    dfs(root);
34    // Return the result array containing the preorder traversal
35    return traversalResult;
36}
37
Fast Track Your Learning with Our Quick Skills Quiz:

Consider the classic dynamic programming of longest increasing subsequence:

Find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order.

For example, the length of LIS for [50, 3, 10, 7, 40, 80] is 4 and LIS is [3, 7, 40, 80].

What is the recurrence relation?

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.


Recommended Readings


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 👨‍🏫