"To get a binary tree of height n + 1 from one of height n, we can create, at most, two leaves in place of each previous one."
Introduction to Formal Languages and Automata – Peter Linz
Could someone explain to me (visually) how we get here a binary tree of height n + 1 by just doubling the leaves?
>Solution :
The words to stress in the quote are "in place of".
Here is an example of a binary tree with height 2:
1
/ \
2 3
/
4
It has two leaves: one with value 3 and one with value 4.
If we replace each of those leaves with a little subtree that has a parent node with 2 leaves, then we get:
1
/ \
2 3
/ / \
4 c d
/ \
a b
Here we see that the resulting tree has height 3.
In general, when a tree has a height of 𝑛, then there is at least one leaf at level 𝑛 in that tree (when starting the level numbering at 0). When that leaf is replaced with a little subtree with a parent node that has 2 leaves, it is clear that those new leaves reside on level 𝑛 + 1, giving the tree a height of 𝑛 + 1.
The words "at most, two leaves" indicate that the above would also work if we replaced the existing leaves with little subtrees that just have a parent with one leaf.