Search code examples
algorithmtreeinsertion

Build a specific leftist tree?

I was practicing leftist trees and saw an example of min height-biased leftist tree on the textbook:

        2
      /   \
     7    50
    /    /
   11   80
  /
13

The question is, can I use only insertions to build this example?


I tried the following insertion sequence:

2  7  11  13  50  80

and it turns out to be this one:

      2
    /   \
  11     7
 /  \   /
13  50 80



So how can I achieve this? If it is impossible, why?
Furthermore, can the example tree on the textbook be built when other operations are allowed?

Solution

  • I figured it out! The following sequence is fine:

    13  11  7  2  50  80



    The idea is that the tree goes unbalanced when the sequence is descending. For example,

    4  3  2  1

    builds an unbalanced tree

          1
     /
    2
   /
  3
 /
4