Airport Transfer Burden Map
Sum of value-weighted distances for each binary tree node in preorder
An airport's transfer corridors form a binary tree. Each node represents a departure gate, and its value is the number of passengers currently waiting at that gate. Each corridor joins a node to one of its children and takes one minute to walk in either direction.
The airport is considering placing a temporary assistance desk at each gate. If the desk is placed at gate u, its transfer burden is
sum(passengers at v * distance between u and v)
over every gate v. Distance is the number of corridors on the unique path between the two gates. Passengers at the desk's own gate contribute zero.
Given root, return the transfer burden for every gate in preorder: visit the root, then its left subtree, then its right subtree. Gates with equal passenger counts remain separate gates and must each have their own entry.
Return an empty list if the airport has no gates.
Examples
Example 1
Input: root = [5,2,4] Output: [6,13,9]
The preorder gate sequence is the root, its left child, then its right child. A desk at the root is one corridor from both other gates. A desk at either child is one corridor from the root and two corridors from the other child.
Example 2
Input: root = [0,0,0,null,3] Output: [6,3,0,9]
The gate containing three passengers is the only gate contributing to any burden. Each candidate desk's burden is three times its distance from that gate. The zero-passenger gates still receive entries in preorder.
Example 3
Input: root = [12] Output: [0]
A single gate has no transfer distance to itself, regardless of how many passengers are waiting.
Constraints
- The tree contains between 0 and 7,000 nodes.
- 0 <= node.val <= 1,000,000.
- Every corridor has length one.
- The input is a valid binary tree; it need not be balanced.
- Use integer arithmetic capable of representing values up to 49,000,000,000,000.
An iterative traversal avoids recursion-depth limits on long chains. The intended solution takes O(n) time and O(n) auxiliary space. JavaScript Number represents every possible result exactly under these constraints.
Hints
Show hint 1Hint 1
First compute the total number of passengers in each subtree and the burden of a desk at the root.
Show hint 2Hint 2
When a desk moves from a parent to its child, every passenger in that child's subtree becomes one corridor closer, and every other passenger becomes one corridor farther away.
Follow-up questions
What an interviewer might ask once you have a working solution.
- How would the rerooting formula change if corridors had different positive lengths?
- How would you return only the best desk location, breaking ties by earliest preorder position?
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