N-ary tree sum and leaf next-links

Trees in this problem are N-ary: a node can have any number of children, in order.

Write the node class yourself:

• Node(val, children=None) stores val (an int), children (a list of Node, an empty list when None is passed) and next, which starts as None. You'll use next in later levels.

Then write tree_sum(root) -> int, the sum of val over every node. root may be None (sum 0). Values can be negative.

Constraints: up to 2 * 10**5 nodes, and a tree can be a long chain up to 20_000 levels deep. Python's default recursion limit is 1000, so walk the tree with an explicit stack (or queue) instead of recursion.

t = Node(1, [Node(2, [Node(5)]), Node(3), Node(-4)])
tree_sum(t)     # 7
tree_sum(None)  # 0