Loading…

hardTreesRarely asked

Centroid of a Tree

Q: How do you solve Centroid of a Tree using the Brute Force — Remove Each Node, Measure the Pieces approach?

When to use it: Say this first: it defines a centroid operationally and makes the n − size insight visible before optimizing. The definition is constructive, so the brute force just follows it. **For each candidate.** Pretend to delete the node, then traverse the remaining forest to find the size of each connected component. **Test the balance.** If the maximum component size is at most `⌊n/2⌋`, the candidate qualifies as a centroid; otherwise move on. **Why it is correct.** It literally checks the centroid condition for every node, so it cannot be fooled. **Why it is slow.** Each candidate costs an O(n) traversal, and there are n of them — O(n²). The redundancy is that every traversal recomputes the same subtree sizes. Compute those sizes *once* with a single DFS and each candidate's pieces can be read off in O(1): the child subtree sizes are stored, and the piece above is `n − size[node]`. Time complexity: O(n²). Space complexity: O(n).

Trees & BST · 24 of 41 · 10 min

Given a tree with n nodes, find a **centroid**: a node such that, if it is removed, every connected component that remains has at most ⌊n/2⌋ nodes.

Return any centroid (there may be two adjacent ones). Your solution should run in **O(n)**.

In plain English

We want the most 'balanced' node — the one whose removal does not leave any oversized chunk. Removing a node splits the tree into pieces: one per child subtree, plus the whole rest of the tree hanging above the node. The centroid is the node whose biggest such piece is as small as possible, and that minimum is guaranteed to be ≤ n/2. The single non-obvious part is accounting for the piece above the node, whose size is n minus the node's own subtree.

Examples

Example 1

Input: star: center 0 connected to 1,2,3,4 (n=5); find centroid
Output: 0
Note: Removing 0 leaves four singletons (size 1 each ≤ 2). Removing any leaf leaves a component of size 4 > 2. So 0 is the unique centroid.

Example 2

Input: path 0-1-2-3 (n=4); find centroid
Output: 1 (or 2)
Note: n is even. Removing 1 gives pieces {0} and {2,3}: sizes 1 and 2 ≤ 2. Removing 2 gives {0,1} and {3}: 2 and 1. Both 1 and 2 are centroids — adjacent, as the even-n rule predicts.

Example 3

Input: single node (n=1)
Output: 0
Note: Removing it leaves nothing; the trivial centroid is the node itself.

Constraints

1 ≤ n ≤ 2 × 10⁵
The graph is a tree: connected, n − 1 edges, no cycles
Nodes are 0-indexed; the tree is given as an edge list
A tree always has at least one centroid; even-n balanced trees have two adjacent centroids

Clarifying questions4First question: Centroid or center — which do you mean?Explore questions

Q1.Centroid or center — which do you mean?
Centroid: removing it balances component sizes (≤ n/2 each). The center minimizes tree height/eccentricity and is found by peeling leaves. They can differ; I will solve the centroid.
Q2.Can there be more than one centroid?
One or two. Two occur (and are always adjacent) exactly when n is even and an edge splits the tree into two equal n/2 halves.
Q3.Is balance by node count or something weighted?
Node count here. If pieces were weighted, I would replace 'size' with the summed weight and keep the same logic.
Q4.How deep can the tree be?
Up to n in a chain, so the size DFS should be iterative (explicit stack) to avoid a recursion-stack overflow at 2×10⁵ nodes.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

A centroid of a tree is a node whose removal leaves every remaining component with at most n/2 nodes. Compute subtree sizes with one DFS, then a node is a centroid iff its largest 'piece' — the bigger of (its heaviest child subtree) and (n minus its own subtree, the part above it) — is ≤ ⌊n/2⌋. A tree has one centroid, or two adjacent centroids when n is even. Finding it is O(n).

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you compute subtree sizes correctly and — the real test — remember that removing a node also creates the component ABOVE it of size n − size[node], not just the child subtrees.

Where candidates slip

Only checking child subtree sizes and ignoring the n − size[node] part above the node, or confusing the centroid (balances component sizes) with the center (minimizes height).

How to stand out

Define the centroid precisely, derive the ≤ n/2 test from the size DFS, explain the 1-or-2 centroid fact, and note the O(n) 'walk toward the heavy child' method plus its role in centroid decomposition.

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	Brute Force — Remove Each Node, Measure the Pieces	`O(n²)`	`O(n)`	Say this first: it defines a centroid operationally and makes the n − size insight visible before optimizing.	Read
2	Subtree-Size DFS — Single Pass (Optimal)Optimal	`O(n)`	`O(n)`	The answer they want. 'One DFS for subtree sizes, then each node's largest piece is max(heaviest child, n − size[node]).'	Read

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

