Follow

Keep Up to Date with the Most Important News

By pressing the Subscribe button, you confirm that you have read and are agreeing to our Privacy Policy and Terms of Use
Contact

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

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

MEDevel.com: Open-source for Healthcare and Education

Collecting and validating open-source software for healthcare, education, enterprise, development, medical imaging, medical records, and digital pathology.

Visit Medevel

>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.

Add a comment

Leave a Reply

Keep Up to Date with the Most Important News

By pressing the Subscribe button, you confirm that you have read and are agreeing to our Privacy Policy and Terms of Use

Discover more from Dev solutions

Subscribe now to keep reading and get access to the full archive.

Continue reading