N-ary Tree Preorder Traversal

EASY

Description

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

Checkout 2 different approaches to solve N-ary Tree Preorder Traversal. Click on different approaches to view the approach and algorithm in detail.

Recursive Approach

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.

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 Analysis

Time Complexity: O(N), where N is the total number of nodes in the tree. This is because we visit each node exactly once.Space Complexity: 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.

Pros and Cons

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.

Code Solutions

Checking out 3 solutions in different languages for N-ary Tree Preorder Traversal. Click on different languages to view the code.

/* // 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 Solution

Watch the video walkthrough for N-ary Tree Preorder Traversal

Algorithms:

Depth-First Search

Data Structures:

StackTree