Concept Flow - Path Compression in Union Find
Start: Find(x)
Is parent[x
No
Recursively find parent of parent[x
Set parent[x
Return root
Path Compression flattens the tree by making each node point directly to the root during find operation.
0
0
Path Compression in Union Find in DSA Typescript - Execution Trace
Execution Sample
DSA Typescript
function find(x: number): number {
if (parent[x] !== x) {
parent[x] = find(parent[x]);
}
return parent[x];
}This code finds the root of x and compresses the path by pointing x directly to the root.
Execution Table
| Step | Operation | Node x | parent[x] before | Recursive call | parent[x] after | Visual State |
|---|---|---|---|---|---|---|
| 1 | Call find(4) | 4 | 3 | find(3) | TBD | parent[4] points to 3 |
| 2 | Call find(3) | 3 | 1 | find(1) | TBD | parent[3] points to 1 |
| 3 | Call find(1) | 1 | 1 | No recursion | 1 | parent[1] points to itself (root) |
| 4 | Return from find(1) | 3 | 1 | - | 1 | parent[3] updated to 1 (path compressed) |
| 5 | Return from find(3) | 4 | 3 | - | 1 | parent[4] updated to 1 (path compressed) |
| 6 | Final return | 4 | 1 | - | 1 | Root of 4 is 1, path compressed |
| 7 | Call find(5) | 5 | 5 | No recursion | 5 | parent[5] points to itself (root) |
| 8 | Final return | 5 | 5 | - | 5 | Root of 5 is 5 |
💡 Recursion stops when parent[x] == x, meaning root is found.
Variable Tracker
| Variable | Start | After Step 1 | After Step 2 | After Step 4 | After Step 5 | Final |
|---|---|---|---|---|---|---|
| parent[4] | 3 | 3 | 3 | 3 | 1 | 1 |
| parent[3] | 1 | 1 | 1 | 1 | 1 | 1 |
| parent[1] | 1 | 1 | 1 | 1 | 1 | 1 |
| parent[5] | 5 | 5 | 5 | 5 | 5 | 5 |
Key Moments - 3 Insights
Why does find(4) call find(3) before updating parent[4]?
Because parent[4] is 3, which is not root, so we must find root of 3 first (see steps 1 and 2 in execution_table).
Why is parent[3] updated to 1 after find(1) returns?
Path compression sets parent[3] directly to root 1 to flatten the tree (see step 4).
What stops the recursion in find function?
When parent[x] equals x, meaning x is root, recursion stops (see step 3).
Visual Quiz - 3 Questions
Test your understanding
Look at the execution_table, what is parent[4] after step 5?
💡 Hint
Check the 'parent[x] after' column for step 5 in execution_table.
At which step does the recursion stop because parent[x] == x?
💡 Hint
Look for 'No recursion' in the 'Recursive call' column in execution_table.
If parent[4] was initially 4, how many recursive calls would find(4) make?
💡 Hint
If parent[4] == 4, recursion stops immediately (see variable_tracker start values).
Concept Snapshot
Path Compression in Union Find: - Used in find(x) to flatten tree. - If parent[x] != x, recursively find root. - Set parent[x] = root to compress path. - Speeds up future find operations. - Stops recursion when parent[x] == x.
Full Transcript
Path Compression in Union Find is a technique to speed up the find operation by making nodes point directly to the root. The find function checks if the node is its own parent (root). If not, it recursively finds the root of its parent and updates the node's parent to this root. This flattens the tree structure, reducing the time for future finds. The recursion stops when a node is its own parent. The execution table shows step-by-step how parent pointers change during find(4) and find(5). Variable tracker shows parent array changes. Key moments clarify why recursion happens and when it stops. The visual quiz tests understanding of parent updates and recursion stopping conditions.