Graph Theory37 sections · 1633 units
Open in Course

Common Mistakes

(Pitfalls to avoid)

Mistake 11: Forgetting to handle the case where one node is an ancestor of the other. If uu is an ancestor of vv, then lca(u,v)=ulca(u, v) = u. Check for this after equalizing depths.

Mistake 22: Using up[u][i] == up[v][i] as the condition to jump both nodes. You should jump when up[u][i] != up[v][i]. Jumping when ancestors match overshoots the LCA. Only jump when ancestors differ, so you stop just below the LCA.

Mistake 33: Not accounting for 00-indexing vs 11-indexing. If nodes are 11-indexed, adjust your upup table and depthdepth array so.