A binary tree of load-balancer weights 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).
For a node, define its subtree sum as the sum of every value in its subtree (including itself); a missing child contributes a subtree sum of 0. Define the node's tilt as the absolute difference between its left child's subtree sum and its right child's subtree sum.
Print the sum of the tilt values over every node in the tree.
Input format
Line 1: space-separated level-order tokens describing the binary tree (integers and the token null).
Output format
A single integer: the total tilt. If the tree is empty, print 0.
Constraints
- 0 <= number of nodes <= 500
- Each node value is an integer with -1000 <= value <= 1000