Proving correctness and optimality of a greedy algorithm
Notation.
Given a binary tree $T$ and vertex $v$ of $T$, let $\ell_v$ and $r_v$ be the left and right children of vertex $v$ in $T$, respectively. Let $T_v$ be subtree of $T$ rooted at $v$.
Let $d_T(v)$ be the weighted distance between the root of $T$ and $v$ and $h(T) = \max_{v \in T} d_T(v)$.
If $(u,v)$ is an edge of $T$, let $w_T(u,v)$ be its weight.
With a slight abuse of notation, define $w(T) = \sum_{(u,v) \in T} w(u,v)$. 
Finally, we define the skew of $v$ as $s_T(v) = w_T(v, \ell_v) + h(T_{\ell_v}) - w_T(v, r_v) - h(T_{r_v})$ if $v$ is an interval vertex of $T$ and $s_T(v)=0$ if $v$ is a leaf of $T$.


  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).


We will show by induction on $i=0,1,\dots$ that, for all trees $T$ with $2^{i+1} - 1$ vertices, the algorithm returns a tree in which all vertices have skew $0$.

The base case $i=0$ is trivially true since $T$ must have exactly one vertex and the algorithm does nothing.

Suppose now that $i&gt;0$ and let $v$ be the root of $T$.
The trees $T_{\ell_v}$ and $T_{r_v}$ have exactly $\frac{(2^{i+1} - 1) - 1}{2} = 2^i - 1$ vertices and, by inductive hypothesis, the recursive calls on $T_{\ell_v}$ and $T_{r_v}$ ensure that all vertices, except possibly $v$, have skew $0$. The reweighing of $(v, \ell_v)$ and $(v, r_v)$ only affects the skew of $v$ and ensures that $s(v)=0$.


  The sum of the edge lengths is minimized with this algorithm.


Let $T'$ be the tree returned by the algorithm. Suppose that an optimal zero-skew tree $T^*$ obtained from the input tree $T$ by lengthening edges is such that $w(T^*) &lt; w(T')$.

Let $(u,v)$ be an edge of $T$ (where $u$ is the parent of $v$) such that
$w_{T^*}(u,v) &lt; w_{T'}(u,v)$ and the depth of $u$ is maximized.

Since  $s_{T^*}(u)=0$ and since $h(T_v^*) \ge h(T_v) = h(T'_v)$,
the sum of the weights in $T^*$ on each path from $v$ to a leaf in $T_v$
must have increased by at least $w_{T'}(u,v) - w_{T^*}(u,v)$.
Consider the subgraph of $T^*_v$ induced by the edges whose weight has not been increased w.r.t. $T$ and let $C$ be the connected component containing $v$.
Let $E$ be the set of edges with one endpoint in $C$ and the other in $T^*_v \setminus C$. Let $\Delta = \min_{(x,y) \in E} \{ w_{T^*}(x,y) - w_T(x,y) \}$.

Consider a new tree $T''$ that is obtained from $T'$ by reducing the weight of all edges in $E$ by $\Delta$ and increasing the weight of $(u,v)$ by $\Delta$.
The tree $T''$ is a feasible solution to your problem and weighs $w(T^*) - |E| \Delta + \Delta &lt; w(T^*)$ (since $|E|\ge 2$). This is a contradiction.