Running time based on smallest subtree
A nice question!

As the OP has pointed out, it is enough to show the following inequality for any tree $T$ of $n\gt0$ nodes, where for any node $x$, $l(x)$ is the number of nodes in the left subtree of $x$ and $r(x)$ is the number of nodes in the right subtree of $x$. 

$$\sum_{x\in V(T)}\min(l(x), r(x)) \leq n \log n$$

Proof by mathematical induction.


base case when $n=1$. Both side is 0.
Suppose it is true when the number of nodes in the tree is smaller than $n$. Let us consider a tree $T$ with $n&gt;1$ node. Let the left subtree $T_l$ of the root node has $p$ node and the right subtree $T_r$ of the root node has $n-1-p$ node. There are two cases.


$p=0$ or $p=n-1$ is easy.
$p\neq0$ and $p\neq n-1$. (This case is only possible when $n\ge3$.) WLOG assume $p\le n-1-p$; otherwise we can switch the left subtree and the right subtree.



$$\begin{aligned}
&amp;\sum_{x\in V(T)}\min(l(x), r(x)) \\
&amp;= \min(p, n-1-p) + \sum_{x\in V(T_l)}\min(l(x), r(x))+\sum_{x\in V(T_r)}\min(l(x), r(x))\\
&amp;\leq p + p\log p +(n-1-p)\log(n-1-p)\\
&amp;= p + p\log p +p\log(n-1-p) + (n-1-2p)\log(n-1-p)\\
&amp;= p + p\log (p(n-1-p)) + (n-1-2p)\log n\\
&amp;\le p + p\log \left((\frac{n-1}2)^2\right) + (n-1-2p)\log n\\
&amp;\le p + 2p\log \left(\frac{n}2\right) + (n-1-2p)\log n\\
&amp;= (1- 2\log2)p + (n-1)\log n\\
&amp;\le n\log n
\end{aligned}$$

Proof is done. Note that we have actually proved a tighter upper bound, $\frac1{2}n \log_2 n$.