Number of nodes in the bottom level of a balanced binary tree

Question

I am wondering about two questions that came up when studying about binary search trees. They are the following:

What is the maximum number of nodes in the bottom level of a balanced binary search tree with n nodes?

What is the minimum number of nodes in the bottom level of a balanced binary search tree with n nodes?

I cannot find any formulas in my textbook regarding this. Is there any way to answers these questions? Please let me know.

Answer 1

Assuming that it's a full binary tree, the number of nodes in the leaf will always be equal to (n/2)+1.

For the minimum number of nodes, the total number of nodes could be 1 (satisfying the condition that it should be a balanced tree).

Answer 2

Using notation:

• H = Balanced binary tree height
• L = Total number of leaves in a full binary tree of height H
• N = Total number of nodes in a full binary tree of height H

The relation is L = (N + 1) / 2 as demonstrated below. That would be the maximum number of leaf nodes for a given tree height H. The minimum number of nodes at a given height is 1 (cannot be zero, because then the tree height would be reduced by one).

Drawing trees with increasing heights, one can observe that:

H = 1, L = 1, N = 1
H = 2, L = 2, N = 3
H = 3, L = 4, N = 7
H = 4, L = 8, N = 15
...

The relation between tree height (H) and the total number of leaves (L) and the total number of nodes (N) becomes apparent:

L = 2^(H-1)
N = (2^H) - 1

The correctness is easily proven using mathematical induction.

Examples above show that it is true for small H. Simply put in the value of H (e.g. H=1) and compute L and N. Assuming the formulas are true for some H, one can show they are also true for HH=H+1:

For L, the assumption is that L=2^(H-1) is true. As each node has two children, increasing the height by one is going to replace each leaf node with two new leaves, effectively doubling the total number of leaves. Therefore, in case of HH=H+1, the total number of leaves (LL) is going to be doubled:

LL = L * 2
   = 2^(H-1) * 2
   = 2^(H)
   = 2^(HH-1)

For N, the assumption is that N=(2^H)-1 is true. Increasing the height by one (HH=H+1) increases the total number of nodes by the total number of added leaf nodes. Therefore,

NN = N + LL
   = (2^H) - 1 + 2^(HH-1)
   = 2^(HH-1) - 1 + 2^(HH-1)
   = 2 * 2^(HH-1) - 1
   = (2^HH) - 1

Applying the mathematical induction, the correctness is proven.

H can be expressed in terms of N:

N = (2^H) - 1        // +1 to both sides
N + 1 = 2^H          // apply log2 monotone function to both sides
log2(N+1) = log2(2^H)
          = H * log2(2)
          = H

The direct relation between L and N (which is the answer to the question asked) is:

L = 2^(H - 1)                 // replace H = log2(N + 1)
  = 2^(log2(N + 1) - 1)
  = 2^(log2(N + 1) - log2(2))
  = 2^(log2( (N + 1) / 2 ))
  = (N + 1) / 2

For Big O analysis, the constants are discarded, so the Binary Search Tree lookup time complexity (i.e. H with respect to the input size N) is O(log2(N)). Also, keeping in mind the formula for changing the logarithm base:

log2(N) = log10(N) / log10(2)

and discarding the constant factor 1/log10(2), where instead of 10 one can have an arbitrary logarithm base, the time complexity is simply O(log(N)) regardless of the chosen logarithm base constant.

Answer 3

I got the answers from my professor.

1) Maximum number of nodes at the last level: ⌈n/2⌉

If there is a balanced binary search tree with 7 nodes, then the answer would be ⌈7/2⌉ = 4 and for a tree with 15 nodes, the answer would be ⌈15/2⌉ = 8. But what is troubling is the fact that this formula gives the right answer only when the last level of a balanced tree is completely filled from left to right. For example, a balanced binary search tree with 5 nodes, the above formula gives an answer of 3 which is not true because a tree with 5 nodes can contain a maximum nodes of 4 nodes at the last level. So I am guessing he meant full balanced binary search tree.

2) Minimum number of nodes at the last level: 1

Answer 4

The maximum number of nodes at level L in a binary tree is 2^L (if you assume that the vertex is level 0). This is easy to see because at each level you spawn 2 children from each previous leaf. The fact that it is balanced/search tree is irrelevant. So you have to find the biggest L such that 2^L < n and subtract it from n. Which in math language is:

The minimum number of nodes depends on the way you balance your tree. There can be height-balanced trees, weight-balanced trees and I assume other balanced trees. Even with height balanced trees you can define what do you mean by a balanced tree. Because technically a tree of 2^N nodes that has a hight of N + 2 is still a balanced tree.