Section Recap

You learned binary lifting, a technique that answers $k$-th ancestor queries in $O(\log k)$ time after $O(n \log n)$ preprocessing. You built the sparse table up[v][j] (the $2^j$-th ancestor of $v$) using the recurrence up[v][j] = up[up[v][j-1]][j-1]. You answered queries by decomposing $k$ into powers of $2$.

You solved three problems: Company Queries I (basic ancestor queries), Company Queries II (LCA with binary lifting), and Kth Ancestor of a Tree Node (LeetCode class-based version). You are now ready for more advanced tree techniques.