3

A balanced binary tree is a binary tree for which the difference in height between any node's two sub-trees is at most 1. (Such a tree is known as an AVL tree.)

What is the minimum number of leaves in such a tree of height $h$?

My thinking is this:

Let $H(h)$ be a function that returns the minimum number of leaves in a balanced binary tree of height $h$, then

$H(h) = H(h-1) + H(h-2) +1 -1 = H(h-1) + H(h-2) = Fibonacci(h)$.

By inspection, $H(0) = 0$ and $H(1) = 1$.

That recursive formula is correct because a balanced binary tree of height $h$ with a minimum number of leaves must have as one sub-tree a balanced binary tree of height $h-1$ with a minimum number of leaves, and as the other sub-tree a balanced binary tree of height $h-2$ with a minimum number of leaves. (Remember that at most a difference of one is permitted between two sub-trees, hence the $h-1$ vs $h-2$.)

We add one and subtract one because in going from height $h-1$ to $h$ we add, and simultaneously remove, a leaf.

Is my reasoning correct?

josh
  • 35

1 Answers1

2

Your reasoning is basically correct, but three small points:

  • If the tree's height is defined as usual as the number of edges on the longest path from the root to a leaf, then your indexing is off by one – the only tree of height $0$ has one leaf, and the minimal tree of height $1$ has one leaf, so it should be $h(0)=h(1)=1$.

  • Technically, you shouldn't write "$=\text{Fibonacci}(h)$" before stating the initial values, since only the recurrence and the initial values together imply that it's the Fibonacci sequence (or, if I'm right about the height, a shifted version of the Fibonacci sequence).

  • I'm not sure what you mean by "we add, and simultaneously remove, a leaf" – I would have thought that we just stick two trees onto the root and the number of leaves is simply their sum.

joriki
  • 238,052
  • 1
    This question comes from the book Algorithms and Data Structures in Java, Second Edition, by Adam Drozdek. He defines the height as you do but adds one. No one else appears to do this. I take your point about point 2. In regards to point 3, I understand. Thank you! – josh Jul 20 '15 at 14:35
  • counting path edges: $h(0)$ (just a root node) should be different from $h(1)$ (root node plus one child node) and be different from the empty tree. I think the author chose his definition of height to enforce the Fibonacci series as solution. – mvw Jul 20 '15 at 14:56
  • @mvw: The problem asks for the number of leaves. Both for $h(0)$ (just a root node) and for $h(1)$ (root note plus one child node), there's one leaf (if a leaf is defined as usual as a node without descendants). – joriki Jul 20 '15 at 15:09
  • Thanks, that makes more sense then, I counted nodes. – mvw Jul 20 '15 at 15:13
  • @mvw: I did at first, too :-) – joriki Jul 20 '15 at 15:19