When we do union by rank we merge the smaller tree into the larger tree. I dont understand why we do this exactly?


1 Answer 1


Imagine merging the larger tree into the smaller one. By doing this, you are guarantying that the new tree will have depth one more than the larger tree's depth. But, if you were to merge the smaller tree into the larger one - the increase in depth would occur only in the branches of the small tree, and since it is small it wont impact the depth (unless the smaller tree is the same size as the larger tree).

So to summarize - by doing this you ensure to create the lowest possible depth you can.

Try to run on some examples both cases (merging largest to smallest and merging smallest to largest) and see the differences for yourself


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.