Understanding Euler Tour Technique: Theory and Implementation

Introduction and Core Concepts

The euler tour technique is one of the most elegant and powerful methods for transforming tree problems into array problems. At its core, this technique linearizes a tree by recording the order in which nodes are visited during a depth-first traversal, creating a flat array representation that preserves hierarchical relationships. This transformation allows complex tree queries — such as subtree aggregations, ancestor checks, and path computations — to be answered efficiently using classic array data structures like segment trees, Fenwick trees, and sparse tables.

Despite its name, the euler tour technique should not be confused with finding an Eulerian path or circuit in a graph, which visits every edge exactly once. Instead, the technique borrows the idea of a tour — a systematic walk through the structure — and applies it to trees. As we perform a depth-first search (DFS), we note the time we first enter a node and the time we exit it. The interval between these two timestamps encapsulates the entire subtree of that node. This interval property is the fundamental insight that makes the technique so versatile.

Why does the euler tour technique matter for modern software engineering? Trees are ubiquitous in computing: file systems, DOM hierarchies, organizational charts, database indexes, and network routing topologies are all tree-structured. Naively answering queries on trees often requires traversing large portions of the structure, leading to O(n) time per query. By flattening the tree once in O(n) time, the euler tour technique enables O(log n) or even O(1) query times thereafter. For systems handling millions of queries — such as web servers resolving hierarchical permissions or databases executing subtree aggregations — this optimization is transformative.

The Flattening Principle

The central idea is to map each node to a contiguous segment in an array. When we flatten a tree using DFS, all nodes in the subtree of a given node v appear consecutively in the Euler array. This contiguity means a subtree query becomes a range query on an array, a problem for which highly optimized data structures already exist.

Entry and Exit Times

During the tour, we maintain a global timer that increments with each step. For every node, we store tin[v] (time in) when we first visit v, and tout[v] (time out) when we finish exploring its entire subtree. Node u is an ancestor of node v if and only if tin[u] <= tin[v] and tout[v] <= tout[u]. This O(1) ancestor check is itself a powerful primitive for many algorithms.

Types of Euler Tours

There are two common variants. The first records each node exactly once upon entry, producing an array of size n, ideal for subtree queries. The second records a node every time it is visited, including when backtracking, producing an array of size 2n-1, which is essential for Lowest Common Ancestor (LCA) reduction to Range Minimum Query (RMQ). Understanding which variant to use is critical for correct implementation.

How It Works

The mechanism of the euler tour technique is best understood as a disciplined depth-first traversal with bookkeeping. We start at the root of the tree, initialize a timer to zero, and recursively visit children. Before exploring a node's children, we assign its entry time and append it to the Euler array. After all children have been fully processed, we assign its exit time. The sequence of entry times defines a permutation of the nodes that respects the tree's structure.

Consider the interval property more formally. Let the Euler array be E where E[tin[v]] = v. Then the set of nodes in the subtree of v corresponds precisely to the subarray E[tin[v] ... tout[v]]. This is because DFS explores a subtree completely before backtracking. No node outside the subtree can be interleaved within this interval, and no node inside the subtree can appear outside it. This guarantee converts a two-dimensional hierarchical problem into a one-dimensional range problem.

For LCA, the mechanism is slightly different. We create an extended Euler tour where we append a node to the array each time we visit it, not just on first entry. We also record the depth of each occurrence. The LCA of nodes u and v is the node with minimum depth in the Euler array between the first occurrences of u and v. This works because the nodes encountered on the walk between u and v in the DFS order must include their lowest common ancestor, and that ancestor will be the shallowest node on that walk.

From Tree Query to Range Query

