Walkthrough - Different Subtrees

Tree: $1$ has children $2, 3$. Node $2$ has child $4$. Node $3$ has child $5$. Query: LCA$(4, 5)$. Both have $depth = 2$. Check up[4][1] = 1, up[5][1] = 1: same, skip.

Check up[4][0] = 2, up[5][0] = 3: different, jump both. Now $a = 2$, $b = 3$. No more bits to check. Return up[2][0] = 1. LCA is $1$. The nodes are in different subtrees, so their meeting point is the root. This example shows how the algorithm handles nodes in separate branches.