Advanced Tree Algorithms: HLD, Centroid & Euler Tour

Basic tree algorithms — traversals, DFS, BFS, simple DP — handle most interview problems. But competitive programming and advanced system design demand techniques that turn trees into flat structures you can query with powerful data structures. This post covers six advanced tree techniques, each with a clear mental model, working code, and practical applications.

1. Heavy-Light Decomposition (HLD) — Path Queries on Trees

The problem: answer queries like “what is the maximum edge weight on the path from node u to node v?” or “add 5 to every edge on the path from u to v.” On a flat array, segment trees handle these easily. On a tree, the path can twist through branches.

The idea: decompose the tree into chains of heavy edges. A heavy edge connects a node to its child with the largest subtree. Any path from root to leaf crosses at most O(log n) chains. Map each chain to a contiguous segment of an array, then use a segment tree on that array.

1
/|

2  3  4
/|     |
5  6    7
/
8
Heavy edges (largest subtree child):
1→2, 2→5, 5→8  (chain 1)
1→4, 4→7       (chain 2)
2→6             (chain 3)
1→3             (chain 4)

Implementation

import sys
from collections import defaultdict

class HLD:
    def __init__(self, n, adj, root=0):
        self.n = n
        self.adj = adj
        self.parent = [0] * n
        self.depth = [0] * n
        self.subtree_size = [1] * n
        self.chain_head = [0] * n
        self.pos = [0] * n  # position in segment tree array
        self.timer = 0

        sys.setrecursionlimit(n + 100)
        self._dfs_size(root, -1, 0)
        self.chain_head[root] = root
        self._dfs_hld(root, -1)

    def _dfs_size(self, u, par, d):
        self.parent[u] = par
        self.depth[u] = d
        for v in self.adj[u]:
            if v != par:
                self._dfs_size(v, u, d + 1)
                self.subtree_size[u] += self.subtree_size[v]

    def _dfs_hld(self, u, par):
        self.pos[u] = self.timer
        self.timer += 1

        # Find heavy child (largest subtree)
        heavy = -1
        max_size = 0
        for v in self.adj[u]:
            if v != par and self.subtree_size[v] > max_size:
                max_size = self.subtree_size[v]
                heavy = v

        # Process heavy child first (same chain)
        if heavy != -1:
            self.chain_head[heavy] = self.chain_head[u]
            self._dfs_hld(heavy, u)

        # Process light children (new chains)
        for v in self.adj[u]:
            if v != par and v != heavy:
                self.chain_head[v] = v
                self._dfs_hld(v, u)

    def path_query(self, u, v, seg_tree_query):
        """Query the path u-v using a segment tree query function."""
        result = 0  # or identity element for your operation
        while self.chain_head[u] != self.chain_head[v]:
            # Move the deeper chain head up
            if self.depth[self.chain_head[u]] < self.depth[self.chain_head[v]]:
                u, v = v, u
            result = max(result, seg_tree_query(
                self.pos[self.chain_head[u]], self.pos[u]
            ))
            u = self.parent[self.chain_head[u]]

        # Now u and v are on the same chain
        if self.depth[u] > self.depth[v]:
            u, v = v, u
        result = max(result, seg_tree_query(self.pos[u], self.pos[v]))
        return result

Time per query: O(log^2 n) — O(log n) chains crossed, each queried on a segment tree in O(log n).

When to use: any problem with path queries (sum, max, min, update) on a tree. Classic examples: SPOJ QTREE, heavy path queries.

2. Euler Tour Technique — Subtree Queries as Range Queries

The idea: do a DFS and record the entry time (tin) and exit time (tout) of each node. The subtree of node u corresponds exactly to the range [tin[u], tout[u]] in the Euler tour array. Now subtree queries become range queries on a flat array.

Tree:       1
/ 

2   3
/ 

4   5
DFS order:  1  2  4  4  5  5  2  3  3
Entry time: 1→0, 2→1, 4→2, 5→3, 3→4
Exit time:  4→2, 5→3, 2→4, 3→5, 1→5
Subtree of 2: indices [1, 3] → nodes 2, 4, 5

class EulerTour:
    def __init__(self, n, adj, root=0):
        self.tin = [0] * n
        self.tout = [0] * n
        self.order = []  # nodes in DFS entry order
        self.timer = 0

        self._dfs(root, -1, adj)

    def _dfs(self, u, parent, adj):
        self.tin[u] = self.timer
        self.order.append(u)
        self.timer += 1

        for v in adj[u]:
            if v != parent:
                self._dfs(v, u, adj)

        self.tout[u] = self.timer - 1

    def is_ancestor(self, u, v):
        return self.tin[u] <= self.tin[v] <= self.tout[u]

    def subtree_range(self, u):
        return (self.tin[u], self.tout[u])

