How can I make the following tree using weighted quick union

Question

So what weighted quick union is is connecting two trees together and always making the smaller tree the child of the bigger tree. So if I have this graph: tree

then is it possible to make this graph by performing weighted quick union on a bunch of 1 node graphs and connecting them together. I'm trying to figure this out but if the smaller tree always has to be the child of the bigger tree and how you always have to connect the root of one tree to the root of the other tree, I don't see how this can be done. Does anyone thing it's possible to do this or can you not make a tree like that with weighted quick union?

Answer 1

It is impossible.

Hint:

• The easiest way to show this is to prove that any tree resulting from that operation has a certain bound on its height with regard to number of total elements. Your example violates this bound.
• A more basic, direct method for that particular instance would be to prove that such a union cannot produce graphs of size $\geq 3$ in which root has only one child, thus, it's impossible to obtain path $1\to6\to5$ in which $6$ has only one child, but its whole subtree is big.

I hope this helps $\ddot\smile$