# 3 stages of union find

Investigated this when doing query optimization.

## Naive approach O(N^2)

When doing union and merging new sub-trees, set all sub-tree roots to base root.

For example:

```
root(1) = 1-2-3
root(3) = 3-4
union(1,3) -- 3 is the new parent
```

We have to set all of 1’s children to have 3 as their root.

This takes N time since we union N nodes. N time for each union, since we need to iterate over all nodes, and update their root if they have `1`

as root (are `1`

‘s children’).

## Better approach O(N)

Use indirect union instead.

Rather than linking all of root(1) children to `3`

, just link the root `1`

->`3`

.

This takes O(1) time / union.

## Betterer approach O(log2N)

Source: https://www.hackerearth.com/practice/notes/disjoint-set-union-union-find/