Solution: N-ary Tree Preorder Traversal

This is part of a series of Leetcode solution explanations (index). If you liked this solution or found it useful, please like this post and/or upvote my solution post on Leetcode's forums.

---

Leetcode Problem #589 (Easy): N-ary Tree Preorder Traversal

---

Description:

(Jump to: Solution Idea || Code: JavaScript | Python | Java | C++)

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)

---

Examples:

Example 1:
Input:	root = [1,null,3,2,4,null,5,6]
Output:	[1,3,5,6,2,4]
Visual:

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]
Visual:

---

Constraints:

• The number of nodes in the tree is in the range [0, 104].
• 0 <= Node.val <= 10^4
• The height of the n-ary tree is less than or equal to 1000.

---

Idea:

(Jump to: Problem Description || Code: JavaScript | Python | Java | C++)

Preorder traversal is a type of depth-first search (DFS) approach, and DFS problems are generally best solved with a recursive function. In this case, we can even make the main function its own recursive function, rather than having to define a separate recursive helper. In order to accomplish this, we'll need to create a new default argument for the function to hold our answer array (ans), which should default to an empty array.

In a preorder DFS traversal, a node is processed before moving on to its children, and then the children are processed from left to right. Our recursive function should then process the current node (root) by pushing its value to ans, and then we should iterate through root.children and call our recursive function on each.

For all but the main function call, the return value will be unused, but ans should be finished by the time the main function returns it.

---

Implementation:

Python has mutable default arguments, so we'll have to force a clearing back to None and then back to an empty array on a new class instance.

Java doesn't support default arguments, but we can make ans an instance variable instead.

Even though C++ supports default arguments, it's difficult to pass in a pointer, so it's easier just to define a recursive helper instead.

---

Javascript Code:

(Jump to: Problem Description || Solution Idea)

var preorder = function(root, ans=[]) {
    if (!root) return ans
    ans.push(root.val)
    for (let child of root.children)
        preorder(child, ans)
    return ans
};

---

Python Code:

(Jump to: Problem Description || Solution Idea)

class Solution:
    def preorder(self, root: 'Node', ans: list = None) -> List[int]:
        if not root: return ans
        if ans == None: ans = []
        ans.append(root.val)
        for child in root.children:
            self.preorder(child, ans)
        return ans

---

Java Code:

(Jump to: Problem Description || Solution Idea)

class Solution {
    List<Integer> ans = new ArrayList<>();
    public List<Integer> preorder(Node root) {
        if (root == null) return ans;
        ans.add(root.val);
        for (Node child : root.children)
            preorder(child);
        return ans;
    }
}

---

C++ Code:

(Jump to: Problem Description || Solution Idea)

class Solution {
public:
    vector<int> preorder(Node* root) {
        vector<int> ans;
        if (root) pre(root, &ans);
        return ans;
    }
    void pre(Node* node, vector<int>* ans) {
        ans->push_back(node->val);
        for (Node* child : node->children)
            pre(child, ans);
    }
};