Speculating big O for a binary tree
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&gt;0$, $\sigma(T) \leq Cf(n)$ for all trees $T$ on $n$ nodes, and furthermore for some constant $c&gt;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.