Loading…

mediumTreesSometimes asked

Euler Tour of a Tree (Subtree Flattening)

Q: How do you solve Euler Tour of a Tree (Subtree Flattening) using the Baseline — DFS the Subtree Per Query approach?

When to use it: Say this first: it directly answers a subtree query and exposes why repeated queries need flattening. The direct method needs no preprocessing beyond the adjacency list. **Update is trivial.** Storing values per node, `update(node, val)` is one write — O(1). **Query walks the subtree.** `subtreeSum(node)` runs a DFS rooted at `node`, summing every value it reaches. Correct, because a subtree is exactly the set of nodes reachable downward from `node`. **Why it does not scale.** A subtree can be the whole tree (querying the root), so a single query is O(n). With up to 2×10⁵ queries that is up to 4×10¹⁰ node visits. **What flattening buys.** The subtree is reconstructed from scratch every query even though the tree shape never changes. If we instead assign each subtree a fixed contiguous range once, a query becomes a range-sum over that block — answerable in O(log n) with a Fenwick tree, and updates stay cheap. Time complexity: O(n) per query, O(1) update. Space complexity: O(n).

Trees & BST · 26 of 41 · 11 min

You are given a rooted tree with n nodes, each holding a value. Support:

1
**update(node, val)** — change the value stored at node.
2
**subtreeSum(node)** — return the sum of values over node and all of its descendants.

Preprocess with an Euler tour so each subtree maps to a contiguous array range, then back the array with a Fenwick tree to make both operations **O(log n)**.

In plain English

We want subtree aggregates to be fast under updates. A subtree is awkward on a tree but trivial on an array — if only it were contiguous. The Euler tour makes it so: a single DFS that stamps an entry index when it first reaches a node and an exit index when it finishes the node's subtree lays every subtree out as one unbroken block [tin, tout]. From there, subtree operations are range operations and any 1-D range structure applies.

Examples

Example 1

Input: tree rooted at 0: 0-1,0-2,1-3,1-4; values=[5,3,2,1,4]; subtreeSum(1)
Output: 8
Note: Subtree of 1 is {1,3,4} = 3 + 1 + 4 = 8.

Example 2

Input: same tree; subtreeSum(0)
Output: 15
Note: The whole tree: 5 + 3 + 2 + 1 + 4 = 15. tin[0]=0, tout[0]=4 covers the entire array.

Example 3

Input: same tree; update(3, 10) then subtreeSum(1)
Output: 17
Note: After node 3 becomes 10, subtree of 1 is 3 + 10 + 4 = 17. The update touches one array index (tin[3]).

Constraints

1 ≤ n ≤ 2 × 10⁵
Up to 2 × 10⁵ interleaved update and subtreeSum calls
The tree is rooted and its shape is static
Sums fit in 64-bit (use long in Java)

Clarifying questions4First question: Are queries about subtrees or arbitrary paths?Explore questions

Q1.Are queries about subtrees or arbitrary paths?
Subtrees here. The Euler tour makes a subtree contiguous. Arbitrary path queries need heavy-light decomposition or LCA splitting instead.
Q2.Does the tree change shape between queries?
No. tin/tout indices assume a fixed shape; if edges changed we would have to recompute the tour or use a dynamic structure.
Q3.Are values on nodes or edges?
Nodes here. Edge values can be pushed onto the deeper endpoint of each edge, with care about the root having no incoming edge.
Q4.How deep can the tree be?
Up to n in a chain, so the DFS that builds the tour should be iterative (explicit stack) to avoid blowing the recursion stack at 2×10⁵.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

An Euler tour flattens a rooted tree into an array by recording an entry time tin[node] and an exit time tout[node] during one DFS. The key property: a node's entire subtree occupies the contiguous index range [tin[node], tout[node]] in that array. That turns 'update/query a whole subtree' into 'update/query a contiguous range', so a Fenwick or segment tree over the flattened array answers subtree-sum and subtree-update in O(log n). The tour itself is O(n).

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you can flatten a tree so subtree operations become range operations — assigning tin before recursing and tout after, and recognizing that [tin, tout] is exactly one subtree.

Where candidates slip

Setting tout before recursing (so it does not cover descendants), using a node→array map that is not contiguous, or recursing deeply enough to overflow the stack on a chain.

How to stand out

State the contiguous-range invariant precisely, show the O(1) ancestor test, and explain how layering a Fenwick tree on the flattened array gives O(log n) subtree-sum with point updates. Mention the iterative DFS for deep trees.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Baseline — DFS the Subtree Per Query	`O(n) per query, O(1) update`	`O(n)`	Say this first: it directly answers a subtree query and exposes why repeated queries need flattening.	Read
2	Euler Tour + Fenwick Tree (Optimal)Optimal	`O(n) tour + O(log n) per op`	`O(n)`	The answer they want for many subtree queries/updates. 'Flatten with tin/tout so each subtree is a range, then a BIT handles ranges.'	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.Explore the full tree