With a Fenwick tree or segment tree on the Euler tour array, you get:

• Subtree sum/update: O(log n)
• Ancestor check: O(1)

Example — subtree sum queries:

class FenwickTree:
    def __init__(self, n):
        self.n = n
        self.tree = [0] * (n + 1)

    def update(self, i, delta):
        i += 1
        while i <= self.n:
            self.tree[i] += delta
            i += i & (-i)

    def query(self, i):
        i += 1
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & (-i)
        return s

    def range_query(self, l, r):
        return self.query(r) - (self.query(l - 1) if l > 0 else 0)

# Usage with Euler tour
def subtree_sum(euler, fenwick, node):
    l, r = euler.subtree_range(node)
    return fenwick.range_query(l, r)

3. Centroid Decomposition — Divide and Conquer on Trees

The problem: process all paths in a tree efficiently. Brute force is O(n^2) pairs. Can we do better?

The idea: find the centroid of the tree — the node whose removal splits the tree into components each of size at most n/2. Process all paths through the centroid, remove it, and recursively decompose each component.

This creates a centroid tree of depth O(log n). Every path in the original tree passes through exactly one centroid in this tree.

class CentroidDecomposition:
    def __init__(self, n, adj):
        self.n = n
        self.adj = adj
        self.subtree_size = [0] * n
        self.removed = [False] * n
        self.centroid_parent = [-1] * n

        self._build(0, -1)

    def _get_subtree_size(self, u, parent):
        self.subtree_size[u] = 1
        for v in self.adj[u]:
            if v != parent and not self.removed[v]:
                self._get_subtree_size(v, u)
                self.subtree_size[u] += self.subtree_size[v]

    def _get_centroid(self, u, parent, tree_size):
        for v in self.adj[u]:
            if v != parent and not self.removed[v]:
                if self.subtree_size[v] > tree_size // 2:
                    return self._get_centroid(v, u, tree_size)
        return u

    def _build(self, u, par):
        self._get_subtree_size(u, -1)
        centroid = self._get_centroid(u, -1, self.subtree_size[u])
        self.centroid_parent[centroid] = par
        self.removed[centroid] = True

        for v in self.adj[centroid]:
            if not self.removed[v]:
                self._build(v, centroid)

Analogy: imagine you have a country and want to build a postal system. Place the main post office at the centroid (most central location), then recursively place sub-offices in each region. Any letter travels through at most O(log n) offices.

Applications: counting paths of a given length, finding the closest marked node, xor-distance queries.

4. LCA with Binary Lifting — Detailed Implementation

Binary lifting precomputes up[k][v] = the 2^k-th ancestor of node v. Any ancestor query decomposes into at most O(log n) jumps.

import math
from collections import deque

class BinaryLiftingLCA:
    def __init__(self, n, adj, root=0):
        self.LOG = max(1, int(math.log2(n)) + 1)
        self.n = n
        self.depth = [0] * n
        self.up = [[-1] * n for _ in range(self.LOG)]

        # BFS to set depths and direct parents
        visited = [False] * n
        queue = deque([root])
        visited[root] = True
        self.up[0][root] = root

        while queue:
            u = queue.popleft()
            for v in adj[u]:
                if not visited[v]:
                    visited[v] = True
                    self.depth[v] = self.depth[u] + 1
                    self.up[0][v] = u
                    queue.append(v)

        # Fill binary lifting table
        for k in range(1, self.LOG):
            for v in range(n):
                if self.up[k-1][v] != -1:
                    self.up[k][v] = self.up[k-1][self.up[k-1][v]]

    def kth_ancestor(self, v, k):
        for i in range(self.LOG):
            if k & (1 << i):
                v = self.up[i][v]
                if v == -1:
                    return -1
        return v

    def lca(self, u, v):
        if self.depth[u] < self.depth[v]:
            u, v = v, u

        # Bring u to same depth as v
        diff = self.depth[u] - self.depth[v]
        u = self.kth_ancestor(u, diff)

        if u == v:
            return u

        # Binary lift both until just below LCA
        for k in range(self.LOG - 1, -1, -1):
            if self.up[k][u] != self.up[k][v]:
                u = self.up[k][u]
                v = self.up[k][v]

        return self.up[0][u]

    def distance(self, u, v):
        return self.depth[u] + self.depth[v] - 2 * self.depth[self.lca(u, v)]

