Algorithms
Advanced Tree Algorithms
Difficulty: Advanced
Finding the lowest common ancestor of two nodes by walking up parent pointers is O(n) per query, fine if you ask once but ruinous if you ask a million times on a tree of a million nodes. Binary Lifting precomputes the 2^k-th ancestor of...
Advanced Tree Algorithms
Finding the lowest common ancestor of two nodes by walking up parent pointers is O(n) per query, fine if you ask once but ruinous if you ask a million times on a tree of a million nodes. Binary Lifting precomputes the 2^k-th ancestor of every node in O(n log n) total, then answers LCA in O(log n) per query. The same compute-once-then-query-fast pattern unlocks an entire family of advanced tree algorithms.
Advanced Tree Algorithms covers that family. You will implement LCA via Binary Lifting and via the Euler Tour plus Range Minimum Query approach, where flattening the tree turns subtree queries into array-range queries. Heavy-Light Decomposition splits the tree into chains so path queries become O(log^2 n) segment-tree operations. Centroid Decomposition splits a tree of n nodes into O(log n) layers and powers distance and path-counting queries. The lesson finishes with the rerooting technique for tree DP, which computes DP results for every choice of root in linear total time instead of the naive O(n^2).
In Tree Algorithms, you mastered recursion-based tree problems and BST operations. This lesson trades simple recursion for preprocessing-and-query structures on top of the tree.
Next, Advanced Search Algorithms revisits BFS and DFS with heuristic refinements.
Prerequisites:
Tree AlgorithmsTopics:
What You'll Learn
By the end of this lesson, you will be able to:
Implement LCA with Binary Lifting using O(n log n) preprocessing and O(log n) per query.
Apply the Euler Tour technique to convert subtree queries into range queries on a flat array.
Implement Centroid Decomposition and explain how it enables O(n log n) distance queries.
Use the rerooting technique to compute tree DP for all possible roots in O(n).
Identify when each technique is most appropriate for a given tree problem.
Why This Matters
01
Binary Lifting solves Lowest Common Ancestor (LCA) queries in O(log n) per query with O(n log n) preprocessing — essential for tree path queries in competitive programming.
02
The Euler Tour technique flattens a tree into an array, converting subtree queries into range queries that can be answered with segment trees or sparse tables.
03
Centroid Decomposition splits a tree into O(log n) layers, enabling efficient distance queries and path counting — a powerful divide-and-conquer framework for trees.
04
The rerooting technique computes DP results for all possible roots in O(n) total time, avoiding the naive O(n^2) approach of running DP from each node.
Key Terms
6 terms you'll encounter in this lesson
Binary Lifting
A preprocessing technique that stores the 2^k-th ancestor of each node for k = 0, 1, ..., log n. Enables jumping up the tree by any distance in O(log n) by decomposing the distance into powers of 2.
Lowest Common Ancestor (LCA)
The deepest node that is an ancestor of both nodes u and v. LCA queries are fundamental to tree path problems: the path from u to v passes through LCA(u, v).
Euler Tour
A traversal of a tree that records each node when entering (tin) and leaving (tout) it. The subtree of node u corresponds to the contiguous range [tin[u], tout[u]] in the Euler tour array.
Centroid
A node whose removal splits the tree into components each of size at most n/2. Every tree has at least one centroid. Finding it takes O(n) via subtree size computation.
Centroid Decomposition
A recursive decomposition of a tree by repeatedly finding and removing centroids. The resulting centroid tree has depth O(log n), enabling efficient divide-and-conquer on paths.
Rerooting
A technique for computing tree DP results for all nodes as roots. First compute DP from an arbitrary root, then propagate results by 'rerooting' to each child in O(1), achieving O(n) total time.
Heads Up
Common misconceptions to watch out for
"Binary Lifting stores all ancestors of each node"
Binary Lifting only stores the 2^k-th ancestor for each k (at most log n entries per node). This is enough to reach any ancestor by combining jumps, like binary representation of distances.
"Euler Tour creates a sequence of length n"
The Euler Tour visits each node twice (enter and leave), creating a sequence of length 2n. The enter times (tin) and leave times (tout) together define subtree ranges.
"Centroid Decomposition modifies the original tree"
Centroid Decomposition builds a separate centroid tree — the original tree structure is preserved. The centroid tree has different parent-child relationships and O(log n) depth.