# 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)

Rather than linking all of root(1) children to 3, just link the root 1->3.