title: Disjoint set with Union by Size and Path Compression; possible for taller tree to become subtree of shorter tree?
body: <p>Hi this is my first time posting here,</p>
  
  <p>I have been trying to work out a question for studying but haven't been able to figure it out:</p>
  
  <p>We consider the forest implementation of the disjoint-set abstract data type, with Weighted Union by size and Path Compression. Initially, each element is in a one-node tree.</p>
  
  <p>Starting from the above initial state:</p>
  
  <ol>
  <li><p>give a (short) sequence of UNION and FIND operations in which the last operation is a UNION that causes a taller tree A to become the subtree of a shorter tree B (ie. the height of A is strictly larger than the height of B).</p></li>
  <li><p>Show the two trees A and B that the last UNION merges</p></li>
  </ol>
  
  <p>Hint: You can start from n = 9 elements, each one in a one-node tree.</p>
  
  <hr>
  
  <p>I'm not sure how that would work since the smaller tree always gets merged with the larger tree because of union by size?</p>
  
  <p>Thanks.</p>