N-ary Tree Preorder Traversal

Easy

#0561Time: 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.

Algorithms

Depth-First Search

Data structures

Stack Tree

Prompt

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, 10⁴].
0 <= Node.val <= 10⁴
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 a Node and a List<Integer> as arguments.
The main preorder function will initialize an empty list and call this helper function with the root node.
Inside the traverse function:
1. Check for the base case: if the current node is null, simply return.
2. Add the value of the current node to the list. This is the "visit" step in preorder (Root -> Left -> Right).
3. Iterate through the list of children of the current node.
4. For each child, make a recursive call to the traverse function, passing the child node and the list.

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.

1/*2// Definition for a Node.3class Node {4    public int val;5    public List<Node> children;6 7    public Node() {}8 9    public Node(int _val) {10        val = _val;11    }12 13    public Node(int _val, List<Node> _children) {14        val = _val;15        children = _children;16    }17};18*/19 20class Solution {21    public List<Integer> preorder(Node root) {22        List<Integer> result = new ArrayList<>();23        traverse(root, result);24        return result;25    }26 27    private void traverse(Node node, List<Integer> result) {28        if (node == null) {29            return;30        }31        // Visit the root node first32        result.add(node.val);33        // Then, recursively traverse its children34        for (Node child : node.children) {35            traverse(child, result);36        }37    }38}

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 StackOverflowError because each recursive call adds a new frame to the system's call stack.

As a follow-up to the recursive solution, we can perform the preorder traversal iteratively using an explicit stack. This approach avoids the risk of stack overflow for very deep trees by managing the traversal process on the heap instead of the call stack.

Algorithm

Initialize an empty List<Integer> for the results and an empty Stack<Node>.
If the root is null, return the empty list.
Push the root node onto the stack.
Loop as long as the stack is not empty:
1. Pop a node from the top of the stack. Let's call it currentNode.
2. Add the value of currentNode to the result list.
3. Get the list of children for currentNode.
4. Iterate through the children in reverse order (from right to left).
5. Push each child onto the stack. Pushing in reverse order ensures that when we pop them, they are processed in the correct left-to-right order.
Return the result list.

Walkthrough

The core idea is to use a stack to simulate the function call stack used in recursion. We start by pushing the root node onto the stack. Then, we enter a loop that continues as long as the stack is not empty. In each iteration, we pop a node, add its value to our result list, and then push its children onto the stack. A key detail is that we must push the children from right to left. This ensures that the leftmost child is at the top of the stack and will be processed next, correctly maintaining the preorder sequence.

1/*2// Definition for a Node.3class Node {4    public int val;5    public List<Node> children;6 7    public Node() {}8 9    public Node(int _val) {10        val = _val;11    }12 13    public Node(int _val, List<Node> _children) {14        val = _val;15        children = _children;16    }17};18*/19 20class Solution {21    public List<Integer> preorder(Node root) {22        List<Integer> result = new ArrayList<>();23        if (root == null) {24            return result;25        }26 27        Stack<Node> stack = new Stack<>();28        stack.push(root);29 30        while (!stack.isEmpty()) {31            Node node = stack.pop();32            result.add(node.val);33 34            // Push children from right to left to process them from left to right35            for (int i = node.children.size() - 1; i >= 0; i--) {36                stack.push(node.children.get(i));37            }38        }39 40        return result;41    }42}

Complexity

Time

O(N), where N is the total number of nodes. Each node is pushed onto and popped from the stack exactly once.

Space

O(W), where W is the maximum width of the tree. In the worst case, for a complete N-ary tree, the last level can contain roughly N nodes, leading to a space complexity of O(N). This space is used by the explicit stack.

Trade-offs

Pros

Avoids StackOverflowError that can occur with deep trees in the recursive approach.
Can be more memory efficient in certain tree structures (e.g., a completely skewed tree where its space complexity would be O(1) while recursion's would be O(N)).

Cons

The logic can be slightly less intuitive than the recursive version, particularly the need to push children onto the stack in reverse order.
Requires manual management of the stack.

Solutions

Solution

1/* // 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 ; } }

1/* // Definition for a Node. class Node { public: int val; vector<Node*> children; Node() {} Node(int _val) { val = _val; } Node(int _val, vector<Node*> _children) { val = _val; children = _children; } }; */ class Solution { public: vector < int > preorder ( Node * root ) { if ( ! root ) return {}; vector < int > ans ; stack < Node *> stk ; stk . push ( root ); while ( ! stk . empty ()) { Node * node = stk . top (); ans . push_back ( node -> val ); stk . pop (); auto children = node -> children ; for ( int i = children . size () - 1 ; i >= 0 ; -- i ) stk . push ( children [ i ]); } return ans ; } };

1""" # Definition for a Node. class Node: def __init__(self, val=None, children=None): self.val = val self.children = children """ class Solution : def preorder ( self , root : 'Node' ) -> List [ int ]: ans = [] if root is None : return ans stk = [ root ] while stk : node = stk . pop () ans . append ( node . val ) for child in node . children [:: - 1 ]: stk . append ( child ) 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.

← Previous

Previous problem

Next problem