2
$\begingroup$

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

Like this image


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

$\endgroup$
  • 2
    $\begingroup$ 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... $\endgroup$ – D.W. Mar 18 '17 at 18:58
  • $\begingroup$ 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. $\endgroup$ – D.W. Mar 29 '17 at 7:00
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – user4838962 Mar 19 '17 at 8:00
  • $\begingroup$ On the contrary, every tree would have sum of tags $O(n^2)$. Don't forget that big O is just an upper bound. $\endgroup$ – Yuval Filmus Mar 19 '17 at 8:02
  • $\begingroup$ Regarding your other question, you can increase the number of vertices without changing the sum of tags by replacing a leaf with a path. $\endgroup$ – Yuval Filmus Mar 19 '17 at 8:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.