N-ary Tree Preorder Traversal- Easy

Easy : https://leetcode.com/problems/n-ary-tree-preorder-traversal/

Given 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).

Follow up:

Recursive solution is trivial, could you do it iteratively?

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 height of the n-ary tree is less than or equal to 1000
• The total number of nodes is between [0, 10^4]

Solution:

Based on preorder traversals : https://takeitoutamber.medium.com/tree-recursive-traversals-e5fdfc17e646

Code:

"""
# 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]:
        stack = [root]
        res = []
        
        while stack:
            node = stack.pop()
            
            if node:
                res.append(node.val)
                
                # Instead of appending one child at a time, 
                # extend the stack -> its 30% more faster.ArithmeticError
                # push the children from right to left 
                stack.extend(node.children[::-1])
                # for x in node.children[::-1]:
                #     stack.append(x)
                        
        return res

Runtime: 52 ms, faster than 80.81% of Python3 online submissions for N-ary Tree Preorder Traversal.

Memory Usage: 16.2 MB, less than 15.47% of Python3 online submissions for N-ary Tree Preorder Traversal.

• Time complexity : we visit each node exactly once, and for each visit, the complexity of the operation (i.e. appending the child nodes) is proportional to the number of child nodes n (n-ary tree). Therefore the overall time complexity is O(N)O(N), where NN is the number of nodes, i.e. the size of tree.
• Space complexity : depending on the tree structure, we could keep up to the entire tree, therefore, the space complexity is O(N)O(N).

## Recursive solution -> slower than the iterative solution

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

Runtime: 56 ms, faster than 24.60% of Python3 online submissions for N-ary Tree Preorder Traversal.

Memory Usage: 16.1 MB, less than 15.68% of Python3 online submissions for N-ary Tree Preorder Traversal.