A binary tree of stock-portfolio returns is given in level-order form (a single line of space-separated tokens, null marking a missing child; every non-null node contributes exactly two following tokens for its children). The tree always has at least one node.
For any node, define its subtree's average as (sum of all values in its subtree) divided by (the number of nodes in its subtree). Find the maximum such average over every subtree of the tree (including single-node subtrees and the whole tree), and print it as an exact fraction p/q in lowest terms, with q > 0 (print 0/1 if the maximum average is exactly zero).
Line 1: space-separated level-order tokens describing the binary tree (integers and the token null). The tree has at least 1 node.
A single line of the form p/q: the maximum subtree average, as a reduced fraction with a positive denominator.
Example 1
Input
5 3 9
Expected
9/1
Explanation
Subtree averages: node 3 alone = 3/1, node 9 alone = 9/1, whole tree = (5+3+9)/3 = 17/3 ~ 5.67. The maximum is the single node 9, giving 9/1.
Example 2
Input
-4 -2 -2
Expected
-2/1
Explanation
The subtrees are: each leaf -2 by itself = -2/1, and the whole tree rooted at -4 = (-4 + -2 + -2)/3 = -8/3 ~ -2.67. (A root-plus-one-child is not a subtree, since a subtree must include all of a node's descendants.) The maximum, i.e. least negative, is a single -2 leaf: -2/1.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →