Sum Integers in a Tree | Dataford Interview Questions

ShipBob may represent a fulfillment hierarchy as a tree of integer-valued nodes. Given the root of an arbitrary n-ary tree, recursively calculate the sum of every node's value.

A tree is represented as nested dictionaries. Each node has an integer value and a children array containing zero or more child nodes. An empty tree is represented by None and has a sum of 0.

Formal Specification

Implement sum_tree(root):

Input: root, either None or a dictionary with the shape {"value": int, "children": list[node]}.
Output: An integer equal to the sum of the value field for every node reachable from root.
The solution must use recursion and must not modify the tree.

Constraints

0 <= number of nodes <= 10^5
-10^9 <= node.value <= 10^9
The tree contains no cycles
The maximum depth is at most 1,000

Function Signature

def sum_tree(root):

Your question is Sum Integers in a Tree. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem