Election Rollup Audit
Check if binary tree non-leaf values equal their subtree leaf sums
An election office organizes its reports in a binary tree. Each leaf represents a precinct, and each non-leaf node represents an office combining all precincts below it.
Every node stores a signed vote margin: votes for candidate A minus votes for candidate B. A leaf's value is its precinct's actual margin. A non-leaf node's value is a reported total that might be incorrect.
Given the root root, return true if every non-leaf node's value equals the sum of the values of all leaves in its subtree. Otherwise, return false.
A node with only one child still combines all leaves below that child. An empty tree passes the audit.
Examples
Example 1
Input: root = [7,3,4,1,2,null,4] Output: true
The left office reports 3 from precinct margins 1 and 2. The right office reports 4 from its single precinct margin 4. The root reports their combined margin of 7.
Example 2
Input: root = [8,3,5,1,3] Output: false
The root's report matches the reports of its immediate children, but the left office reports 3 even though its precinct margins 1 and 3 sum to 4. Every office must be audited, not just the root.
Example 3
Input: root = [] Output: true
There are no offices or precincts to audit in an empty tree.
Constraints
- The tree contains between 0 and 4,000 nodes.
- -1,000,000,000 <= node.val <= 1,000,000,000.
- The input is a binary tree; reported totals are not guaranteed to be correct.
A depth-first traversal checking local parent-child sums takes O(n) time and O(h) auxiliary space, where h is the tree height. Local checks are sufficient because the equality propagates upward from the leaves. Use an iterative traversal to support deeply skewed trees.
Hints
Show hint 1Hint 1
If all reports are correct, what relationship must hold between a non-leaf node and its existing children?
Show hint 2Hint 2
If that relationship holds at every non-leaf node, reason upward from the leaves to show that every report equals its subtree's leaf total.
Follow-up questions
What an interviewer might ask once you have a working solution.
- How would you return the number of incorrect reports, where correctness is still measured against actual leaf margins?
- How would you audit reports if each office could have any number of children?
Practice this with an AI interviewer
Explain your approach out loud, write Python or JavaScript, run it against hidden tests (including large inputs), and get a scored debrief.
Start this problem