# What is the average height of a binary tree?

Is there any formal definition about the average height of a binary tree?

I have a tutorial question about finding the average height of a binary tree using the following two methods:

1. The natural solution might be to take the average length of all possible paths from the root to a leaf, that is

$\qquad \displaystyle \operatorname{avh}_1(T) = \frac{1}{\text{# leaves in } T} \cdot \sum_{v \text{ leaf of } T} \operatorname{depth}(v)$.

2. Another option is to define it recursively, that is the average height for a node is the average over the average heights of the subtrees plus one, that is

$\qquad \displaystyle \operatorname{avh}_2(N(l,r)) = \frac{\operatorname{avh}_2(l) + \operatorname{avh}_2(r)}{2} + 1$

with $\operatorname{avh}_2(l) = 1$ for leafs $l$ and $\operatorname{avh}_2(\_) = 0$ for empty slots.

Based on my current understanding, for example the average height of the tree $T$

    1
/ \
2   3
/
4


is $\operatorname{avh}_2(T) = 1.25$ by the second method, that is using recursion.

However, I still don't quite understand how to do the first one. $\operatorname{avh}_1(T) = (1+2)/2=1.5$ is not correct.

• Can you provide some context? There is not such thing as a "correct" mathematical definition; you can define "average height of a binary tree" however you like. (Average of what over what distribution?) But different definitions will more or less useful for different applications. – JeffE Jul 16 '12 at 23:30
• @JeffE "It is not immediately obvious how to define the average height of a binary tree. Perhaps the most natural solution might be to have the average length of the possible paths from the root to a leaf. A simpler (perhaps even simplistic) solution is to say that the average height for a node is the average over the average heights of the subtrees plus one. You fill find it easier to code this alternative. Can you give examples to demonstrate the difference?" – Timeless Jul 17 '12 at 1:45
• I tried to make your post more clear by giving precise definitions of the two variants. Please check that I interpreted your text correctly. In particular, you were missing the anchor for the second variant; whether you take leaves to have height one or zero makes a difference. – Raphael Jul 22 '12 at 9:19

There is no reason to believe that both definitions describe the same measure. You can write $\operatorname{avh}_1$ recursively, too:

$\qquad \displaystyle \operatorname{avh}_1(N(l,r)) = \frac{\operatorname{lv}(l)(\operatorname{avh_1}(l) + 1) + \operatorname{lv}(r)(\operatorname{avh_1}(r) + 1)}{\operatorname{lv}(l) + \operatorname{lv}(r)}$

with $\operatorname{avh}_1(l) = 0$ for leaves $l$. If you don't believe that this is the same, unfold the definition of $\operatorname{avh}_1$ on the right hand side, or perform an induction proof.

Now we see that $\operatorname{avh}_1$ works quite differently from $\operatorname{avh}_2$. While $\operatorname{avh}_2$ weighs the recursive heights of a nodes children equally (adding and dividing by two), $\operatorname{avh}_1$ weighs them according to the number of leaves they contain. So they are the same (modulo the anchor) for leaf-balanced trees, that is balanced in the sense that sibling trees have equally many leaves. If you simplify the recursive form of $\operatorname{avh}_1$ with $\operatorname{lv}(l) = \operatorname{lv}(r)$ this is immediately apparent. On unbalanced trees, however, they are different.

Your calculations are indeed correct (given your definition); note that the example tree is not leaf-balanced.

• Is that possible to show the implementation code for $\operatorname{avh}_1$, I don't quite get the idea how to do it recursively – Timeless Jul 26 '12 at 1:42
• @null: Sorry, I don't understand the question. Do you mean how to prove that the recursive definition of $\operatorname{avh}_1$ is equivalent to yours? – Raphael Jul 26 '12 at 6:19
• I mean the implementation code using recursion – Timeless Jul 26 '12 at 6:27
• @null: You can copy the formula almost literally, provided you incorporate the base case. How to do that precisely depends on your programming language and tree implementation. I suggest you take the recurrence to Stack Overflow if implementation is a hurdle for you. – Raphael Jul 26 '12 at 6:43

Edit: Jeffe makes a good point in his comment above. You should probably read "correct vs incorrect" in the following answer as "convenient/consistent vs inconsistent".

It seems to be that your second calculation is incorrect. Let the height of a subtree with a single node (i.e. a leaf) be 0. Then the height of the subtree root at:

• height at 4 is 0
• height at 3 is 0
• height at 2 is average height at 3 + 1 = 0 + 1 = 1
• height at 1 is average of heights at 2 and 3 = (0 + 1)/2 + 1 = 1.5

I think you are doing the first calculation correctly, and 1.5 is the right answer.

• the idea is null node with height of -1, based on the 2nd approach, a node's average height is average of subtrees plus 1, node 4's average height is ((-1)+(-1))/2+1=0, node 2's average height is (0+(-1))/2+1=0.5, and so the root's average height is 1.25. – Timeless Jul 17 '12 at 1:40
• @null You can define it that way if you insist, but then the two definitions will not be consistent. – Joe Jul 17 '12 at 22:12