N-ary Tree Preorder Traversal
EasyPrompt
Given the root of an n-ary tree, return the preorder traversal of its nodes' values.
Nary-Tree input serialization is represented in their level order traversal. Each group of children is separated by the null value (See examples)
Example 1:
Input: root = [1,null,3,2,4,null,5,6]
Output: [1,3,5,6,2,4]Example 2:
Input: root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
Output: [1,2,3,6,7,11,14,4,8,12,5,9,13,10]
Constraints:
- The number of nodes in the tree is in the range
[0, 104]. 0 <= Node.val <= 104- The height of the n-ary tree is less than or equal to
1000.
Follow up: Recursive solution is trivial, could you do it iteratively?
Approaches
2 approaches with complexity analysis and trade-offs.
The most intuitive way to perform a preorder traversal is using recursion. The definition of preorder traversal is to visit the root node first, and then traverse the subtrees of its children from left to right. This structure lends itself perfectly to a recursive function.
Algorithm
- Define a helper function, let's call it
traverse, that takes aNodeand aList<Integer>as arguments. - The main
preorderfunction will initialize an empty list and call this helper function with therootnode. - Inside the
traversefunction:- Check for the base case: if the current node is
null, simply return. - Add the value of the current node to the list. This is the "visit" step in preorder (Root -> Left -> Right).
- Iterate through the list of children of the current node.
- For each child, make a recursive call to the
traversefunction, passing the child node and the list.
- Check for the base case: if the current node is
Walkthrough
We can implement this with a helper function that performs the traversal. The main function initializes a list to store the results and calls the helper with the root. The helper function first checks if the node is null. If not, it adds the node's value to our result list. Then, it iterates through all the children of the current node, from the first to the last, and makes a recursive call for each child. This process naturally follows the 'root, then children' order of preorder traversal.
/*// Definition for a Node.class Node { public int val; public List<Node> children; public Node() {} public Node(int _val) { val = _val; } public Node(int _val, List<Node> _children) { val = _val; children = _children; }};*/ class Solution { public List<Integer> preorder(Node root) { List<Integer> result = new ArrayList<>(); traverse(root, result); return result; } private void traverse(Node node, List<Integer> result) { if (node == null) { return; } // Visit the root node first result.add(node.val); // Then, recursively traverse its children for (Node child : node.children) { traverse(child, result); } }}Complexity
Time
O(N), where N is the total number of nodes in the tree. This is because we visit each node exactly once.
Space
O(H), where H is the height of the tree. In the worst-case scenario of a skewed tree (where each node has only one child), the height can be equal to the number of nodes N, leading to a space complexity of O(N). This space is used by the recursion call stack.
Trade-offs
Pros
The code is simple, clean, and easy to understand as it directly mirrors the definition of preorder traversal.
It requires minimal boilerplate code.
Cons
For very deep trees, this approach can lead to a
StackOverflowErrorbecause each recursive call adds a new frame to the system's call stack.
Solutions
Solution
/* // Definition for a Node. class Node { public int val; public List<Node> children; public Node() {} public Node(int _val) { val = _val; } public Node(int _val, List<Node> _children) { val = _val; children = _children; } }; */ class Solution { public List < Integer > preorder ( Node root ) { if ( root == null ) { return Collections . emptyList (); } List < Integer > ans = new ArrayList <>(); Deque < Node > stk = new ArrayDeque <>(); stk . push ( root ); while (! stk . isEmpty ()) { Node node = stk . pop (); ans . add ( node . val ); List < Node > children = node . children ; for ( int i = children . size () - 1 ; i >= 0 ; -- i ) { stk . push ( children . get ( i )); } } return ans ; } }Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.