Minimum transfer cost required to make every node of binary tree have equal cookies

user_7190730 0
Viewed 262

Given a binary tree with n total nodes, each having some quantity of cookies summing up to n total cookies.

Task is to transform this into nodes with equal cookies (1 cookie per node) with minimum total cost of transfer, provided the cost of transfer is equal to the qty of cookie being transferred between the nodes itself.

Cookies can be transferred only between, a)Parent to child b)Child to parent

Example,

In the below example, first 1 cookie can be transferred from left child to parent with cost = 1 and then transferred to right child to make it equal on all node with an additional cost of 1. So minimum total cost is 2.

    1                   2                1
 2    0     =====>   1     0   =====> 1     1

(given tree)                        (transformed tree)
  
Minimum cost of transfer = 2

Can we have an optimal (time) algorithm to solve this?

minimum tree binary algorithm
1 Answers

You can use a post-order (depth-first) traversal to collect two informations from each subtree. Define:

  • the deviation: it is the difference between the expected number of cookies (i.e. the number of nodes in that subtree), and the actual number of cookies in that subtree. If negative, this represents a cookie-deficit, and it is certain that this number of cookies will have to come from elsewhere via the parent of this subtree. If postive, this represents a cookie-surplus, and that surplus will need to move out of that subtree to the parent node. So whether negative or positive, its absolute value represents a flow of cookies between the root of this subtree and its parent.

  • the transfer cost within that subtree. This represents the cost of moving cookies along the edges within the subtree, both to fill in missing cookies, and to move cookies away from nodes that have more than one. It also includes the cost of bubbling up all surplus cookies towards the subtree's root node, not counting the cost of moving them out of there to the parent node. It also includes the cost of distributing the cookies that come from the parent further down the subtree, but not including the cost of getting those cookies from the parent into the root node.

There is a recurrence relation here. When you have this pair of information for the left and right subtree of a given node, you can derive that pair of information for the combined tree (of which the given node is the root):

  • the deviation for the current tree (rooted in a given node) is the sum of the deviations of its two subtrees and the the number of cookies in the current node minus 1. The "minus 1" reflects the goal to have 1 cookie in the current node.

  • the cost for the current tree (rooted in a given node) is the sum of the costs found for its two subtrees and the absolute value of the deviation found for this node (cf. previous point).

Here is an implementation in a runnable JavaScript snippet. It is run for the following tree:

      2
     / \
    0   1
   / \
  0   2

The answer is 3.

class Node {
    constructor(value, left=null, right=null) {
        this.value = value;
        this.left = left;
        this.right = right;
    }
    
    transferDiffAndCost() {
        let diffLeft = 0, diffRight = 0, costLeft = 0, costRight = 0;
        if (this.left) {
            [diffLeft, costLeft] = this.left.transferDiffAndCost();
        }
        if (this.right) {
            [diffRight, costRight] = this.right.transferDiffAndCost();
        }
        let diff = diffLeft + diffRight + this.value - 1;
        let cost = costLeft + costRight + Math.abs(diff);
        return [diff, cost];
    }
    
    transferCost() {
        let [diff, cost] = this.transferDiffAndCost();
        if (diff != 0) throw "Number of cookies not the same as number of nodes";
        return cost;
    }
}

// Create tree
let root = new Node(2,
    new Node(0,
        new Node(0),
        new Node(2)
    ),
    new Node(1)
);

console.log(root.transferCost()); // 3

user_54598390
Related