Question

Show that the average depth of a leaf in a binary tree with \(n\) vertices is \({\bf{\Omega (logn)}}\).

Short answer

Average depth of a leaf in a binary tree is \({\bf{\Omega (logn)}}\)

Step-by-step solution

Definition

The children of m are all vertices below m that are connected to m by an edge.

Big-Omega Notation: \(f\left( x \right)\) is \(\Omega (g(x))\) if there exist constants C and k such that

\(|f(x)| \ge C|g(x)|\)whenever \(x > k\).

A complete m-ary tree is a full m-ary tree in which every leaf is at the same level

Height

Given: A binary tree T with n vertices.

T being a binary tree means that every vertex has number 1 or 2 children.

Let us assume that T has height h. We are trying to derive a lower bound for the average depth.

If there are any internal vertices at a level less than h-1 with less than 2 children, then move one of the leaves to the position of the missing child.

Note: This will only lower the average depth of the leaf and thus won't affect the lower bound.

Repeat this process until there are no more interval vertices at a level less than h-1 with less than 2 children.

One then assumes that the resulting tree T’ then has only leaves at level h and h-1

(Note: if not, then we rename the height h as the height of the new tree T’. Since the new and old value of h differ by a constant, it won't affect the Big-Omega estimate).

Finding \({\bf{h}}\)

Next, one deletes all vertices at level h (which will only lower the average depth by 1 and thus won't affect the big-Omega estimate).

The resulting tree T’ is then a complete binary tree, while one knows that T” has \({m^{h - 1}} = {2^{h - 1}}\) leaves (by exercise 28 or exercise 20 in the global edition). Moreover, these \({2^{h - 1}}\) leaves all occur at depth h-1. Thus, the average depth of the leaves is h-1 as well.

One also knows that the number of leaves is \(\frac{{{m^h} - 1}}{{m - 1}}\). In this case \(m = 2\) and \(h - 1\) instead of h:

\(n = \frac{{{m^{h - 1}} - 1}}{{m - 1}} = \frac{{{2^{h - 1}} - 1}}{{2 - 1}} = \frac{{{2^{h - 1}} - 1}}{1} = {2^{h - 1}} - 1\)

Step 4:Solving the equation

Let us solve the equation \(n = {2^{h - 1}} - 1\) to h:

\(h = log(n + 1) + 1\)

Thus, the average depth of the leaves is then \(h - 1 = log(n + 1)\), which is\({\bf{\Omega (logn)}}\).