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
.
Flowchart Walkthrough
Let's use the algorithm flowchart to analyze the appropriate search pattern for LeetCode problem 589, N-ary Tree Preorder Traversal. You can refer to the Flowchart for more details. Here's the step-by-step analysis:
Is it a graph?
- Yes: An N-ary tree is a form of a graph, specifically a rooted tree where nodes can have more than two children.
Is it a tree?
- Yes: An N-ary tree is definitely a tree as it consists of nodes with hierarchical relationships but no cycles.
Thus, since the problem involves a tree and not a directed acyclic graph (DAG), the next clear step is to apply Depth-First Search (DFS) for preorder traversal as indicated directly and simply by following the tree path in the flowchart. This effectively solves the problem by exploring nodes deeply before exploring siblings, which fits perfectly with the requirements for a preorder traversal.
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:
- Initialize an empty list named
ans
to store the preorder traversal result. - If the root of the tree is
None
, return the empty list immediately, as there is nothing to traverse. - Start by creating a stack named
stk
and push the root node onto it. - 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
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 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:
- We initialize
ans
as an empty list. - The root is not
None
, so we proceed by creating a stackstk
with the root node (1) in it.
Now the stk
looks like [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
is1
. - We append
1
toans
, so nowans
is[1]
. - We push the children of node
1
which are4
,3
, and2
onto the stack in reverse order. The reversal ensures that we will visit the leftmost child (node2
) next.
Now stk
looks like [2, 3, 4]
.
Step 2:
- We pop the top of the stack, so
node
is2
. - We append
2
toans
, so nowans
is[1, 2]
. - We push the children of node
2
which are6
and5
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
is5
. - We append
5
toans
, so nowans
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
is6
. - We append
6
toans
, so nowans
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
is3
. - We append
3
toans
, so nowans
is[1, 2, 5, 6, 3]
. - We push the child of node
3
which is7
onto the stack.
Now stk
looks like [7, 4]
.
Step 6:
- We pop the top of the stack, so
node
is7
. - We append
7
toans
, so nowans
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
is4
. - We append
4
toans
, so nowans
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
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
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
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
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
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.
How would you design a stack which has a function min
that returns the minimum element in the stack, in addition to push
and pop
? All push
, pop
, min
should have running time O(1)
.
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