N-ary Tree Preorder Traversal

Given an n-ary tree, return the preorder traversal of its nodes’ values.

Question

Given an n-ary tree, return the preorder traversal of its nodes’ values.

Example:

Input : {1,3,2,4#2#3,5,6#4#5#6}
Output: [1,3,5,6,2,4]
Explanation:
The tree is look like this (in left):

Analyzation

Stack

This problem should only use Stack structure, not Queue, because the stack is LIFO but queue is FIFO and will cause runtime error if using Queue.

The stack goes from the root to leaves. Note that the neighbors should be reversed before putting into the stack, again, it is because stack is LIFO and we want the very left node to be considered first.

The Code

class Solution:
    """
    @param root: the tree
    @return: pre order of the tree
    """
    def preorder(self, root):
        # write your code here
        if root is None:
            return []
        
        stack, output = [root], []
        
        while stack:
            root = stack.pop()
            output.append(root.label)
            
            stack.extend(root.neighbors[::-1])
        
        return output

Time & Space Complexity

• Time complexity: O(n). Remember that the best case of a Binary Tree is O(logn) since it is a balanced tree but the worst case is O(n) because it can skew to only one side.
• Space complexity: O(n). Remember that the space complexity is always about how many nodes there are in a Binary Tree. If the tree is well-balanced then it is O(logn) but the worst case will be O(n).