Problem statement

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

Solution

In this problem we just need to do what is asked: preordrer traversal. Create stack, where we put root of out tree. Then on each step we extract last element from stack, add it to out and then traverse all children. Note, that we need to traverse children in the reversed order, similar to what we did for binary tree, where we traversed first right and then left.

Complexity

Time and space complexity is O(n), where n is the total number of nodes in our tree, because for every node we need O(1) time.

Code

class Solution:
    def preorder(self, root):
        if not root: return []
        stack, out = [root], []
        while stack:
            cur = stack.pop()
            out.append(cur.val)
            for child in cur.children[::-1]:
                stack += [child]
        return out