10
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – JeffE Jul 16 '12 at 23:30
  • $\begingroup$ @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?" $\endgroup$ – Timeless Jul 17 '12 at 1:45
  • $\begingroup$ 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. $\endgroup$ – Raphael Jul 22 '12 at 9:19
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Is that possible to show the implementation code for $\operatorname{avh}_1$, I don't quite get the idea how to do it recursively $\endgroup$ – Timeless Jul 26 '12 at 1:42
  • $\begingroup$ @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? $\endgroup$ – Raphael Jul 26 '12 at 6:19
  • $\begingroup$ I mean the implementation code using recursion $\endgroup$ – Timeless Jul 26 '12 at 6:27
  • $\begingroup$ @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. $\endgroup$ – Raphael Jul 26 '12 at 6:43
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Timeless Jul 17 '12 at 1:40
  • $\begingroup$ @null You can define it that way if you insist, but then the two definitions will not be consistent. $\endgroup$ – Joe Jul 17 '12 at 22:12

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.