CODEWITHSUNDEEP
treedisjoint-setsdisjoint-union
Ajay
Ajay

Reputation: 49

how to calculate height of disjoint trees implemented with union by rank heuristic?

Since very long i am trying to solve a question from a quiz , but i am getting wrong answer , the question is as follows :-

Consider the program:

for i from 1 to 12:
MakeSet(i)
Union(2, 10)
Union(7, 5)
Union(6, 1)
Union(3, 4)
Union(5, 11)
Union(7, 8)
Union(7, 3)
Union(12, 2)
Union(9, 6)

Assume that the disjoint sets data structure is implemented as disjoint trees with union by rank heuristic.

Compute the product of the heights of the resulting trees after executing the code. For example, for a forest consisting of four trees of height 1, 2, 3, 1 the answer would be 6. (Recall that the height of a tree is the number of edges on a longest path from the root to a leaf. In particular, the height of a tree consisting of just one node is equal to 0.)

i solve this question and get the answer as 5 (2*2*1), but it is showing wrong when i submit it, i have tried many times ,please me in calculating this ...

Upvotes: 2

Views: 3312

Answers (1)

R Chang
R Chang

Reputation: 63

I figured it out! the answer is 2. with the explanation Correct: Right! There will be 3 trees of height 1, 1, and 2. (i run into this question on edx but that submission only takes 2 as the answer)

I guess the tree should look something like this:

    tree1,tree2,tree 3

level0: 4 , 1 , 2

level1: 3 5 , 6 9 , 10 12

level2: 8 7 11

you can try it with this visualization website https://www.cs.usfca.edu/~galles/visualization/DisjointSets.html

Upvotes: 1

Related Questions