A complete binary tree is defined as a tree where each node has either 2 or 0 children.
Suppose given a complete binary tree with $n$ leaves, there are $n-1$ internal nodes.
For any node $i$ , denote the depth of left subtree $l_i$, and the depth of right subtree $r_i$.
For each node $i$ of this tree, i'm interested in this quantity: $q(i) := max(l_i, r_i)*min(l_i, r_i) - min(l_i, r_i)^2 $
Now my question is what's the upper bound of sum over all internal nodes: $Q = \sum_{i=1}^{n-1} q(i)$ ?
The lower bound is simple to have, when the tree is balanced then $q(i) = 0$, thus $Q=0$.
Some attempt: denotes the maximum depth of the tree as $d$, then the maximum level 1 quantity is reached when one sub-tree has depth $d-1$, and the other sub-tree has depth $d/2$. Then we can derive the recusive quantity $Q(d) = Q(d-1) + Q(d/2) + (d-1 - d/2)*d/2$, and the $Q(1)$ is simply 1.