Here is a (slightly abridged) problem from Kleinberg and Tardos:
Consider a complete balanced binary tree with $n$ leaves where $n$ is a power of two. Each edge $e$ of the tree has an associated length $\ell_e$, which is a positive number. The distance from the root to a given leaf is the sum of the lengths of all the edges on the path from the root to the leaf.
Now, if all leaves do not have the same distance from the root, then the signals we send starting from the root will not reach the leaves at the same time, and this is a big problem. We want the leaves to be completely synchronized, and all to receive the signal at the same time. To make this happen, we will have to increase the lengths of certain edges, so that all root-to-leaf paths have the same length (we’re not able to shrink edge lengths). If we achieve this, then we say the tree has zero skew.
Give an algorithm that increases the lengths of certain edges so that the resulting tree has zero skew and the total edge length is as small as possible.
This problem was in the "Greedy Algorithms" chapter.
I know the solution to this problem is as follows:
Let the subtrees below the root be $L$ and $R$. If the maximum sum of the edge lengths on the path to a leaf in $L$ starting from the root is greater than the maximum sum of the edge lengths on a path to a leaf in $R$, then increase the edge length from the root to the right subtree by the positive difference between the two.
Conversely, if the maximum sum of the edge lengths on a path to a leaf in $R$ starting from the root is greater than the maximum sum of the edge lengths on a path to a leaf in $L$, then increase the edge length from the root to the left subtree by the positive difference between the two.
I am having trouble proving the following:
$1)$ The resulting tree upon termination of this algorithm is a zero-skew tree (the length from the root to any leaf is the same).
$2)$ The sum of the edge lengths is minimized with this algorithm.
I have tried to prove these facts in many ways, such as induction and direct proof, but I am having a lot of difficulty doing so. The algorithm makes sense to me intuitively, but I'm having trouble explaining why it works formally.
I would greatly appreciate some help in solving this problem.