Once flattened, subtree queries become trivial. To compute the sum of values in the subtree of v, we query the sum over the range [tin[v], tout[v]] in the flattened array. To support point updates (changing a node's value), we update a single position tin[v] in the underlying data structure. The tree structure itself never needs to be traversed again after the initial flattening.

Ancestor and Descendant Checks

The timestamp intervals provide a constant-time test for ancestry without any additional data structure. This is widely used in algorithms that need to determine if one node lies on the path to another, such as checking for cycles when adding edges or validating hierarchical permissions in access control systems.

Building Auxiliary Structures

After the tour, we typically build a segment tree or Fenwick tree over the flattened array for aggregations (sum, min, max, xor), or a Sparse Table for RMQ to answer LCA in O(1). The choice depends on whether the operation is invertible, idempotent, and whether updates are required. The tour itself is only the first half; the power comes from pairing it with the right array data structure.

Implementation

Implementing the euler tour technique correctly requires careful handling of recursion, timer management, and adjacency lists. For trees with up to 10^5 nodes, Python's default recursion limit must be increased, or an iterative DFS should be used to avoid stack overflow. The following implementations demonstrate the core patterns.

The first implementation shows the basic flattening that records entry and exit times and builds the Euler array. This version is sufficient for all subtree queries and ancestor checks. Note how the timer is passed by reference (using a list or nonlocal variable) to ensure it increments globally across recursive calls.

import sys
sys.setrecursionlimit(300000)

def euler_tour_basic(n, adj, root=0):
    """
    Performs Euler Tour to flatten tree for subtree queries.
    Returns tin, tout, euler array, and flat values.
    """
    tin = [-1] * n
    tout = [-1] * n
    euler = [0] * n
    timer = 0

    # Use iterative stack to avoid recursion depth issues for large n
    # Stack stores (node, parent, state) where state 0 = entering, 1 = exiting
    stack = [(root, -1, 0)]
    # For recursive clarity, here is the recursive version logic:
    def dfs(u, parent):
        nonlocal timer
        tin[u] = timer
        euler[timer] = u
        timer += 1
        for v in adj[u]:
            if v != parent:
                dfs(v, u)
        tout[u] = timer - 1

    dfs(root, -1)
    return tin, tout, euler

# Example usage:
# n = 5
# adj = [[1,2], [0,3,4], [0], [1], [1]]
# tin, tout, euler = euler_tour_basic(n, adj)
# Subtree of node 1 corresponds to euler[tin[1] : tout[1]+1]

The second implementation pairs the Euler tour with a Fenwick Tree (Binary Indexed Tree) to support dynamic subtree sum queries with point updates. This is the most common practical application: we flatten the tree, map node values to positions tin[v], and then range queries on the Fenwick tree answer subtree sums in O(log n).

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

    def add(self, idx, delta):
        # idx is 0-based for euler position
        i = idx + 1
        while i <= self.n:
            self.bit[i] += delta
            i += i & -i

    def prefix_sum(self, idx):
        # sum of [0, idx]
        i = idx + 1
        res = 0
        while i > 0:
            res += self.bit[i]
            i -= i & -i
        return res

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

def build_subtree_structure(n, adj, values, root=0):
    tin, tout, euler = euler_tour_basic(n, adj, root)
    ft = FenwickTree(n)
    # Initialize Fenwick tree with values placed at tin position
    for node in range(n):
        ft.add(tin[node], values[node])
    
    def subtree_sum(v):
        return ft.range_sum(tin[v], tout[v])
    
    def update_node(v, new_val):
        delta = new_val - values[v]
        values[v] = new_val
        ft.add(tin[v], delta)
    
    return subtree_sum, update_node, tin, tout

# values = [10, 5, 3, 2, 7]
# subtree_sum, update_node, _, _ = build_subtree_structure(n, adj, values)
# print(subtree_sum(1))  # Sum of subtree rooted at 1

The third implementation demonstrates the extended Euler tour for LCA queries. Here we record every visit, track depths, and build a Sparse Table for O(1) RMQ. This reduces LCA to a range minimum query over depths.

import math

def euler_tour_lca(n, adj, root=0):
    euler = []          # nodes in visit order (size 2*n -1)
    depth_arr = []      # depth of each entry in euler
    first = [-1] * n    # first occurrence index of each node
    depth = [0] * n

    def dfs(u, parent, d):
        depth[u] = d
        if first[u] == -1:
            first[u] = len(euler)
        euler.append(u)
        depth_arr.append(d)
        for v in adj[u]:
            if v != parent:
                dfs(v, u, d+1)
                euler.append(u)
                depth_arr.append(d)

    dfs(root, -1, 0)
    
    # Build Sparse Table for RMQ (minimum depth index)
    m = len(euler)
    LOG = math.floor(math.log2(m)) + 1
    st = [[0]*m for _ in range(LOG)]
    # st[0][i] stores index i
    for i in range(m):
        st[0][i] = i
    j = 1
    while (1 << j) <= m:
        i = 0
        while i + (1 << j) - 1 < m:
            left = st[j-1][i]
            right = st[j-1][i + (1 << (j-1))]
            # choose index with smaller depth
            if depth_arr[left] < depth_arr[right]:
                st[j][i] = left
            else:
                st[j][i] = right
            i += 1
        j += 1

    def lca(u, v):
        l = first[u]
        r = first[v]
        if l > r:
            l, r = r, l
        length = r - l + 1
        k = math.floor(math.log2(length))
        left_idx = st[k][l]
        right_idx = st[k][r - (1 << k) + 1]
        if depth_arr[left_idx] < depth_arr[right_idx]:
            return euler[left_idx]
        else:
            return euler[right_idx]

    return lca, first, euler, depth

# lca_func, _, _, _ = euler_tour_lca(n, adj)
# print(lca_func(3, 4))  # LCA of 3 and 4

A fourth, iterative implementation is essential for production Python code where recursion depth and speed matter. This version explicitly manages the stack and avoids recursion entirely, making it safe for deep, skewed trees such as those representing file system paths.

def euler_tour_iterative(n, adj, root=0):
    tin = [-1] * n
    tout = [-1] * n
    euler = [0] * n
    parent = [-1] * n
    order = []
    timer = 0

    stack = [(root, -1, 0)]  # (node, parent, iterator index)
    # We simulate recursion with manual state
    stack2 = [(root, -1)]
    # Use two-phase stack: push node, then process children
    # Simpler iterative DFS for tin/tout:
    iter_stack = [(root, -1, 0)]  # 0 = enter, 1 = exit
    while iter_stack:
        u, p, state = iter_stack.pop()
        if state == 0:
            tin[u] = timer
            euler[timer] = u
            timer += 1
            iter_stack.append((u, p, 1))
            # Push children in reverse to maintain original order
            for v in reversed(adj[u]):
                if v != p:
                    iter_stack.append((v, u, 0))
        else:
            tout[u] = timer - 1

    # Verify ancestor property
    def is_ancestor(anc, desc):
        return tin[anc] <= tin[desc] and tout[desc] <= tout[anc]

    return tin, tout, euler, is_ancestor

Step-by-Step Example

To solidify understanding, let us walk through a concrete example. Consider a tree with 7 nodes labeled 0 to 6, rooted at 0. Edges are: 0-1, 0-2, 1-3, 1-4, 2-5, 2-6. This is a perfect binary tree of height 2. We will perform the basic Euler tour that records each node once.

We initialize timer = 0. Start at root 0: assign tin[0]=0, euler[0]=0, timer becomes 1. Move to child 1: tin[1]=1, euler[1]=1, timer=2. From 1, go to child 3: tin[3]=2, euler[2]=3, timer=3. Node 3 is a leaf, so we backtrack and set tout[3]=2. Return to 1, next child 4: tin[4]=3, euler[3]=4, timer=4, tout[4]=3. Having finished all children of 1, we set tout[1]=3. Back at root 0, we proceed to child 2: tin[2]=4, euler[4]=2, timer=5. Child 5: tin[5]=5, euler[5]=5, timer=6, tout[5]=5. Child 6: tin[6]=6, euler[6]=6, timer=7, tout[6]=6. Finally, tout[2]=6 and tout[0]=6.

The resulting arrays are: tin = [0,1,4,2,3,5,6], tout = [6,3,6,2,3,5,6], and euler = [0,1,3,4,2,5,6]. Observe the interval property: the subtree of node 1 occupies indices 1 to 3 in the euler array, which indeed contains [1,3,4] — exactly its descendants. The subtree of node 2 occupies indices 4 to 6, containing [2,5,6]. The ancestor check works: is 0 ancestor of 5? tin[0]=0 <= tin[5]=5 and tout[5]=5 <= tout[0]=6, so yes. Is 1 ancestor of 5? tin[1]=1 <=5 is true, but tout[5]=5 <= tout[1]=3 is false, so no.

Extended Tour Walkthrough

If we instead build the extended tour for LCA, the Euler array becomes longer: [0,1,3,1,4,1,0,2,5,2,6,2,0] with corresponding depths [0,1,2,1,2,1,0,1,2,1,2,1,0]. The first occurrence indices are first[0]=0, first[1]=1, first[2]=7, first[3]=2, first[4]=4, first[5]=8, first[6]=10. To find LCA(3,4), we look between indices 2 and 4: subarray [3,1,4] with depths [2,1,2]; the minimum depth is 1 at node 1, so LCA is 1. For LCA(3,5), range is 2 to 8: [3,1,4,1,0,2,5] depths [2,1,2,1,0,1,2]; minimum is 0 at node 0, so LCA is 0, which is correct.

Query Execution

Suppose each node has a value: values = [10,5,7,2,3,1,4] for nodes 0..6. We map these to the flattened order using tin: flat = [10,5,2,3,7,1,4] corresponding to euler order [0,1,3,4,2,5,6]. A Fenwick tree built over flat can answer subtree sum for node 1 as sum of flat[1..3] = 5+2+3=10, which matches values[1]+values[3]+values[4]. Updating node 3 from 2 to 9 requires a point update at index tin[3]=2, adding delta 7, after which subtree sum for node 1 automatically becomes 17.

Complexity Analysis

The efficiency of the euler tour technique comes from its one-time preprocessing cost that enables fast queries thereafter. The initial DFS traversal visits each node and edge exactly once, resulting in linear time. Building auxiliary structures adds a log-linear or linear factor depending on the structure, but this is still a one-time cost. Queries then benefit from the array representation.

Time complexity must be analyzed separately for preprocessing and query phases. Preprocessing includes the tour itself and construction of the supporting data structure. Query complexity depends on which structure is used: Fenwick trees and segment trees offer logarithmic updates and queries, while Sparse Tables offer constant-time queries but no efficient updates. Space complexity is dominated by the Euler arrays and the auxiliary structure, all of which are linear or log-linear in the number of nodes.

It is important to distinguish between the two tour variants. The basic tour uses O(n) space for tin, tout, and euler arrays. The extended tour for LCA uses O(n) for the Euler array of size 2n-1 plus O(n log n) for the Sparse Table. If only subtree queries are needed, the lighter basic tour is preferred. If LCA is required, the additional space is justified by O(1) query time.

Note that worst-case and best-case are identical for most operations because the algorithm's behavior does not depend on input distribution, only on tree size. The logarithmic factors arise from the height of the auxiliary tree structures, which is balanced regardless of the original tree's shape. Even if the original tree is a degenerate chain, the flattened array and segment tree remain balanced, guaranteeing O(log n) performance.

Variations and Optimizations

The basic euler tour technique can be extended and optimized in several ways to handle more complex query types. One common variation is to store both entry and exit times in a 2n-sized array where each node appears twice. This allows handling of path queries that involve the entire root-to-node path, not just subtrees. By assigning +value at entry and -value at exit, the prefix sum up to tin[v] gives the sum on the path from root to v.

Another powerful optimization is the use of Heavy-Light Decomposition (HLD) in conjunction with Euler tours. While the standard Euler tour excels at subtree queries, it cannot efficiently handle arbitrary path queries between two nodes (e.g., sum on path u-v). HLD partitions the tree into heavy paths that are each contiguous in an array, complementing the Euler tour's subtree handling. Some implementations use a single DFS order that simultaneously supports both, but understanding the trade-offs is key.

For offline queries, Mo's algorithm on trees is a variation that uses the Euler tour to reorder queries for minimal pointer movement, achieving O((n+q) * sqrt(n)) total time. This is useful when queries are not decomposable into standard range operations or when updates are not required. Additionally, the Euler Tour Tree (ETT) is a dynamic variant that maintains a forest of trees under link-cut operations using balanced BSTs to represent the Euler tour, enabling O(log n) connectivity queries in dynamic forests.

Iterative vs Recursive DFS

For production systems, iterative DFS is strongly preferred. Python recursion is slow and limited to ~1000 frames by default. An iterative approach using an explicit stack not only avoids recursion limits but also allows finer control over traversal order and easier integration with coroutine-based processing for very large trees that do not fit in memory.

Value Compression and Flattening

When node values are large or queries involve frequencies, we can combine Euler tour with coordinate compression or offline sorting. For example, to answer "how many nodes in subtree v have value <= k", we can flatten the tree and then use a merge-sort tree or offline BIT with sorting by value. This transforms a 2D query (subtree + value constraint) into a 2D offline range query.

Handling Forests

If the graph is a forest (multiple trees), we can run the Euler tour from each unvisited node, assigning contiguous intervals per component. Adding a super-root that connects to all component roots is another clean solution, ensuring a single Euler array covers the entire forest with minimal code changes.

Real-World Applications

The euler tour technique is not merely an academic exercise; it powers critical infrastructure in web servers, databases, and networks. In hierarchical databases, such as those storing organizational structures or category trees in e-commerce, subtree aggregation is a frequent operation. For example, an e-commerce platform might need to compute the total inventory count for a category and all its subcategories. By flattening the category tree, this becomes a range sum query that can be answered in milliseconds even for millions of products.

Web servers and frontend frameworks use similar concepts to manage the Document Object Model (DOM). When a CSS rule or event listener is applied to a subtree, the engine must efficiently determine which nodes are affected. The tin/tout intervals allow O(1) checks for whether a node lies within a given subtree, accelerating style recalculation and event propagation. Content Management Systems (CMS) that manage nested pages or comments also rely on Euler tours to render threaded discussions and compute nested comment counts without recursive database queries.

In networking, routing tables and multicast trees are often represented as trees. Network monitoring tools need to query aggregate traffic statistics for a subtree of the network topology. The Euler tour allows these aggregates to be maintained with Fenwick trees that support both fast queries and real-time updates as traffic flows change. Similarly, in file systems, operations like computing directory sizes (e.g., `du` command) are essentially subtree sum queries that benefit from flattening.

Beyond these, the technique appears in bioinformatics for phylogenetic tree queries, in game development for scene graph management, and in compilers for abstract syntax tree analysis. Any domain where hierarchical data must be queried frequently and updated occasionally is a candidate for Euler tour optimization.

Comparison with Alternatives

While the euler tour technique is powerful, it is not the only method for handling tree queries. Choosing the right tool depends on the specific query type, update frequency, and implementation complexity. Heavy-Light Decomposition (HLD) is the primary alternative for path queries, binary lifting is optimized for ancestor jumps and LCA, and direct DFS without flattening is simplest for one-off queries.

The key distinction is that Euler tour excels at subtree queries and O(1) ancestor checks, but struggles with arbitrary path queries (u to v) without additional structures. HLD, on the other hand, can handle both path and subtree queries efficiently by decomposing the tree into chains, but with higher constant factors and more complex implementation. Binary lifting is unbeatable for k-th ancestor and LCA with O(log n) queries and simpler code, but cannot handle subtree aggregations.

For static trees with no updates, a direct DFS per query might be acceptable if the number of queries is small. However, as query volume grows, the preprocessing investment of Euler tour pays off dramatically. The table below provides a feature-by-feature comparison to guide selection.

In practice, many advanced solutions combine techniques: using Euler tour for subtree parts and HLD or binary lifting for path parts. For interview settings, Euler tour is often the expected answer for subtree problems due to its elegance and efficiency, while HLD is reserved for harder path query variants.

Common Mistakes and Best Practices

Even experienced developers make subtle errors when implementing the euler tour technique. The most frequent mistake is confusing the two tour variants — using the n-sized array when the 2n-1 array is needed for LCA, or vice versa. This leads to incorrect interval calculations and wrong answers that are hard to debug because the code appears to work on small examples. Always clarify whether the problem requires subtree queries (use n-sized tour) or path/LCA queries (use extended tour).

Another common pitfall is mishandling 0-based versus 1-based indexing, especially when interfacing with Fenwick trees which are traditionally 1-based. Off-by-one errors in tout definitions are rampant: some implementations define tout as the last index inclusive, others as exclusive (timer after subtree). Both are valid, but mixing them causes range queries to miss the last node or include an extra node. Document and consistently use one convention, preferably inclusive tout = timer-1 as shown in the code examples.

Recursion depth and Python's recursion limit catch many developers off guard. A tree that is a chain of 10^5 nodes will cause a RecursionError with default settings. Best practice is to either set a high recursion limit and use sys.setrecursionlimit, or better, implement an iterative DFS. Additionally, forgetting to mark the parent when traversing an undirected adjacency list leads to infinite recursion or incorrect tours that revisit the parent as a child.

Best Practices Checklist

• Always increase recursion limit or use iterative DFS for n > 10^4 in Python.
• Clearly define whether tout is inclusive or exclusive and stick to it throughout.
• Use adjacency lists and pass parent to avoid revisiting.
• Test ancestor property on small trees: verify that subtree intervals are contiguous and non-overlapping for siblings.
• For Fenwick trees, remember to convert 0-based euler indices to 1-based BIT indices inside the structure.
• When building Sparse Tables, precompute logarithms to avoid repeated math.log2 calls in queries.
• Validate with brute force on random small trees: compare Euler tour query results with naive DFS results.

Performance Tips

For maximum performance, use iterative loops and local variable binding in Python. PyPy often handles recursion better than CPython for deep DFS. If the tree is static and queries are offline, consider sorting queries by tin to improve cache locality. For persistent or historical queries, use a persistent segment tree built over the Euler array to answer queries for any version of the tree in O(log n) time.

Interview Questions

Interviewers frequently use the euler tour technique to assess a candidate's ability to transform problems and apply data structures creatively. Mastery of this technique signals strong understanding of both graph theory and range query structures. Below are common interview questions that test different facets of the technique.

Q1: Subtree Sum Queries with Updates

Problem: Given a rooted tree with n nodes where each node has a value, support two operations: update the value of a node, and query the sum of values in the subtree of a node. How would you handle q up to 10^5 operations efficiently?

Expected Answer: Flatten the tree using Euler tour to get tin/tout intervals. Build a Fenwick tree or segment tree over the flattened array where position tin[v] holds the value of node v. Subtree sum for v becomes range sum query [tin[v], tout[v]] in O(log n), and point update is O(log n). Preprocessing is O(n). Discuss why naive DFS per query is O(nq) and too slow, and explain the interval property.

Q2: Check if Node u is Ancestor of Node v

Problem: Preprocess a tree to answer many queries of the form "is u an ancestor of v?" in constant time.

Expected Answer: Perform Euler tour and store entry and exit times. Node u is ancestor of v iff tin[u] <= tin[v] and tout[v] <= tout[u]. This works because DFS intervals are nested. Preprocessing O(n), query O(1), space O(n). Mention that this is used in many LCA and cycle detection algorithms.

Q3: Lowest Common Ancestor (LCA) via Euler Tour

Problem: How can you reduce LCA to a Range Minimum Query using Euler tour?

Expected Answer: Build the extended Euler tour of size 2n-1 where each visit (including backtracking) is recorded, along with depth array and first occurrence array. The LCA of u and v is the node with minimum depth between first[u] and first[v] in the Euler array. Build a Sparse Table for RMQ in O(n log n) to answer LCA in O(1), or use segment tree for O(log n) with less memory. Explain why the shallowest node on the walk between u and v must be their LCA.

Q4: Count Nodes in Subtree with Value Greater Than K

Problem: Given a tree, answer queries: how many nodes in the subtree of v have value > k? Values are static, queries are offline.

Expected Answer: Flatten tree to array via Euler tour, converting subtree query to range query [tin[v], tout[v]]. This becomes a classic offline 2D query: count of elements > k in range. Sort nodes by value descending and queries by k descending, then use BIT to add nodes as threshold lowers and query range counts. Complexity O((n+q) log n). Alternative: merge sort tree for online queries in O(log² n). Shows ability to combine Euler tour with offline techniques.

Q5: When Would You Choose Euler Tour Over Heavy-Light Decomposition?

Problem: Compare Euler tour and HLD. When is each appropriate?

Expected Answer: Euler tour is simpler and faster for subtree queries and ancestor checks, with O(log n) queries and O(n) preprocessing. HLD is needed for arbitrary path queries (u to v) where Euler tour alone is insufficient, at cost of higher implementation complexity and O(log² n) queries. If problem only asks for subtree operations, Euler tour is strictly better. If both path and subtree queries are needed, HLD can handle both, or a hybrid approach can be used. Mention trade-offs in code complexity and constant factors.

Preparing for these questions involves not just memorizing code, but understanding the underlying interval property, being able to implement iterative DFS, and knowing which auxiliary data structure to pair with the tour for each query type. Practice by coding the flattening and then solving at least one problem from each category: subtree aggregate, ancestor check, and LCA.