Sum Integers in a Tree

EasyPython00:00

Practice interviewer

In session

5 left

00:00

Your question is Sum Integers in a Tree. Start with the requirements on the right.

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

You need to log in / sign up to run or submit.

Problem

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 solutionPython 3

You need to log in / sign up to run or submit.

Run your code to see test output