Running time based on smallest subtree

Question

I've constructed an algorithm on (rooted) binary trees, where the running time at a node depends on the size of its smaller subtree, where we compute from each leaf upwards towards the root.
More specifically, at each node, a constant amount of time is required for each node in the smallest of its 2 subtrees.

The running time for a tree with $n$ nodes is then easily bounded by $O(n^2)$, however, I conjecture that the running time is bounded by $O(n \log n)$, since I think $\sum_{x\in V(T)}\min(|V_l(x)|, |V_r(x)|) \leq O(n \log n)$ holds.

How would I go about proving this?

Answer 1

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>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} &\sum_{x\in V(T)}\min(l(x), r(x)) \\ &= \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))\\ &\leq p + p\log p +(n-1-p)\log(n-1-p)\\ &= p + p\log p +p\log(n-1-p) + (n-1-2p)\log(n-1-p)\\ &= p + p\log (p(n-1-p)) + (n-1-2p)\log n\\ &\le p + p\log \left((\frac{n-1}2)^2\right) + (n-1-2p)\log n\\ &\le p + 2p\log \left(\frac{n}2\right) + (n-1-2p)\log n\\ &= (1- 2\log2)p + (n-1)\log n\\ &\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$.