Solar Branch Calibration
Minimum root-to-leaf path sum in a binary tree
A solar farm's calibration network is arranged as a binary tree. Each node stores a signed calibration adjustment: a positive value adds to the adjustment, while a negative value subtracts from it.
A complete calibration route starts at the root and follows child connections until it reaches a leaf, a node with no children. The route's total adjustment is the sum of all node values on that route, including the root and leaf.
Given root, return the smallest total adjustment among all complete calibration routes. You must finish at a leaf; stopping at an internal node is not allowed.
If the tree is empty, return 0.
Examples
Example 1
Input: root = [8,3,6,null,-5,2,4] Output: 6
The complete routes have node values [8, 3, -5], [8, 6, 2], and [8, 6, 4]. The route through 3 and -5 has the smallest total adjustment.
Example 2
Input: root = [-4,null,7,-2] Output: 1
There is only one complete route, with node values [-4, 7, -2]. The root and the middle node are not leaves, so neither is a valid stopping point.
Example 3
Input: root = [5,2,2] Output: 7
Both complete routes have the same total adjustment. The returned minimum is still uniquely determined.
Constraints
- The tree contains between 0 and 3,000 nodes.
- Each node value is an integer between -1,000 and 1,000.
- The input is a valid binary tree.
The intended solution takes O(n) time and O(h) auxiliary space, where n is the number of nodes and h is the tree height. An iterative traversal avoids recursion-depth limits on long branches.
Hints
Show hint 1Hint 1
Carry the sum of the route so far when visiting a node.
Show hint 2Hint 2
Only compare a route's total with the current minimum when you reach a node with no children.
Follow-up questions
What an interviewer might ask once you have a working solution.
- How would you also return a minimum-total route, choosing the leftmost route when totals tie?
- How would the traversal change if every node 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