Deepest Leaves Sum in a Binary Tree

In this problem, you are given a binary tree represented in level-order format. A missing node is represented by the keyword null (or None). Your task is to compute the sum of all node values that appear at the deepest level of the tree.

For example, given the input 1 2 3 None None 4 5, the binary tree is constructed as follows:

The deepest leaves are 4 and 5, and their sum is 9.

The binary tree may be incomplete; ensure your solution correctly handles missing nodes.

A mathematical representation for a level that is the deepest can be given as: $$\max_{i} {depth(i)}$$, where depth(i) represents the level of the i-th node. Your solution should compute:

using the provided tree structure.

inputFormat

The input is given from standard input (stdin) as a single line. The line contains the values of the binary tree nodes in level-order separated by spaces. Missing nodes are represented by the string null (or None). For example: 1 2 3 None None 4 5.

outputFormat

Output the sum of the values of the nodes at the deepest level of the binary tree to standard output (stdout).## sample

1 2 3 None None 4 5

9