Graph Theory37 sections · 1633 units
Open in Course

Walkthrough

(Sample LCA trace)

Tree: 11 has children 2,32, 3. Node 22 has children 4,54, 5. Query: LCA(4,5)(4, 5). Both have depth=2depth = 2, so no initial jump. Check up[4][1], up[5][1]: both are 11 (same), so do not jump 212^1. Check up[4][0] = 2, up[5][0] = 2: same, so do not jump 202^0. Wait, they are already at the same parent. Return up[4][0] = 2.

LCA is 22. Since both nodes share the same parent, the algorithm finds it immediately.