get a binary tree of height n + 1 from one of height n

Tryer outer 0
Viewed 23

"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?

binary-tree
1 Answers

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.

trincot0
Related