Time: O(n log n) preprocessing, O(log n) per query.

Beyond LCA: binary lifting can answer “k-th ancestor” queries, which are useful for path decomposition problems.

5. Tree DP with Rerooting

We covered rerooting briefly in Advanced DP Patterns. Here is a more general template:

Phase 1 (root at node 0): compute dp_down[v] — the answer considering only the subtree of v.

Phase 2 (reroot): compute dp_up[v] — the contribution from “everything above v.” The full answer for v is combine(dp_down[v], dp_up[v]).

def rerooting_template(n, adj, base_value, combine, undo):
    """
    base_value: identity value for combine
    combine(accumulated, child_contribution): merge child into answer
    undo(accumulated, child_contribution): remove child from answer
    """
    dp_down = [base_value] * n
    dp_full = [base_value] * n

    # Phase 1: compute dp_down with DFS
    order = []
    parent = [-1] * n
    visited = [False] * n
    stack = [0]
    visited[0] = True
    while stack:
        u = stack.pop()
        order.append(u)
        for v in adj[u]:
            if not visited[v]:
                visited[v] = True
                parent[v] = u
                stack.append(v)

    # Process in reverse DFS order (children before parents)
    for u in reversed(order):
        for v in adj[u]:
            if v != parent[u]:
                dp_down[u] = combine(dp_down[u], dp_down[v])

    # Phase 2: reroot
    dp_full[0] = dp_down[0]
    for u in order:
        for v in adj[u]:
            if v != parent[u]:
                # answer for v = dp_down[v] + (dp_full[u] - dp_down[v])
                parent_contribution = undo(dp_full[u], dp_down[v])
                dp_full[v] = combine(dp_down[v], parent_contribution)

    return dp_full

Applications: maximum distance from each node, tree diameter from each node’s perspective, counting paths through each node.

6. Virtual Tree (Auxiliary Tree)

When a query involves only k key nodes out of n total, building a virtual tree containing just those k nodes (plus their LCAs) reduces the problem size from O(n) to O(k).

Steps:

1. Sort key nodes by DFS entry time.
2. For each consecutive pair, compute their LCA.
3. Build a tree from these nodes using a stack.

def build_virtual_tree(key_nodes, lca_func, tin):
    """
    key_nodes: list of key node IDs
    lca_func: function that returns LCA of two nodes
    tin: entry time array from Euler tour
    """
    # Sort by entry time
    nodes = sorted(key_nodes, key=lambda u: tin[u])

    # Add LCAs of consecutive pairs
    extended = list(nodes)
    for i in range(len(nodes) - 1):
        extended.append(lca_func(nodes[i], nodes[i+1]))

    # Remove duplicates and sort
    extended = sorted(set(extended), key=lambda u: tin[u])

    # Build tree using stack
    stack = [extended[0]]
    virtual_adj = {u: [] for u in extended}

    for i in range(1, len(extended)):
        u = extended[i]
        l = lca_func(u, stack[-1])

        if l != stack[-1]:
            while len(stack) > 1 and tin[stack[-2]] >= tin[l]:
                virtual_adj[stack[-2]].append(stack[-1])
                stack.pop()
            if stack[-1] != l:
                virtual_adj[l] = [stack.pop()]
                stack.append(l)

        stack.append(u)

    while len(stack) > 1:
        virtual_adj[stack[-2]].append(stack[-1])
        stack.pop()

    return virtual_adj, stack[0]  # adjacency list and root

When to use: queries that say “given these k special nodes, compute something about the tree restricted to them.” Common in competitive programming problems where k is much smaller than n.

Technique Selection Guide

Recap

Advanced tree algorithms are about transformation — turning tree problems into problems on flat arrays or smaller trees:

• HLD linearises paths into O(log n) chain segments
• Euler tour linearises subtrees into contiguous array ranges
• Centroid decomposition recursively divides the tree at its balance point
• Binary lifting enables logarithmic jumps up the tree
• Rerooting avoids recomputation when the root changes
• Virtual trees compress the relevant structure when only a few nodes matter

Master these six techniques and you can tackle virtually any tree problem in competitive programming or advanced interviews.

Next steps

For DP techniques that work on trees, see Advanced DP Patterns. For a broader competitive programming toolkit, see CP Patterns.

Questions or feedback? Email codeloomdevv@gmail.com.