tin / tout from one DFS

How to read it:DFS order 0,1,3,4,2 gives tin=[0,1,3,4,2]. Subtree of 1 is array range [1,3] = nodes {1,3,4}.

Rendering diagram…

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Baseline — DFS the Subtree Per Query

TimeO(n) per query, O(1) updateSpaceO(n)

Say this first: it directly answers a subtree query and exposes why repeated queries need flattening.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

To answer subtreeSum(node), run a DFS from node and add up every value reached — that is the subtree.

2Hint 2Explore hint

update(node, val) is a single assignment to the stored value — O(1).

3Hint 3Explore hint

But each subtree query can walk the whole tree (the root's subtree is everything) — O(n) per query, too slow for many queries.

A · Core idea

The direct method needs no preprocessing beyond the adjacency list.

Update is trivial. Storing values per node, update(node, val) is one write — O(1).

Query walks the subtree. subtreeSum(node) runs a DFS rooted at node, summing every value it reaches. Correct, because a subtree is exactly the set of nodes reachable downward from node.

Why it does not scale. A subtree can be the whole tree (querying the root), so a single query is O(n). With up to 2×10⁵ queries that is up to 4×10¹⁰ node visits.

What flattening buys. The subtree is reconstructed from scratch every query even though the tree shape never changes. If we instead assign each subtree a fixed contiguous range once, a query becomes a range-sum over that block — answerable in O(log n) with a Fenwick tree, and updates stay cheap.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

tree rooted at 0: 0-1,0-2,1-3,1-4; values=[5,3,2,1,4]; subtreeSum(1)

visit 1

sum += 3

Statesum = 3

Final result8

C · Code with teaching comments

Reference implementation previewimport java.util.*; class NaiveSubtree { private final List<List<Integer>> adj; private final long[] val;Explore the full code

solution.javaJava

Baseline — DFS the Subtree Per Query — reference

3 teaching notes

1
import java.util.*;
2
 
3
class NaiveSubtree {
4
    private final List<List<Integer>> adj;
5
    private final long[] val;
6
 
7
    NaiveSubtree(int n, int[][] edges, long[] values) {
8
        adj = new ArrayList<>();
9
        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
10
        for (int[] e : edges) { adj.get(e[0]).add(e[1]); adj.get(e[1]).add(e[0]); }
11
        val = values.clone();
12
    }
13
 
14
    void update(int node, long v) {
15
        // Point update is a single write.
16
        val[node] = v;                  // O(1)
17
    }
18
 
19
    long subtreeSum(int node, int parent) {   // O(n)
20
        // Start the subtree sum with the node's own value.
21
        long sum = val[node];
22
        for (int child : adj.get(node)) {
23
            // Recurse into real children; this whole walk is O(n) per query.
24
            if (child != parent) sum += subtreeSum(child, node);
25
        }
26
        return sum;
27
    }
28
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.28 lines

D · Why it works and complexityO(n) per query, O(1) update timeO(n) spaceOpen the invariant and proofExplore the proof

The wasted work is re-discovering the same subtree boundaries on every query. The Euler tour computes those boundaries once as [tin, tout]; everything after is a range operation on a static layout.

ComplexityO(n) per query, O(1) update time, O(n) space — A subtree DFS visits up to n nodes, so a query is O(n). Updates are O(1). With q queries the total is O(q·n), which is too slow when both are large.

E · Edge cases and pitfalls3Re-walking the subtree every query — O(n) each when the shape never changes.Explore edge cases

Pitfalls

Re-walking the subtree every query — O(n) each when the shape never changes.
Forgetting the parent guard and recursing back up the tree.
Recursive subtree sum on a chain — stack overflow for large n.

03.2

Approach 2 of 2 · Optimal

Euler Tour + Fenwick Tree (Optimal)

TimeO(n) tour + O(log n) per opSpaceO(n)

The answer they want for many subtree queries/updates. 'Flatten with tin/tout so each subtree is a range, then a BIT handles ranges.'

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Run one DFS. When you first reach a node, give it tin[node] = the next free array index; when you finish its whole subtree, set tout[node] = the last index used.

2Hint 2Explore hint

Now the subtree of any node is exactly the contiguous range [tin[node], tout[node]] in the flattened array — because DFS visits a node's descendants consecutively before moving on.

3Hint 3Explore hint

Place value[node] at index tin[node]. Then subtreeSum(node) = rangeSum(tin[node], tout[node]) and update(node, v) is a point update at tin[node] — both O(log n) with a Fenwick tree.

A · Core idea

The Euler tour rewrites the tree as an array so that the messy notion of 'subtree' becomes the clean notion of 'contiguous range'.

Building the tour. Run a single DFS from the root with a global counter timer. The instant you enter a node, record tin[node] = timer and increment timer; this is the node's slot in the flattened array, and we place its value there. After all of the node's children have been fully explored, record tout[node] as the last index that was used. Because DFS fully finishes one child's subtree before starting the next, all descendants of a node receive indices that fall between the node's own tin and the moment it finishes — with no outside node squeezed in.

The contiguous-range invariant. This is the whole point: the subtree of node is exactly the index range [tin[node], tout[node]]. Its length tout[node] − tin[node] + 1 equals the subtree size. Equivalently, u is an ancestor of v iff tin[u] ≤ tin[v] ≤ tout[u] — an O(1) ancestor test, no walking.

Why assign tin before recursing and tout after. tin must be stamped on entry so a node sits before all its descendants in the array. tout must be stamped on exit so it captures the last descendant's index. Swapping the order (stamping tout before recursing) would make the range exclude the subtree — the classic bug.

Layering a range structure. With values living at tin positions, every subtree question is a range question:

subtreeSum(node) = rangeSum(tin[node], tout[node]),
update(node, v) is a point update at index tin[node].

A Fenwick tree over the flattened array answers both in O(log n). A segment tree works equally well and adds range updates via lazy propagation (e.g. 'add x to every node in a subtree').

Why this is the standard reduction. Once a subtree is a contiguous range, you inherit every 1-D technique: prefix sums for static data, Fenwick/segment trees for updates, even Mo's algorithm for offline queries. The tour is the adapter that lets array tools operate on trees.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

tree rooted at 0: 0-1,0-2,1-3,1-4; values=[5,3,2,1,4]. Build tour, subtreeSum(1), update(3,10), subtreeSum(1).

Array state

after tour

index→node: 0→0, 1→1, 2→3, 3→4, 4→2

[0]

[1]

[2]

[3]

[4]

Current pointerResolved stateNot processed

Final result8 then 17

C · Code with teaching comments

solution.javaJava

Euler Tour + Fenwick Tree (Optimal) — optimal

5 teaching notes

1
import java.util.*;
2
 
3
class EulerTourSubtree {
4
    private final int n;
5
    private final int[] tin, tout;
6
    private final long[] bit;   // Fenwick tree over the flattened array (1-based)
7
 
8
    EulerTourSubtree(int n, int root, int[][] edges, long[] values) {
9
        this.n = n;
10
        tin = new int[n];
11
        tout = new int[n];
12
        bit = new long[n + 1];
13
        List<List<Integer>> adj = new ArrayList<>();
14
        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
15
        for (int[] e : edges) { adj.get(e[0]).add(e[1]); adj.get(e[1]).add(e[0]); }
16
 
17
        // Iterative DFS to compute tin/tout (chain-safe).
18
        int[] parent = new int[n];
19
        int timer = 0;
20
        Deque<int[]> stack = new ArrayDeque<>();   // {node, childIndex}
21
        parent[root] = root;
22
        stack.push(new int[]{root, 0});
23
        // Entry index assigned the moment the node is first reached.
24
        tin[root] = timer++;
25
        while (!stack.isEmpty()) {
26
            int[] top = stack.peek();
27
            int node = top[0];
28
            if (top[1] < adj.get(node).size()) {
29
                int next = adj.get(node).get(top[1]++);
30
                if (next != parent[node]) {
31
                    parent[next] = node;
32
                    // Each child gets the next free slot before its own children —
33
                    // keeps the subtree contiguous.
34
                    tin[next] = timer++;
35
                    stack.push(new int[]{next, 0});
36
                }
37
            } else {
38
                // Exit index = last slot used by any descendant; set after children
39
                // finish.
40
                tout[node] = timer - 1;   // last index in this subtree
41
                stack.pop();
42
            }
43
        }
44
        // Load values at their tin positions.
45
        // Place each node's value at its tin position in the Fenwick tree (1-based).
46
        for (int v = 0; v < n; v++) bitUpdate(tin[v] + 1, values[v]);
47
    }
48
 
49
    private void bitUpdate(int i, long delta) {
50
        for (; i <= n; i += i & -i) bit[i] += delta;
51
    }
52
 
53
    private long bitPrefix(int i) {
54
        long s = 0;
55
        for (; i > 0; i -= i & -i) s += bit[i];
56
        return s;
57
    }
58
 
59
    void update(int node, long newVal) {
60
        long old = subtreeSumRange(tin[node], tin[node]);
61
        bitUpdate(tin[node] + 1, newVal - old);   // add the delta
62
    }
63
 
64
    private long subtreeSumRange(int l, int r) {  // r inclusive, 0-based tin range
65
        return bitPrefix(r + 1) - bitPrefix(l);
66
    }
67
 
68
    long subtreeSum(int node) {
69
        // Subtree sum is just the range sum over [tin, tout].
70
        return subtreeSumRange(tin[node], tout[node]);
71
    }
72
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.72 lines

D · Why it works and complexityO(n) tour + O(log n) per op timeO(n) spaceOpen the invariant and proofExplore the proof

The Euler tour is a coordinate change: it relabels nodes by DFS entry time so that 'descendant of u' becomes 'index in [tin[u], tout[u]]'. That single relabeling is what lets you reuse Fenwick and segment trees — structures built for arrays — on subtree problems without modification.

ComplexityO(n) tour + O(log n) per op time, O(n) space — The DFS visits each node once → O(n) to compute tin/tout and lay out the array. Each query is one range-sum (two prefix queries) and each update is one point update on the Fenwick tree → O(log n) each.

E · Edge cases and pitfalls7subtreeSum(leaf) — tin == tout, so the range is a single index — returns the leaf's own value.Explore edge cases

Edge cases handled

subtreeSum(leaf)tin == tout, so the range is a single index — returns the leaf's own value.
subtreeSum(root)[tin=0, tout=n-1] covers the whole array → total of all values.
ancestor testu is an ancestor of v iff tin[u] ≤ tin[v] ≤ tout[u] — O(1), no traversal.

Pitfalls

Setting tout before recursing into children — the range then excludes the subtree.
Mapping nodes to non-contiguous array slots — breaks the single-range query.
Recursive DFS on a deep chain — stack overflow; use an explicit stack.
Off-by-one between 0-based tin/tout and the 1-based Fenwick indexing.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewimport java.util.*; class EulerTourSubtree { private final int n; private final int[] tin, tout;Explore the playground

Try it — Java· run a complete program; method snippets need a driver

import java.util.*;

class EulerTourSubtree {
    private final int n;
    private final int[] tin, tout;
    private final long[] bit;   // Fenwick tree over the flattened array (1-based)

EulerTourSubtree(int n, int root, int[][] edges, long[] values) {
        this.n = n;
        tin = new int[n];
        tout = new int[n];
        bit = new long[n + 1];
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
        for (int[] e : edges) { adj.get(e[0]).add(e[1]); adj.get(e[1]).add(e[0]); }

// Iterative DFS to compute tin/tout (chain-safe).
        int[] parent = new int[n];
        int timer = 0;
        Deque<int[]> stack = new ArrayDeque<>();   // {node, childIndex}
        parent[root] = root;
        stack.push(new int[]{root, 0});
        tin[root] = timer++;
        while (!stack.isEmpty()) {
            int[] top = stack.peek();
            int node = top[0];
            if (top[1] < adj.get(node).size()) {
                int next = adj.get(node).get(top[1]++);
                if (next != parent[node]) {
                    parent[next] = node;
                    tin[next] = timer++;
                    stack.push(new int[]{next, 0});
                }
            } else {
                tout[node] = timer - 1;   // last index in this subtree
                stack.pop();
            }
        }
        // Load values at their tin positions.
        for (int v = 0; v < n; v++) bitUpdate(tin[v] + 1, values[v]);
    }

private void bitUpdate(int i, long delta) {
        for (; i <= n; i += i & -i) bit[i] += delta;
    }

private long bitPrefix(int i) {
        long s = 0;
        for (; i > 0; i -= i & -i) s += bit[i];
        return s;
    }

void update(int node, long newVal) {
        long old = subtreeSumRange(tin[node], tin[node]);
        bitUpdate(tin[node] + 1, newVal - old);   // add the delta
    }

private long subtreeSumRange(int l, int r) {  // r inclusive, 0-based tin range
        return bitPrefix(r + 1) - bitPrefix(l);
    }

long subtreeSum(int node) {
        return subtreeSumRange(tin[node], tout[node]);
    }
}

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

tout set too early

tout must be the LAST index used by any descendant, so it can only be known after all children are explored. Setting it before recursing makes [tin, tout] cover just the node, dropping its subtree.

Explore the code comparison

Don't write this

def dfs(node, parent):
    self.tin[node] = self.timer; self.timer += 1
    self.tout[node] = self.timer - 1     # wrong: set before children
    for c in adj[node]:
        if c != parent: dfs(c, node)

Write this instead

def dfs(node, parent):
    self.tin[node] = self.timer; self.timer += 1
    for c in adj[node]:
        if c != parent: dfs(c, node)
    self.tout[node] = self.timer - 1     # set after all children return

Non-contiguous node mapping

The whole benefit is that a subtree is one contiguous range. Assigning array slots in any order other than DFS entry time scatters a subtree across the array, so a single rangeSum no longer captures it.

Explore the code comparison

Don't write this

int slot = someHash(node);     // arbitrary positions
bitUpdate(slot, values[node]);

Write this instead

bitUpdate(tin[node] + 1, values[node]);  // position = DFS entry time

Recursive DFS overflow

A chain of 2×10⁵ nodes recurses 2×10⁵ deep, overflowing the default stack in both Java and Python. Build the tour with an explicit stack.

Explore the code comparison

Don't write this

def dfs(node, parent):
    ...
    for c in adj[node]:
        if c != parent: dfs(c, node)   # depth up to n

Write this instead

stack = [(root, iter(adj[root]))]
while stack:
    ...                                # iterative tour, constant call depth

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

DFS timestamps tin/tout so each subtree is a contiguous [tin, tout] range

Code pattern to memorize

timer = 0
def dfs(node, parent):
    tin[node] = timer; timer += 1
    order[tin[node]] = node
    for child != parent: dfs(child, node)
    tout[node] = timer - 1   # last index of this subtree

Rules to remember

1tin[node] is the node's position in the flattened array; assign it before recursing into children.
2tout[node] is the last index belonging to node's subtree — set it after all children return.
3u is an ancestor of v exactly when tin[u] ≤ tin[v] ≤ tout[u] — a pure range test.
4Subtree of node = the contiguous slice [tin[node], tout[node]], of length (tout − tin + 1) = subtree size.
5Place each node's value at index tin[node], then a BIT/segment tree gives subtree-sum and point/subtree updates.

Use this pattern when

Subtree aggregate queries or updates (sum/min/max over an entire subtree)
Ancestor / descendant tests in O(1) after an O(n) tour
Path-to-root updates combined with a difference trick on tin/tout
Reducing tree problems to array problems so 1-D structures (BIT, segment tree) apply

Choose another pattern when

Arbitrary path (u to v) queries, not subtree → heavy-light decomposition or LCA-based splitting
The tree changes shape between queries → the tin/tout indices become stale; recompute or use a dynamic structure
Edge-based attributes rather than node-based → store edge values on the deeper endpoint, mind the off-by-one
You only need one subtree sum once → a single DFS sum is simpler than building a BIT

Interview takeaway

The Euler tour is the bridge from tree to array: one DFS assigns each subtree a contiguous index range, after which every 1-D range structure you already know (Fenwick, segment tree, prefix sums) applies to subtree queries unchanged.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternEuler tour (subtree flattening): one DFS stamps tin on entry and tout on exit so each subtree is the contiguous range [tin, tout]. This reduces subtree queries/updates and ancestor tests to array range operations, after which Fenwick or segment trees give O(log n) per operation. The standard adapter from tree problems to 1-D structures.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Subtree Range Update (add x to a whole subtree)
Coming soon
Swap the Fenwick tree for a segment tree with lazy propagation; the subtree is still [tin, tout].
Number of Nodes in the Sub-Tree With the Same Label
Coming soon
Per-label counts gathered during the same DFS that defines the tour.
LCA with Binary Lifting
The tin/tout ancestor test pairs naturally with lifting for ancestor and path queries.
Heavy-Light Decomposition
For path (not subtree) queries, HLD lays chains contiguously so segment trees apply to root-to-node paths.

Same pattern

←

Diameter of Binary Tree

Continue · Next problem

Fenwick Tree (Binary Indexed Tree)

mediumTreesSometimes asked

Euler Tour of a Tree (Subtree Flattening)

Trees & BST · 26 of 41 · 11 min

You are given a rooted tree with n nodes, each holding a value. Support:

1
**update(node, val)** — change the value stored at node.
2
**subtreeSum(node)** — return the sum of values over node and all of its descendants.

Preprocess with an Euler tour so each subtree maps to a contiguous array range, then back the array with a Fenwick tree to make both operations **O(log n)**.

In plain English

Examples

Example 1

Input: tree rooted at 0: 0-1,0-2,1-3,1-4; values=[5,3,2,1,4]; subtreeSum(1)
Output: 8
Note: Subtree of 1 is {1,3,4} = 3 + 1 + 4 = 8.

Example 2

Input: same tree; subtreeSum(0)
Output: 15
Note: The whole tree: 5 + 3 + 2 + 1 + 4 = 15. tin[0]=0, tout[0]=4 covers the entire array.

Example 3

Input: same tree; update(3, 10) then subtreeSum(1)
Output: 17
Note: After node 3 becomes 10, subtree of 1 is 3 + 10 + 4 = 17. The update touches one array index (tin[3]).

Constraints

1 ≤ n ≤ 2 × 10⁵
Up to 2 × 10⁵ interleaved update and subtreeSum calls
The tree is rooted and its shape is static
Sums fit in 64-bit (use long in Java)

Clarifying questions4First question: Are queries about subtrees or arbitrary paths?Explore questions

Q1.Are queries about subtrees or arbitrary paths?
Subtrees here. The Euler tour makes a subtree contiguous. Arbitrary path queries need heavy-light decomposition or LCA splitting instead.
Q2.Does the tree change shape between queries?
No. tin/tout indices assume a fixed shape; if edges changed we would have to recompute the tour or use a dynamic structure.
Q3.Are values on nodes or edges?
Nodes here. Edge values can be pushed onto the deeper endpoint of each edge, with care about the root having no incoming edge.
Q4.How deep can the tree be?
Up to n in a chain, so the DFS that builds the tour should be iterative (explicit stack) to avoid blowing the recursion stack at 2×10⁵.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you can flatten a tree so subtree operations become range operations — assigning tin before recursing and tout after, and recognizing that [tin, tout] is exactly one subtree.

Where candidates slip

Setting tout before recursing (so it does not cover descendants), using a node→array map that is not contiguous, or recursing deeply enough to overflow the stack on a chain.

How to stand out

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Baseline — DFS the Subtree Per Query	`O(n) per query, O(1) update`	`O(n)`	Say this first: it directly answers a subtree query and exposes why repeated queries need flattening.	Read
2	Euler Tour + Fenwick Tree (Optimal)Optimal	`O(n) tour + O(log n) per op`	`O(n)`	The answer they want for many subtree queries/updates. 'Flatten with tin/tout so each subtree is a range, then a BIT handles ranges.'	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.Explore the full tree

tin / tout from one DFS

How to read it:DFS order 0,1,3,4,2 gives tin=[0,1,3,4,2]. Subtree of 1 is array range [1,3] = nodes {1,3,4}.

Rendering diagram…

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Baseline — DFS the Subtree Per Query

TimeO(n) per query, O(1) updateSpaceO(n)

Say this first: it directly answers a subtree query and exposes why repeated queries need flattening.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

To answer subtreeSum(node), run a DFS from node and add up every value reached — that is the subtree.

2Hint 2Explore hint

update(node, val) is a single assignment to the stored value — O(1).

3Hint 3Explore hint

But each subtree query can walk the whole tree (the root's subtree is everything) — O(n) per query, too slow for many queries.

A · Core idea

The direct method needs no preprocessing beyond the adjacency list.

Update is trivial. Storing values per node, update(node, val) is one write — O(1).

Query walks the subtree. subtreeSum(node) runs a DFS rooted at node, summing every value it reaches. Correct, because a subtree is exactly the set of nodes reachable downward from node.

Why it does not scale. A subtree can be the whole tree (querying the root), so a single query is O(n). With up to 2×10⁵ queries that is up to 4×10¹⁰ node visits.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

tree rooted at 0: 0-1,0-2,1-3,1-4; values=[5,3,2,1,4]; subtreeSum(1)

visit 1

sum += 3

Statesum = 3

Final result8

C · Code with teaching comments

Reference implementation previewimport java.util.*; class NaiveSubtree { private final List<List<Integer>> adj; private final long[] val;Explore the full code

solution.javaJava

Baseline — DFS the Subtree Per Query — reference

3 teaching notes

1
import java.util.*;
2
 
3
class NaiveSubtree {
4
    private final List<List<Integer>> adj;
5
    private final long[] val;
6
 
7
    NaiveSubtree(int n, int[][] edges, long[] values) {
8
        adj = new ArrayList<>();
9
        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
10
        for (int[] e : edges) { adj.get(e[0]).add(e[1]); adj.get(e[1]).add(e[0]); }
11
        val = values.clone();
12
    }
13
 
14
    void update(int node, long v) {
15
        // Point update is a single write.
16
        val[node] = v;                  // O(1)
17
    }
18
 
19
    long subtreeSum(int node, int parent) {   // O(n)
20
        // Start the subtree sum with the node's own value.
21
        long sum = val[node];
22
        for (int child : adj.get(node)) {
23
            // Recurse into real children; this whole walk is O(n) per query.
24
            if (child != parent) sum += subtreeSum(child, node);
25
        }
26
        return sum;
27
    }
28
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.28 lines

D · Why it works and complexityO(n) per query, O(1) update timeO(n) spaceOpen the invariant and proofExplore the proof

The wasted work is re-discovering the same subtree boundaries on every query. The Euler tour computes those boundaries once as [tin, tout]; everything after is a range operation on a static layout.

E · Edge cases and pitfalls3Re-walking the subtree every query — O(n) each when the shape never changes.Explore edge cases

Pitfalls

Re-walking the subtree every query — O(n) each when the shape never changes.
Forgetting the parent guard and recursing back up the tree.
Recursive subtree sum on a chain — stack overflow for large n.

03.2

Approach 2 of 2 · Optimal

Euler Tour + Fenwick Tree (Optimal)

TimeO(n) tour + O(log n) per opSpaceO(n)

The answer they want for many subtree queries/updates. 'Flatten with tin/tout so each subtree is a range, then a BIT handles ranges.'

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Run one DFS. When you first reach a node, give it tin[node] = the next free array index; when you finish its whole subtree, set tout[node] = the last index used.

2Hint 2Explore hint

Now the subtree of any node is exactly the contiguous range [tin[node], tout[node]] in the flattened array — because DFS visits a node's descendants consecutively before moving on.

3Hint 3Explore hint

Place value[node] at index tin[node]. Then subtreeSum(node) = rangeSum(tin[node], tout[node]) and update(node, v) is a point update at tin[node] — both O(log n) with a Fenwick tree.

A · Core idea

The Euler tour rewrites the tree as an array so that the messy notion of 'subtree' becomes the clean notion of 'contiguous range'.

Layering a range structure. With values living at tin positions, every subtree question is a range question:

subtreeSum(node) = rangeSum(tin[node], tout[node]),
update(node, v) is a point update at index tin[node].

A Fenwick tree over the flattened array answers both in O(log n). A segment tree works equally well and adds range updates via lazy propagation (e.g. 'add x to every node in a subtree').

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

tree rooted at 0: 0-1,0-2,1-3,1-4; values=[5,3,2,1,4]. Build tour, subtreeSum(1), update(3,10), subtreeSum(1).

Array state

after tour

index→node: 0→0, 1→1, 2→3, 3→4, 4→2

[0]

[1]

[2]

[3]

[4]

Current pointerResolved stateNot processed

Final result8 then 17

C · Code with teaching comments

solution.javaJava

Euler Tour + Fenwick Tree (Optimal) — optimal

5 teaching notes

1
import java.util.*;
2
 
3
class EulerTourSubtree {
4
    private final int n;
5
    private final int[] tin, tout;
6
    private final long[] bit;   // Fenwick tree over the flattened array (1-based)
7
 
8
    EulerTourSubtree(int n, int root, int[][] edges, long[] values) {
9
        this.n = n;
10
        tin = new int[n];
11
        tout = new int[n];
12
        bit = new long[n + 1];
13
        List<List<Integer>> adj = new ArrayList<>();
14
        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
15
        for (int[] e : edges) { adj.get(e[0]).add(e[1]); adj.get(e[1]).add(e[0]); }
16
 
17
        // Iterative DFS to compute tin/tout (chain-safe).
18
        int[] parent = new int[n];
19
        int timer = 0;
20
        Deque<int[]> stack = new ArrayDeque<>();   // {node, childIndex}
21
        parent[root] = root;
22
        stack.push(new int[]{root, 0});
23
        // Entry index assigned the moment the node is first reached.
24
        tin[root] = timer++;
25
        while (!stack.isEmpty()) {
26
            int[] top = stack.peek();
27
            int node = top[0];
28
            if (top[1] < adj.get(node).size()) {
29
                int next = adj.get(node).get(top[1]++);
30
                if (next != parent[node]) {
31
                    parent[next] = node;
32
                    // Each child gets the next free slot before its own children —
33
                    // keeps the subtree contiguous.
34
                    tin[next] = timer++;
35
                    stack.push(new int[]{next, 0});
36
                }
37
            } else {
38
                // Exit index = last slot used by any descendant; set after children
39
                // finish.
40
                tout[node] = timer - 1;   // last index in this subtree
41
                stack.pop();
42
            }
43
        }
44
        // Load values at their tin positions.
45
        // Place each node's value at its tin position in the Fenwick tree (1-based).
46
        for (int v = 0; v < n; v++) bitUpdate(tin[v] + 1, values[v]);
47
    }
48
 
49
    private void bitUpdate(int i, long delta) {
50
        for (; i <= n; i += i & -i) bit[i] += delta;
51
    }
52
 
53
    private long bitPrefix(int i) {
54
        long s = 0;
55
        for (; i > 0; i -= i & -i) s += bit[i];
56
        return s;
57
    }
58
 
59
    void update(int node, long newVal) {
60
        long old = subtreeSumRange(tin[node], tin[node]);
61
        bitUpdate(tin[node] + 1, newVal - old);   // add the delta
62
    }
63
 
64
    private long subtreeSumRange(int l, int r) {  // r inclusive, 0-based tin range
65
        return bitPrefix(r + 1) - bitPrefix(l);
66
    }
67
 
68
    long subtreeSum(int node) {
69
        // Subtree sum is just the range sum over [tin, tout].
70
        return subtreeSumRange(tin[node], tout[node]);
71
    }
72
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.72 lines

D · Why it works and complexityO(n) tour + O(log n) per op timeO(n) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls7subtreeSum(leaf) — tin == tout, so the range is a single index — returns the leaf's own value.Explore edge cases

Edge cases handled

subtreeSum(leaf)tin == tout, so the range is a single index — returns the leaf's own value.
subtreeSum(root)[tin=0, tout=n-1] covers the whole array → total of all values.
ancestor testu is an ancestor of v iff tin[u] ≤ tin[v] ≤ tout[u] — O(1), no traversal.

Pitfalls

Setting tout before recursing into children — the range then excludes the subtree.
Mapping nodes to non-contiguous array slots — breaks the single-range query.
Recursive DFS on a deep chain — stack overflow; use an explicit stack.
Off-by-one between 0-based tin/tout and the 1-based Fenwick indexing.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewimport java.util.*; class EulerTourSubtree { private final int n; private final int[] tin, tout;Explore the playground

Try it — Java· run a complete program; method snippets need a driver

import java.util.*;

class EulerTourSubtree {
    private final int n;
    private final int[] tin, tout;
    private final long[] bit;   // Fenwick tree over the flattened array (1-based)

private void bitUpdate(int i, long delta) {
        for (; i <= n; i += i & -i) bit[i] += delta;
    }

private long bitPrefix(int i) {
        long s = 0;
        for (; i > 0; i -= i & -i) s += bit[i];
        return s;
    }

void update(int node, long newVal) {
        long old = subtreeSumRange(tin[node], tin[node]);
        bitUpdate(tin[node] + 1, newVal - old);   // add the delta
    }

private long subtreeSumRange(int l, int r) {  // r inclusive, 0-based tin range
        return bitPrefix(r + 1) - bitPrefix(l);
    }

long subtreeSum(int node) {
        return subtreeSumRange(tin[node], tout[node]);
    }
}

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

tout set too early

tout must be the LAST index used by any descendant, so it can only be known after all children are explored. Setting it before recursing makes [tin, tout] cover just the node, dropping its subtree.

Explore the code comparison

Don't write this

def dfs(node, parent):
    self.tin[node] = self.timer; self.timer += 1
    self.tout[node] = self.timer - 1     # wrong: set before children
    for c in adj[node]:
        if c != parent: dfs(c, node)

Write this instead

def dfs(node, parent):
    self.tin[node] = self.timer; self.timer += 1
    for c in adj[node]:
        if c != parent: dfs(c, node)
    self.tout[node] = self.timer - 1     # set after all children return

Non-contiguous node mapping

Explore the code comparison

Don't write this

int slot = someHash(node);     // arbitrary positions
bitUpdate(slot, values[node]);

Write this instead

bitUpdate(tin[node] + 1, values[node]);  // position = DFS entry time

Recursive DFS overflow

A chain of 2×10⁵ nodes recurses 2×10⁵ deep, overflowing the default stack in both Java and Python. Build the tour with an explicit stack.

Explore the code comparison

Don't write this

def dfs(node, parent):
    ...
    for c in adj[node]:
        if c != parent: dfs(c, node)   # depth up to n

Write this instead

stack = [(root, iter(adj[root]))]
while stack:
    ...                                # iterative tour, constant call depth

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

DFS timestamps tin/tout so each subtree is a contiguous [tin, tout] range

Code pattern to memorize

timer = 0
def dfs(node, parent):
    tin[node] = timer; timer += 1
    order[tin[node]] = node
    for child != parent: dfs(child, node)
    tout[node] = timer - 1   # last index of this subtree

Rules to remember

1tin[node] is the node's position in the flattened array; assign it before recursing into children.
2tout[node] is the last index belonging to node's subtree — set it after all children return.
3u is an ancestor of v exactly when tin[u] ≤ tin[v] ≤ tout[u] — a pure range test.
4Subtree of node = the contiguous slice [tin[node], tout[node]], of length (tout − tin + 1) = subtree size.
5Place each node's value at index tin[node], then a BIT/segment tree gives subtree-sum and point/subtree updates.

Use this pattern when

Subtree aggregate queries or updates (sum/min/max over an entire subtree)
Ancestor / descendant tests in O(1) after an O(n) tour
Path-to-root updates combined with a difference trick on tin/tout
Reducing tree problems to array problems so 1-D structures (BIT, segment tree) apply

Choose another pattern when

Arbitrary path (u to v) queries, not subtree → heavy-light decomposition or LCA-based splitting
The tree changes shape between queries → the tin/tout indices become stale; recompute or use a dynamic structure
Edge-based attributes rather than node-based → store edge values on the deeper endpoint, mind the off-by-one
You only need one subtree sum once → a single DFS sum is simpler than building a BIT

Interview takeaway

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Subtree Range Update (add x to a whole subtree)
Coming soon
Swap the Fenwick tree for a segment tree with lazy propagation; the subtree is still [tin, tout].
Number of Nodes in the Sub-Tree With the Same Label
Coming soon
Per-label counts gathered during the same DFS that defines the tour.
LCA with Binary Lifting
The tin/tout ancestor test pairs naturally with lifting for ancestor and path queries.
Heavy-Light Decomposition
For path (not subtree) queries, HLD lays chains contiguously so segment trees apply to root-to-node paths.

Same pattern

←

Diameter of Binary Tree

Continue · Next problem

Fenwick Tree (Binary Indexed Tree)