Best Product of a Tree Cut

Medium

You get the root of a binary tree whose nodes hold positive numbers. Remove exactly one edge, which splits the tree into two parts. Add up the values in each part and multiply the two sums. Return the largest product you can get by choosing the edge well. The answer may be large, so return it modulo 10⁹ + 7. Compare the true products and take the remainder only of the final one.

Example 1

root=tree_node([4, 9, 2, None, None, 5, 1]) → 108

The whole tree sums to 21. Cutting off node 2 with its children 5 and 1 gives parts 8 and 13, product 104. Cutting off the leaf 9 does better: 9 · 12 = 108. Every other cut gives less, so the answer is 108.

Example 2

root=tree_node([3, 3]) → 9

There is only one edge: parts 3 and 3, product 9.

Constraints

The tree has between 2 and 10⁵ nodes
1 ≤ Node.val ≤ 10⁴

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Tree Depth-First Search Binary Tree

Similar problems

Is It a Search Tree? Medium Two Mixed-Up Nodes Medium All Leaf Paths With a Given Total Medium Tree Into a Right Chain Medium Digit Branch Totals Medium

Input

root=tree_node([4, 9, 2, None, None, 5, 1])

Expected

Run checks the first 3 tests in your browser. Submit checks all 61 tests on the server, hidden ones included.