Pieces when a node is removed

How to read it:Removing node X creates one component per child subtree plus the 'rest above' of size n − size[X]. The centroid keeps all pieces ≤ n/2.

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

Brute Force — Remove Each Node, Measure the Pieces

TimeO(n²)SpaceO(n)

Say this first: it defines a centroid operationally and makes the n − size insight visible before optimizing.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

For each candidate node, imagine deleting it and run a BFS/DFS over the rest to measure every resulting component.

2Hint 2Explore hint

If the largest component is ≤ n/2, the candidate is a centroid.

3Hint 3Explore hint

Each test is an O(n) traversal and there are n candidates → O(n²). Correct, but it screams 'precompute the sizes once'.

A · Core idea

The definition is constructive, so the brute force just follows it.

For each candidate. Pretend to delete the node, then traverse the remaining forest to find the size of each connected component.

Test the balance. If the maximum component size is at most ⌊n/2⌋, the candidate qualifies as a centroid; otherwise move on.

Why it is correct. It literally checks the centroid condition for every node, so it cannot be fooled.

Why it is slow. Each candidate costs an O(n) traversal, and there are n of them — O(n²). The redundancy is that every traversal recomputes the same subtree sizes. Compute those sizes once with a single DFS and each candidate's pieces can be read off in O(1): the child subtree sizes are stored, and the piece above is n − size[node].

B · Visual dry run

Interactive dry run

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

path 0-1-2-3 (n=4); test each node

remove 0

component {1,2,3} size 3

State3 > 2 → not centroid

Final result1 (and 2)

C · Code with teaching comments

