# Balance the balance

## Problem

There are some weighing scales which has left and right plates. The weighing scales are very compact and plates are pretty big. As a result of this, one weighing scale can be put into another weighing scale's plate. At the same time some weights can be put onto the plates along with the weighing scale. The empty weighing scale has a fixed predefined weight. Only one weighing scale can be accommodated in one plate. However any number of weights can be put into the plate, even after putting one weighing scale. One such arrangement is given as an input to your program. There are enough supply of weights and they can be of fractional value as well. The program should add weights to the plates to balance the weighing scales. The ultimate result would be that all the weighing scales are balanced.

## Solution

We can balance the weighing scale which has no more weighing scales in its left or right plate. When these are balanced, we can try to balance the weighing scales which has no unbalanced weighing scales in their plates. So if we represent the weighing scale like a binary tree, the ones with only weights will be it's leaf nodes and the weighing scale which is not contained in any other's plate will be the root node. Now if we traverse the tree in a manner that root comes after it's children and we recursively traverse the tree we can find our solution. So the problem is solved by representing the arrangement of the weighing scales by binary tree and then by doing a post order traversal to balance the balances.

### Code

public class BalanceWeight { final static int weightOfBalanceBeam = 10; public static void main(String[] args) { Balance a = new Balance(1, 4, 6); Balance b = new Balance(2, 3, 8); Balance c = new Balance(3, 5, 9); Balance d = new Balance(4, 3, 2); a.left = b; a.right = c; b.left = d; doBalance(a); } public static double doBalance(Balance balance) { if (balance == null) return 0; if (balance.left == null && balance.right == null) { return printBalance(balance.id, balance.leftWeight, balance.rightWeight); } else { return printBalance(balance.id, balance.leftWeight + doBalance(balance.left), balance.rightWeight + doBalance(balance.right)); } } public static double printBalance(int id, double leftWeight, double rightWeight) { if (leftWeight > rightWeight) { System.out.println("Add " + (leftWeight - rightWeight) + " to the right of Balance#" + id); return leftWeight * 2 + weightOfBalanceBeam; } else if (leftWeight < rightWeight) { System.out.println("Add " + (rightWeight - leftWeight) + " to the left of Balance#" + id); return rightWeight * 2 + 10; } else { return rightWeight * 2 + 10; } } } class Balance { public int id; public Balance left; public Balance right; public double leftWeight; public double rightWeight; public Balance(int id, double leftWeight, double rightWeight) { this.id = id; this.leftWeight = leftWeight; this.rightWeight = rightWeight; } }