Speculating big O for a binary tree

Question

I have a binary tree with $n$ nodes. The tree is not necessarily balanced.

For each node of the tree, I count down the total number of the nodes for its left sub-tree as $n_L$ and then I count down the total number of the nodes for its right sub-tree as $n_R$. Then I calculate $\min(n_L,n_R)$ and then assign the minimum value as a tag to the node. I repeat this process to produce appropriate tags for all the nodes of the tree.

Now I wonder what is the big O for the sum of all the tags. I mean, I wonder if the sum of tags is $O(n\log n)$ or $O(n)$ or $O(n^2)$.

---

In the most unbalanced case, the binary tree is just a long list like figure below. In this case, I think sum of tags would be 0, therefore the big O would be $O(0)$.

---

In the case of a perfect binary tree, the tag of the root node might be $2^0\frac{n}{2^{0+1}}$ and at the next level, i.e. root's left and right children, sum of tags might be $2^1\frac{n}{2^{1+1}}$ and for the $i$th level of the perfect binary tree, the sum of tags might be $2^i\frac{n}{2^{i+1}}$.

At the $i$th level, sum of tags might become $2^i\frac{n}{2^{i+1}}=\frac{n}{2}$ therefore looks like that some of tags at each level might be $\frac{n}{2}$ and because a perfect binary three has a total height of $\log_2n$ hence the total sum of tags might be $\frac{n}{2}\log_2n$ and this implies that for a perfect binary tree, the big O for sum of tags might be $O(n\log_2n)$.

Answer 1

Let us denote by $\sigma(T)$ the sum of tags of a tree $T$. As you notice in your worked out examples, $\sigma(T)$ in general depends on the tree structure and not only on the number of nodes. What you are looking for is a tight upper bound on $\sigma(T)$ in terms of the number of nodes.

What is this tight upper bound? For each $n$, we want to know what is the maximal $\sigma$ for a tree having $n$ nodes. Denoting this by $\tau(n)$, this quantity satisfies $\sigma(T) \leq \tau(n)$ for all trees $T$ on $n$ nodes, and furthermore $\tau(n)$ cannot be replaced by any smaller value.

In fact, in practice we often don't care about finding the tight upper bound to this degree of accuracy. It is often enough to find a function $f(n)$ such that for some constant $C>0$, $\sigma(T) \leq Cf(n)$ for all trees $T$ on $n$ nodes, and furthermore for some constant $c>0$, $\sigma(T) \geq cf(n)$ for some tree $T$ on $n$ nodes.

You can prove by induction on $n$ that $\sigma(T) = O(n\log n)$ for all trees on $n$ nodes. Conversely, by taking a nearly complete binary tree $T_n$ on $n$ nodes (that is, a binary tree all of whose leaves are at heights $h,h+1$ for some $h$), you can check that $\sigma(T) = \Omega(n\log n)$. Hence $O(n\log n)$ is a tight upper bound for the sum of tags of binary trees on $n$ nodes.