Reference implementation previewimport java.util.*; class BruteForceCentroid { int findCentroid(int n, int[][] edges) { List<List<Integer>> adj = new ArrayList<>();Explore the full code

solution.javaJava

Brute Force — Remove Each Node, Measure the Pieces — reference

3 teaching notes

1
import java.util.*;
2
 
3
class BruteForceCentroid {
4
    int findCentroid(int n, int[][] edges) {
5
        List<List<Integer>> adj = new ArrayList<>();
6
        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
7
        for (int[] e : edges) { adj.get(e[0]).add(e[1]); adj.get(e[1]).add(e[0]); }
8
        for (int removed = 0; removed < n; removed++) {
9
            // Measure the biggest leftover piece after deleting this candidate.
10
            int largest = largestComponent(n, adj, removed);
11
            // The centroid condition stated directly.
12
            if (largest <= n / 2) return removed;
13
        }
14
        return -1;   // unreachable for a valid tree
15
    }
16
 
17
    private int largestComponent(int n, List<List<Integer>> adj, int removed) {
18
        boolean[] seen = new boolean[n];
19
        seen[removed] = true;
20
        int largest = 0;
21
        // Re-traverses the whole tree per candidate — the O(n²) cost.
22
        for (int start = 0; start < n; start++) {
23
            if (seen[start]) continue;
24
            int count = 0;
25
            Deque<Integer> stack = new ArrayDeque<>();
26
            stack.push(start); seen[start] = true;
27
            while (!stack.isEmpty()) {
28
                int node = stack.pop(); count++;
29
                for (int nx : adj.get(node)) if (!seen[nx]) { seen[nx] = true; stack.push(nx); }
30
            }
31
            largest = Math.max(largest, count);
32
        }
33
        return largest;
34
    }
35
}

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

D · Why it works and complexityO(n²) timeO(n) spaceOpen the invariant and proofExplore the proof

Doing the deletion explicitly reveals the components you must measure — including the one above the node. The optimization is purely that those component sizes are all derivable from a single subtree-size DFS, so the n repeated traversals collapse into one.

ComplexityO(n²) time, O(n) space — Removing a node and measuring components is an O(n) traversal; repeating for all n candidates gives O(n²). Fine for small n, too slow at 2×10⁵.

E · Edge cases and pitfalls3Forgetting that deleting an internal node creates a component above it as well as below.Explore edge cases

Pitfalls

Forgetting that deleting an internal node creates a component above it as well as below.
Recomputing component sizes for every candidate — the redundancy the size DFS removes.
Using n/2 with the wrong rounding — use ⌊n/2⌋ consistently.

03.2

Approach 2 of 2 · Optimal

Subtree-Size DFS — Single Pass (Optimal)

TimeO(n)SpaceO(n)

The answer they want. 'One DFS for subtree sizes, then each node's largest piece is max(heaviest child, n − size[node]).'

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Root the tree anywhere and compute size[node] = 1 + sum of children's sizes with one DFS.

2Hint 2Explore hint

When you remove a node, the pieces are its child subtrees (sizes already known) plus the part above it, whose size is n − size[node].

3Hint 3Explore hint

A node is a centroid iff the maximum of those pieces is ≤ n/2. Check every node in a second linear scan (or fold it into the DFS).

A · Core idea

Compute the structure once, then read off the answer.

Step 1 — subtree sizes. Root the tree at any node (say 0) and compute size[node] = 1 + Σ size[child] with a single post-order DFS. size[node] counts the node and everything below it in this rooting.

Step 2 — the pieces created by removal. Deleting node disconnects the tree into:

one component per child, of size size[child], and
the component above node — everything not in node's subtree — of size n − size[node].

The largest piece for node is therefore max( max over children size[child], n − size[node] ). The second term is the one candidates forget; it is exactly the rest of the tree hanging above the node through its parent.

Step 3 — the centroid test. node is a centroid iff that largest piece is ≤ ⌊n/2⌋. Scan all nodes and return any that pass. Because the sizes are precomputed, each node's check is O(deg), so the whole scan is O(n).

Why a centroid always exists, and why ≤ n/2. Start anywhere and repeatedly move to the neighbor whose component (after cutting the edge you came from) exceeds n/2. Each move strictly decreases the size of the heaviest piece, so the walk terminates — at a node where no piece exceeds n/2, the centroid. That same walk is an alternative O(n) algorithm: from the root, keep stepping into the child whose subtree size > n/2 until none qualifies.

Why one or two centroids. If some node has a child subtree of exactly n/2 (only possible when n is even), then both that node and that child satisfy the ≤ n/2 test, and they are adjacent. Otherwise the centroid is unique. There can never be three, because a third would force a piece larger than n/2 somewhere.

Centroid vs center. The centroid balances sizes (this problem). The center minimizes height (tree radius) and is found by repeatedly removing all current leaves until one or two nodes remain. They sometimes coincide but are different in general — naming the right one is part of the interview.

B · Visual dry run

Interactive dry run

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

star: 0 connected to 1,2,3,4 (n=5), rooted at 0

Array state

sizes

size[0]=5, size[1]=size[2]=size[3]=size[4]=1

[0]

[1]

[2]

[3]

[4]

Current pointerResolved stateNot processed

Final result0

C · Code with teaching comments

solution.javaJava

Subtree-Size DFS — Single Pass (Optimal) — optimal

4 teaching notes

1
import java.util.*;
2
 
3
class Centroid {
4
    int findCentroid(int n, int[][] edges) {
5
        if (n == 1) return 0;
6
        List<List<Integer>> adj = new ArrayList<>();
7
        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
8
        for (int[] e : edges) { adj.get(e[0]).add(e[1]); adj.get(e[1]).add(e[0]); }
9
 
10
        int[] size = new int[n];
11
        int[] parent = new int[n];
12
        int root = 0;
13
        // Iterative DFS: discovery order then reverse for post-order sizes.
14
        int[] order = new int[n]; int idx = 0;
15
        boolean[] seen = new boolean[n];
16
        Deque<Integer> stack = new ArrayDeque<>();
17
        stack.push(root); parent[root] = root; seen[root] = true;
18
        while (!stack.isEmpty()) {
19
            int node = stack.pop(); order[idx++] = node;
20
            for (int nx : adj.get(node)) if (!seen[nx]) { seen[nx] = true; parent[nx] = node; stack.push(nx); }
21
        }
22
        for (int i = n - 1; i >= 0; i--) {        // children before parents
23
            int node = order[i];
24
            size[node] = 1;
25
            // Post-order subtree size: node plus all descendants.
26
            for (int c : adj.get(node)) if (c != parent[node]) size[node] += size[c];
27
        }
28
        // Evaluate the largest piece for each node.
29
        for (int node = 0; node < n; node++) {
30
            // The component above node through its parent — the piece most candidates
31
            // forget.
32
            int largest = n - size[node];          // the part ABOVE node
33
            for (int c : adj.get(node)) if (c != parent[node]) {
34
                // Compare against each child subtree, the pieces below node.
35
                largest = Math.max(largest, size[c]);
36
            }
37
            // Centroid condition: no leftover piece exceeds half the tree.
38
            if (largest <= n / 2) return node;
39
        }
40
        return -1;   // unreachable for a valid tree
41
    }
42
}

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

D · Why it works and complexityO(n) timeO(n) spaceOpen the invariant and proofExplore the proof

Everything hinges on a single accounting identity: removing a node leaves child subtrees you already measured plus a top piece of size n − size[node]. Once you internalize that the 'rest above' is just n minus the subtree, the centroid test is a one-line max comparison, and the whole problem is one DFS.

ComplexityO(n) time, O(n) space — One DFS computes all subtree sizes in O(n). A second O(n) scan evaluates each node's largest piece in O(deg) using stored sizes, summing to O(n). Total O(n) time, O(n) space for sizes and the stack.

E · Edge cases and pitfalls7n = 1 — Single node is its own centroid; handled before the DFS.Explore edge cases

Edge cases handled

n = 1Single node is its own centroid; handled before the DFS.
n = 2 (one edge)Both nodes are centroids: removing either leaves one node (size 1 ≤ 1). Two adjacent centroids — the even-n case.
perfectly balanced even tree across one edgeTwo adjacent centroids, each with a child subtree of exactly n/2; the scan returns the first one found.

Pitfalls

Checking only child subtrees and ignoring the n − size[node] piece above the node.
Confusing the centroid (balances sizes) with the center (minimizes height).
Recursive size DFS on a chain of 2×10⁵ nodes — stack overflow; use an explicit stack.
Rounding n/2 inconsistently — use integer ⌊n/2⌋ throughout.

Practice

Try the solution yourself

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

Editable code previewimport java.util.*; class Centroid { int findCentroid(int n, int[][] edges) { if (n == 1) return 0;Explore the playground

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

import java.util.*;

class Centroid {
    int findCentroid(int n, int[][] edges) {
        if (n == 1) return 0;
        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]); }

int[] size = new int[n];
        int[] parent = new int[n];
        int root = 0;
        // Iterative DFS: discovery order then reverse for post-order sizes.
        int[] order = new int[n]; int idx = 0;
        boolean[] seen = new boolean[n];
        Deque<Integer> stack = new ArrayDeque<>();
        stack.push(root); parent[root] = root; seen[root] = true;
        while (!stack.isEmpty()) {
            int node = stack.pop(); order[idx++] = node;
            for (int nx : adj.get(node)) if (!seen[nx]) { seen[nx] = true; parent[nx] = node; stack.push(nx); }
        }
        for (int i = n - 1; i >= 0; i--) {        // children before parents
            int node = order[i];
            size[node] = 1;
            for (int c : adj.get(node)) if (c != parent[node]) size[node] += size[c];
        }
        // Evaluate the largest piece for each node.
        for (int node = 0; node < n; node++) {
            int largest = n - size[node];          // the part ABOVE node
            for (int c : adj.get(node)) if (c != parent[node]) {
                largest = Math.max(largest, size[c]);
            }
            if (largest <= n / 2) return node;
        }
        return -1;   // unreachable for a valid tree
    }
}

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Forgetting the piece above the node

Removing an internal node creates the child-subtree pieces AND the whole rest of the tree above it. That upper piece has size n − size[node]; skip it and almost every node looks like a centroid.

Explore the code comparison

Don't write this

largest = 0
for c in adj[node]:
    if c != parent[node]:
        largest = max(largest, size[c])   # missing the upward piece
if largest <= n // 2:
    return node

Write this instead

largest = n - size[node]                # the part above node
for c in adj[node]:
    if c != parent[node]:
        largest = max(largest, size[c])
if largest <= n // 2:
    return node

Centroid vs center confusion

The center minimizes tree height (found by peeling leaves) while the centroid balances component sizes. They can be different nodes; solving the wrong one fails the test even with correct code.

Explore the code comparison

Don't write this

# Peeling leaves finds the CENTER, not the centroid
while len(remaining) > 2:
    remove_all_current_leaves()

Write this instead

# Centroid: balance sizes
largest = max(n - size[node], max((size[c] for c in children), default=0))
if largest <= n // 2:
    return node

Recursive size DFS overflow

A chain of 2×10⁵ nodes recurses 2×10⁵ deep, overflowing the default call stack in both Java and Python. Compute subtree sizes with an explicit stack and a reverse-order pass.

Explore the code comparison

Don't write this

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

Write this instead

stack = [root]; order = []
while stack:
    node = stack.pop(); order.append(node)
    for c in adj[node]:
        if c != parent[node]: parent[c] = node; stack.append(c)
for node in reversed(order):
    size[node] = 1 + sum(size[c] for c in adj[node] if c != parent[node])

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Subtree-size DFS, then test max(child subtrees, rest-of-tree) ≤ n/2

Code pattern to memorize

size[node] = 1 + Σ size[child]
for each node:
    biggest = max over children of size[child]
    biggest = max(biggest, n - size[node])   # the part above node
    if biggest <= n // 2: node is a centroid

Rules to remember

1The 'piece above' a node has size n − size[node] — do not forget it; it is the most-missed component.
2A node is a centroid iff its largest component after removal ≤ ⌊n/2⌋.
3Every tree has 1 or 2 centroids; 2 (adjacent) happen exactly when n is even and the tree is balanced across one edge.
4Centroid sizes are computed from any root — rooting does not change the answer, only how you phrase 'above'.
5Walking from any start toward the heaviest neighbor whose subtree > n/2 reaches a centroid in O(n).

Use this pattern when

Balancing a tree for divide-and-conquer (centroid decomposition)
Bounding recursion depth: rooting at the centroid limits component size to n/2
Problems over all paths in a tree solved by splitting at a balanced node
Minimizing the maximum subtree size after removing one node

Choose another pattern when

You need the node minimizing total distance to all others → that is also the centroid, but state it as the 1-median; same node, different framing
You need the center (minimizing eccentricity / tree radius) → that is a different node found by peeling leaves (BFS)
Weighted 'balance' by edge length, not node count → adapt the size definition accordingly
Graph has cycles → 'centroid' is undefined; this relies on the tree structure

Interview takeaway

The centroid is the tree's balance point: remove it and no leftover piece exceeds half the tree. One subtree-size DFS plus remembering the 'piece above' (n − size) finds it in O(n), and it is the anchor that makes centroid decomposition's O(n log n) divide-and-conquer work.

Continue

Transfer the pattern to another problem

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

Transferable patternCentroid of a tree: compute subtree sizes with one DFS, then a node is a centroid iff its largest piece after removal — max(heaviest child subtree, n − size[node]) — is ≤ ⌊n/2⌋. There are one or two (adjacent) centroids, found in O(n). It is the balance point that anchors centroid decomposition.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Centroid Decomposition
Coming soon
Recursively make the centroid the root of its component; depth is O(log n), enabling divide-and-conquer over all paths.
Minimum Height Trees
Coming soon
Finds the tree CENTER (1 or 2 nodes) by peeling leaves — contrast with the centroid here.
Sum of Distances in Tree
Coming soon
Re-rooting DP; the node minimizing total distance is the centroid (1-median) view of balance.
Heavy-Light Decomposition
Another size-driven decomposition; the heavy-child idea mirrors the largest-subtree reasoning used here.

Same pattern

←

Lowest Common Ancestor with Binary Lifting

Continue · Next problem

Diameter of Binary Tree

hardTreesRarely asked

Centroid of a Tree

Trees & BST · 24 of 41 · 10 min

Given a tree with n nodes, find a **centroid**: a node such that, if it is removed, every connected component that remains has at most ⌊n/2⌋ nodes.

Return any centroid (there may be two adjacent ones). Your solution should run in **O(n)**.

In plain English

Examples

Example 1

Input: star: center 0 connected to 1,2,3,4 (n=5); find centroid
Output: 0
Note: Removing 0 leaves four singletons (size 1 each ≤ 2). Removing any leaf leaves a component of size 4 > 2. So 0 is the unique centroid.

Example 2

Input: path 0-1-2-3 (n=4); find centroid
Output: 1 (or 2)
Note: n is even. Removing 1 gives pieces {0} and {2,3}: sizes 1 and 2 ≤ 2. Removing 2 gives {0,1} and {3}: 2 and 1. Both 1 and 2 are centroids — adjacent, as the even-n rule predicts.

Example 3

Input: single node (n=1)
Output: 0
Note: Removing it leaves nothing; the trivial centroid is the node itself.

Constraints

1 ≤ n ≤ 2 × 10⁵
The graph is a tree: connected, n − 1 edges, no cycles
Nodes are 0-indexed; the tree is given as an edge list
A tree always has at least one centroid; even-n balanced trees have two adjacent centroids

Clarifying questions4First question: Centroid or center — which do you mean?Explore questions

Q1.Centroid or center — which do you mean?
Centroid: removing it balances component sizes (≤ n/2 each). The center minimizes tree height/eccentricity and is found by peeling leaves. They can differ; I will solve the centroid.
Q2.Can there be more than one centroid?
One or two. Two occur (and are always adjacent) exactly when n is even and an edge splits the tree into two equal n/2 halves.
Q3.Is balance by node count or something weighted?
Node count here. If pieces were weighted, I would replace 'size' with the summed weight and keep the same logic.
Q4.How deep can the tree be?
Up to n in a chain, so the size DFS should be iterative (explicit stack) to avoid a recursion-stack overflow at 2×10⁵ nodes.

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 compute subtree sizes correctly and — the real test — remember that removing a node also creates the component ABOVE it of size n − size[node], not just the child subtrees.

Where candidates slip

Only checking child subtree sizes and ignoring the n − size[node] part above the node, or confusing the centroid (balances component sizes) with the center (minimizes height).

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	Brute Force — Remove Each Node, Measure the Pieces	`O(n²)`	`O(n)`	Say this first: it defines a centroid operationally and makes the n − size insight visible before optimizing.	Read
2	Subtree-Size DFS — Single Pass (Optimal)Optimal	`O(n)`	`O(n)`	The answer they want. 'One DFS for subtree sizes, then each node's largest piece is max(heaviest child, n − size[node]).'	Read

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

Pieces when a node is removed

How to read it:Removing node X creates one component per child subtree plus the 'rest above' of size n − size[X]. The centroid keeps all pieces ≤ n/2.

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

Brute Force — Remove Each Node, Measure the Pieces

TimeO(n²)SpaceO(n)

Say this first: it defines a centroid operationally and makes the n − size insight visible before optimizing.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

For each candidate node, imagine deleting it and run a BFS/DFS over the rest to measure every resulting component.

2Hint 2Explore hint

If the largest component is ≤ n/2, the candidate is a centroid.

3Hint 3Explore hint

Each test is an O(n) traversal and there are n candidates → O(n²). Correct, but it screams 'precompute the sizes once'.

A · Core idea

The definition is constructive, so the brute force just follows it.

For each candidate. Pretend to delete the node, then traverse the remaining forest to find the size of each connected component.

Test the balance. If the maximum component size is at most ⌊n/2⌋, the candidate qualifies as a centroid; otherwise move on.

Why it is correct. It literally checks the centroid condition for every node, so it cannot be fooled.

B · Visual dry run

Interactive dry run

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

path 0-1-2-3 (n=4); test each node

remove 0

component {1,2,3} size 3

State3 > 2 → not centroid

Final result1 (and 2)

C · Code with teaching comments

Reference implementation previewimport java.util.*; class BruteForceCentroid { int findCentroid(int n, int[][] edges) { List<List<Integer>> adj = new ArrayList<>();Explore the full code

solution.javaJava

Brute Force — Remove Each Node, Measure the Pieces — reference

3 teaching notes

1
import java.util.*;
2
 
3
class BruteForceCentroid {
4
    int findCentroid(int n, int[][] edges) {
5
        List<List<Integer>> adj = new ArrayList<>();
6
        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
7
        for (int[] e : edges) { adj.get(e[0]).add(e[1]); adj.get(e[1]).add(e[0]); }
8
        for (int removed = 0; removed < n; removed++) {
9
            // Measure the biggest leftover piece after deleting this candidate.
10
            int largest = largestComponent(n, adj, removed);
11
            // The centroid condition stated directly.
12
            if (largest <= n / 2) return removed;
13
        }
14
        return -1;   // unreachable for a valid tree
15
    }
16
 
17
    private int largestComponent(int n, List<List<Integer>> adj, int removed) {
18
        boolean[] seen = new boolean[n];
19
        seen[removed] = true;
20
        int largest = 0;
21
        // Re-traverses the whole tree per candidate — the O(n²) cost.
22
        for (int start = 0; start < n; start++) {
23
            if (seen[start]) continue;
24
            int count = 0;
25
            Deque<Integer> stack = new ArrayDeque<>();
26
            stack.push(start); seen[start] = true;
27
            while (!stack.isEmpty()) {
28
                int node = stack.pop(); count++;
29
                for (int nx : adj.get(node)) if (!seen[nx]) { seen[nx] = true; stack.push(nx); }
30
            }
31
            largest = Math.max(largest, count);
32
        }
33
        return largest;
34
    }
35
}

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

D · Why it works and complexityO(n²) timeO(n) spaceOpen the invariant and proofExplore the proof

ComplexityO(n²) time, O(n) space — Removing a node and measuring components is an O(n) traversal; repeating for all n candidates gives O(n²). Fine for small n, too slow at 2×10⁵.

E · Edge cases and pitfalls3Forgetting that deleting an internal node creates a component above it as well as below.Explore edge cases

Pitfalls

Forgetting that deleting an internal node creates a component above it as well as below.
Recomputing component sizes for every candidate — the redundancy the size DFS removes.
Using n/2 with the wrong rounding — use ⌊n/2⌋ consistently.

03.2

Approach 2 of 2 · Optimal

Subtree-Size DFS — Single Pass (Optimal)

TimeO(n)SpaceO(n)

The answer they want. 'One DFS for subtree sizes, then each node's largest piece is max(heaviest child, n − size[node]).'

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Root the tree anywhere and compute size[node] = 1 + sum of children's sizes with one DFS.

2Hint 2Explore hint

When you remove a node, the pieces are its child subtrees (sizes already known) plus the part above it, whose size is n − size[node].

3Hint 3Explore hint

A node is a centroid iff the maximum of those pieces is ≤ n/2. Check every node in a second linear scan (or fold it into the DFS).

A · Core idea

Compute the structure once, then read off the answer.

Step 2 — the pieces created by removal. Deleting node disconnects the tree into:

one component per child, of size size[child], and
the component above node — everything not in node's subtree — of size n − size[node].

B · Visual dry run

Interactive dry run

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

star: 0 connected to 1,2,3,4 (n=5), rooted at 0

Array state

sizes

size[0]=5, size[1]=size[2]=size[3]=size[4]=1

[0]

[1]

[2]

[3]

[4]

Current pointerResolved stateNot processed

Final result0

C · Code with teaching comments

solution.javaJava

Subtree-Size DFS — Single Pass (Optimal) — optimal

4 teaching notes

1
import java.util.*;
2
 
3
class Centroid {
4
    int findCentroid(int n, int[][] edges) {
5
        if (n == 1) return 0;
6
        List<List<Integer>> adj = new ArrayList<>();
7
        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
8
        for (int[] e : edges) { adj.get(e[0]).add(e[1]); adj.get(e[1]).add(e[0]); }
9
 
10
        int[] size = new int[n];
11
        int[] parent = new int[n];
12
        int root = 0;
13
        // Iterative DFS: discovery order then reverse for post-order sizes.
14
        int[] order = new int[n]; int idx = 0;
15
        boolean[] seen = new boolean[n];
16
        Deque<Integer> stack = new ArrayDeque<>();
17
        stack.push(root); parent[root] = root; seen[root] = true;
18
        while (!stack.isEmpty()) {
19
            int node = stack.pop(); order[idx++] = node;
20
            for (int nx : adj.get(node)) if (!seen[nx]) { seen[nx] = true; parent[nx] = node; stack.push(nx); }
21
        }
22
        for (int i = n - 1; i >= 0; i--) {        // children before parents
23
            int node = order[i];
24
            size[node] = 1;
25
            // Post-order subtree size: node plus all descendants.
26
            for (int c : adj.get(node)) if (c != parent[node]) size[node] += size[c];
27
        }
28
        // Evaluate the largest piece for each node.
29
        for (int node = 0; node < n; node++) {
30
            // The component above node through its parent — the piece most candidates
31
            // forget.
32
            int largest = n - size[node];          // the part ABOVE node
33
            for (int c : adj.get(node)) if (c != parent[node]) {
34
                // Compare against each child subtree, the pieces below node.
35
                largest = Math.max(largest, size[c]);
36
            }
37
            // Centroid condition: no leftover piece exceeds half the tree.
38
            if (largest <= n / 2) return node;
39
        }
40
        return -1;   // unreachable for a valid tree
41
    }
42
}

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

D · Why it works and complexityO(n) timeO(n) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls7n = 1 — Single node is its own centroid; handled before the DFS.Explore edge cases

Edge cases handled

n = 1Single node is its own centroid; handled before the DFS.
n = 2 (one edge)Both nodes are centroids: removing either leaves one node (size 1 ≤ 1). Two adjacent centroids — the even-n case.
perfectly balanced even tree across one edgeTwo adjacent centroids, each with a child subtree of exactly n/2; the scan returns the first one found.

Pitfalls

Checking only child subtrees and ignoring the n − size[node] piece above the node.
Confusing the centroid (balances sizes) with the center (minimizes height).
Recursive size DFS on a chain of 2×10⁵ nodes — stack overflow; use an explicit stack.
Rounding n/2 inconsistently — use integer ⌊n/2⌋ throughout.

Practice

Try the solution yourself

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

Editable code previewimport java.util.*; class Centroid { int findCentroid(int n, int[][] edges) { if (n == 1) return 0;Explore the playground

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

import java.util.*;

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Forgetting the piece above the node

Removing an internal node creates the child-subtree pieces AND the whole rest of the tree above it. That upper piece has size n − size[node]; skip it and almost every node looks like a centroid.

Explore the code comparison

Don't write this

largest = 0
for c in adj[node]:
    if c != parent[node]:
        largest = max(largest, size[c])   # missing the upward piece
if largest <= n // 2:
    return node

Write this instead

largest = n - size[node]                # the part above node
for c in adj[node]:
    if c != parent[node]:
        largest = max(largest, size[c])
if largest <= n // 2:
    return node

Centroid vs center confusion

The center minimizes tree height (found by peeling leaves) while the centroid balances component sizes. They can be different nodes; solving the wrong one fails the test even with correct code.

Explore the code comparison

Don't write this

# Peeling leaves finds the CENTER, not the centroid
while len(remaining) > 2:
    remove_all_current_leaves()

Write this instead

# Centroid: balance sizes
largest = max(n - size[node], max((size[c] for c in children), default=0))
if largest <= n // 2:
    return node

Recursive size DFS overflow

A chain of 2×10⁵ nodes recurses 2×10⁵ deep, overflowing the default call stack in both Java and Python. Compute subtree sizes with an explicit stack and a reverse-order pass.

Explore the code comparison

Don't write this

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

Write this instead

stack = [root]; order = []
while stack:
    node = stack.pop(); order.append(node)
    for c in adj[node]:
        if c != parent[node]: parent[c] = node; stack.append(c)
for node in reversed(order):
    size[node] = 1 + sum(size[c] for c in adj[node] if c != parent[node])

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Subtree-size DFS, then test max(child subtrees, rest-of-tree) ≤ n/2

Code pattern to memorize

size[node] = 1 + Σ size[child]
for each node:
    biggest = max over children of size[child]
    biggest = max(biggest, n - size[node])   # the part above node
    if biggest <= n // 2: node is a centroid

Rules to remember

1The 'piece above' a node has size n − size[node] — do not forget it; it is the most-missed component.
2A node is a centroid iff its largest component after removal ≤ ⌊n/2⌋.
3Every tree has 1 or 2 centroids; 2 (adjacent) happen exactly when n is even and the tree is balanced across one edge.
4Centroid sizes are computed from any root — rooting does not change the answer, only how you phrase 'above'.
5Walking from any start toward the heaviest neighbor whose subtree > n/2 reaches a centroid in O(n).

Use this pattern when

Balancing a tree for divide-and-conquer (centroid decomposition)
Bounding recursion depth: rooting at the centroid limits component size to n/2
Problems over all paths in a tree solved by splitting at a balanced node
Minimizing the maximum subtree size after removing one node

Choose another pattern when

You need the node minimizing total distance to all others → that is also the centroid, but state it as the 1-median; same node, different framing
You need the center (minimizing eccentricity / tree radius) → that is a different node found by peeling leaves (BFS)
Weighted 'balance' by edge length, not node count → adapt the size definition accordingly
Graph has cycles → 'centroid' is undefined; this relies on the tree structure

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

Centroid Decomposition
Coming soon
Recursively make the centroid the root of its component; depth is O(log n), enabling divide-and-conquer over all paths.
Minimum Height Trees
Coming soon
Finds the tree CENTER (1 or 2 nodes) by peeling leaves — contrast with the centroid here.
Sum of Distances in Tree
Coming soon
Re-rooting DP; the node minimizing total distance is the centroid (1-median) view of balance.
Heavy-Light Decomposition
Another size-driven decomposition; the heavy-child idea mirrors the largest-subtree reasoning used here.

Same pattern

←

Lowest Common Ancestor with Binary Lifting

Continue · Next problem

Diameter of Binary Tree