Why is there a big O for the minimum height of a tree?

In my algorithms and data structures course we’re given a proof for the upper bounds of the minimum height of a tree, a general tree, not a binary tree. In the course, the degree of a tree is based upon the largest amount of child nodes found in a parent node that’s defined as d. Secondly, the total number of nodes in the tree is defined as n. The big O for the minimum height of the tree is h <= ceiling(log_d(n)).

I tried to find out what it means by using an example: d = 4, n = 21 The result is h <= 3. What I’m now trying to understand is what the meaning of this result is. My biggest difficulty is just understanding why there is a big O used for a minimum.

Solution

The minimum height for a tree with 𝑛 nodes and a maximum degree of 𝑑 is when you pack those 𝑛 nodes with as many as possible in the upper levels of the tree, because you'll want to use as few levels as possible.

Practically, when you have 𝑛 nodes, you'd use the first as the root, the second batch of 𝑑 nodes as direct children of the root, and so filling up levels of the tree as needed. This is called a complete tree. There is no way to reduce the height in such a tree by moving nodes around. All levels -- except maybe the bottom one -- will already be filled at full capacity.

So for 𝑛=21 and 𝑑=4 you would build a complete tree as follows:

       __________________1___________________
      /            /           \             \
  ___2__       ___3___       ___4___       ___5___
 /  /\  \     /  / \  \     /  / \  \     /  / \  \
6  7  8  9   10 11 12 13   14 15 16 17   18 19 20 21

Note how this is a perfect tree: all levels are filled to maximum capacity. Adding even one more node will necessarily increase the tree's height.

It seems you are using a definition of height that is slightly different from the standard definition: the above pictured tree has height 2, not 3. Height is defined (standard) as the length of the longest path from root to leaf, expressed as the number of edges on that path.

Now to derive the formula for the minimum height we can observe how a level can contain 𝑑 times more nodes than the previous level (since all nodes on that level can have at most 𝑑 children).

So we have this maximum capacity of the levels:

1, 𝑑, 𝑑², 𝑑³, ... 𝑑^ℎ

The sum of those terms is a geometric series, and is therefore:

(𝑑^ℎ+1−1) / (𝑑−1)

Just to verify, for ℎ=2 and 𝑑=4 (the example), we then have:

(4²⁺¹−1) / (4−1) = (64−1) / 3 = 21

For a given height ℎ, the number of nodes in a complete tree is thus bounded like this:

(𝑑^ℎ−1) / (𝑑−1) < 𝑛 ≤ (𝑑^ℎ+1−1) / (𝑑−1)

Let's move things around to isolate ℎ:

𝑑^ℎ < 𝑛(𝑑−1) + 1 ≤ 𝑑^ℎ+1

If we subtract 1 from all terms, we can change the comparators:

𝑑^ℎ ≤ 𝑛(𝑑−1) < 𝑑^ℎ+1

Taking the logarithm with base 𝑑, we get:

ℎ ≤ log_𝑑(𝑛(𝑑−1)) < ℎ+1

And so we can now derive the minimum ℎ by rounding downwards:

ℎ = ⌊ log_𝑑(𝑛(𝑑−1)) ⌋

Verification

Let's try again with the example 𝑛=21 and 𝑑=4:

ℎ = ⌊ log_₄(21(4−1)) ⌋

ℎ = ⌊ log_₄(63) ⌋ = ⌊ 2.9886... ⌋ = 2

Big O

In Big O notation, the base of the logarithm is not significant, and things like rounding up or down are not relevant either.

So the big O for the minimum height given 𝑛 and 𝑑 is:

O(⌊ log_𝑑(𝑛(𝑑−1)) ⌋) = O(log(𝑛𝑑))