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.
Line 1: space-separated level-order tokens describing the binary tree (integers and the token null).
A single integer: the total tilt. If the tree is empty, print 0.
Example 1
Input
1 2 3
Expected
1
Explanation
Leaves 2 and 3 each have tilt 0 (no children). Root's left subtree sum is 2, right is 3, tilt = |2-3| = 1. Total tilt = 1.
Example 2
Input
4 2 9 3 5 null 7
Expected
15
Explanation
Node 2's subtrees: left=3 (tilt 0), right=5 (tilt 0), tilt at 2 = |3-5| = 2. Node 9's subtrees: left=0 (missing), right=7, tilt at 9 = |0-7| = 7. Root's left subtree sum = 2+3+5=10, right subtree sum = 9+7=16, tilt at root = |10-16| = 6. Total = 2+7+6 = 15.
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 →