Compute minimum added stones to balance a tree

Problem Statement

You are given a binary tree where each node contains a value representing the number of stones at that position. A tree is considered 'balanced' if the sum of all nodes in every subtree rooted at any node u is equal to a target value K.

You can add any number of non-negative stones to any node in the tree. Your goal is to return the minimum total number of stones you need to add to the existing nodes to make the entire tree balanced.

Function Signature

def min_added_stones(root, K) -> int:

Constraints

• The tree has between 1 and 10^5 nodes.
• Node values and K are integers between 0 and 10^6.
• If it is impossible to balance the tree by adding stones, return -1.

Examples

Example 1:

• Input: root = [1, 2, 3], K = 6
• Explanation: The total sum of the tree is 6. The root subtree already sums to 6. The left child (2) needs +1 to make its subtree sum equal to 3, and the right child (3) needs 0. Wait—if K is the target for every subtree, we must check if the structure allows it. If K=6, the left subtree must sum to 6 and the right to 6.
• Output: 10 (Calculation: 6-2=4 added to left, 6-3=3 added to right, then root adjustment).

Note: If the target K is smaller than a current subtree's sum, it is impossible to reach K by adding stones.