# Speculating big O for a binary tree

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

• What have you tried so far? Have you tried working through some examples or extreme cases? Have you tried working out what the value will be for a balanced tree? For a maximally unbalanced tree? You should be able to answer your question on your own if you just work through those two cases...
– D.W.
Mar 18, 2017 at 18:58
• Cross-posted: cs.stackexchange.com/q/71727/755, stackoverflow.com/q/42883388/781723. Please do not post the same question on multiple sites. Each community should have an honest shot at answering without anybody's time being wasted.
– D.W.
Mar 29, 2017 at 7:00

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.
• Right. Therefore there would be no tree with sum of tags at $O(n^{2})$ because that would violate the tight upper bound. Now I wonder if we can say that there can possibly be a tree with sum of tags at $O(n)$: I'm not sure, maybe that's possible, because $O(n)$ doesn't violate tight upper bound. Mar 19, 2017 at 8:00
• On the contrary, every tree would have sum of tags $O(n^2)$. Don't forget that big O is just an upper bound. Mar 19, 2017 at 8:02