V

Algorithm Visualizer

ZHEN
Share on WeiboShare on XGitHub repositoryAuthor website
Learning ToolsAlgorithm Complexity ReferenceAlgorithm Learning Paths
Data StructuresArrayLinked ListStackQueue and DequeBinary Search TreeBinary HeapHash TableGraphTrieDisjoint Set UnionLRU CacheSkip ListSegment TreeB+ TreeBloom FilterFenwick Tree
SortingBubble SortCocktail Shaker SortBitonic SortSelection SortInsertion SortBinary Insertion SortShell SortMerge SortTop-Down Merge SortQuick SortThree-Way Quick SortDual-Pivot Quick SortHeap SortCounting SortRadix SortBucket Sort
Graph AlgorithmsDijkstra's Shortest PathKruskal's Minimum Spanning TreePrim's Minimum Spanning TreeBellman-Ford Shortest PathsTopological SortFloyd-WarshallStrongly Connected Components2-SATMaximum FlowBipartite MatchingLowest Common AncestorEulerian Path
Dynamic ProgrammingEdit Distance0/1 KnapsackUnbounded KnapsackLongest Common SubsequenceLongest Increasing SubsequenceCoin ChangeStone MergingTraveling Salesperson DPTree Dynamic ProgrammingDigit DPRerooting DP
Backtracking and SearchN-QueensSubsetsPermutationsCombination SumMaze Solving with DFSNumber of IslandsWord SearchSudoku SolverA* Search
StringsKMP String MatchingRabin-Karp String MatchingBoyer-Moore String MatchingManacher's Longest Palindromic SubstringSuffix ArrayLCP ArrayAho-Corasick AutomatonZ Function
Math and Number TheorySieve of EratosthenesLinear SieveEuclidean AlgorithmBinary ExponentiationExtended Euclidean AlgorithmChinese Remainder TheoremEuler's Totient FunctionMiller-Rabin Primality TestFast Fourier TransformPollard's Rho Factorization
Computational GeometryConvex HullRotating CalipersClosest Pair of PointsLine Segment IntersectionBentley-Ottmann Sweep Line
SearchingBinary SearchLower and Upper BoundSearch in a Rotated Sorted ArrayBinary Search on the AnswerTernary Search

Lowest Common Ancestor

Build binary-lifting ancestors, align node depths, and jump together to find their deepest shared ancestor.

Core idea

Binary lifting stores each node's ancestor one, two, four, and more powers of two above it. Queries first equalize depths, then lift both nodes without jumping above their meeting point.

Read the visualization

The table builds from smaller jumps to larger ones. During a query, highlighted powers explain each depth alignment and synchronized jump before the shared parent is returned.

depthup⁰up¹up²
0
1
2
3
4
5
6
7

Root the tree and prepare depths plus powers-of-two ancestor columns.

1function lca(n: number, fa: number[], LOG: number, u: number, v: number): number {
2 const depth = new Array(n).fill(0); // build table: depth + up[0] = fa
3 const up = [fa.slice()];
4 for (let i = 1; i < n; i++) depth[i] = depth[fa[i]] + 1;
5 for (let k = 1; k < LOG; k++) // build
6 up.push(up[k - 1].map((p) => (p < 0 ? -1: up[k - 1][p])));
7 if (depth[u] < depth[v]) [u, v] = [v, u];
8 for (let k = LOG - 1; k >= 0; k--) // ① align: depth difference align
9 if ((depth[u] - depth[v]) & (1 << k)) u = up[k][u];
10 if (u === v) return u;
11 for (let k = LOG - 1; k >= 0; k--)
12 if (up[k][u] !== up[k][v]) { // ② jump: jump different jump
13 u = up[k][u];
14 v = up[k][v];
15 }
16 return up[0][u]; // ③ answer child, parent answer answer
17}
tree0 root; 1,2 child; 3,4 as 1 child; 5 as 2 child; 6 as 3 child; 7 as 6 child
targetLCA(7, 4) and LCA(6, 5)
1 / 11

Complexity and tradeoffs

Time: Build O(V log V); query O(log V). Space: O(V log V). Binary lifting answers many static-tree ancestor and distance queries efficiently.

Invariant: After column j is built, every entry points exactly 2 to the power j edges upward, or to the root sentinel when that ancestor does not exist.

Where it fits

LCA preprocessing supports repeated ancestor, tree-distance, path, and virtual-tree queries on a static rooted tree. Dynamic trees require different machinery.