Preorder Listing of a Menu Tree

An application menu is an N-ary tree of Node objects (val is the label, children is a list in display order). Return the labels in preorder: a node is listed first, then its children subtrees from left to right. Return [] for an empty menu.

Examples

Input:  root = Node("File", [Node("New", [Node("Doc"), Node("Sheet")]), Node("Open"), Node("Exit")])
Output: ["File", "New", "Doc", "Sheet", "Open", "Exit"]

Input:  root = None
Output: []

Constraints

• 0 <= number of nodes <= 10**4, depth up to 1500 (an iterative solution is safer)
• Target: O(n) time

Goals

• Produce a preorder sequence from an N-ary tree without recursion
• Push children in reverse so the leftmost child is processed first