Expected Steps to Remove a Random Subtree Tree
You are given a rooted tree with $n$ nodes. At each step, you pick one of the remaining non-root nodes uniformly at random and remove it along with its entire subtree. You repeat this process until only the root remains.
Find the expected number of steps to clear the tree.
Hints
- Rather than tracking the tree's state after each removal, focus on a single node $i$ and ask: what is the probability that $i$ is the one directly chosen (versus being swept away by an ancestor's removal)?
- Node $i$ is directly chosen if and only if $i$ is selected before any of its ancestors. By the symmetry of uniform sampling, each node in the set $\{i, \text{parent}(i), \ldots\}$ is equally likely to be picked first.
- Once you have $P(i \text{ is directly chosen}) = 1/\text{depth}(i)$, apply linearity of expectation: $E[\text{steps}] = \sum_{i \neq \text{root}} 1/\text{depth}(i)$.
Worked Solution
How to Think About It: The naive approach -- trying to track what the tree looks like after each removal -- is a mess because the state space is enormous. The right move is to step back and think about each node's fate independently. For a given non-root node $i$, ask: what is the probability that $i$ itself is directly chosen (as opposed to being swept away when one of its ancestors is chosen)? That probability is all you need, because by linearity of expectation the total expected steps is just the sum of these probabilities over all non-root nodes.
Quick Estimate: Consider a simple path graph: root -> A -> B -> C (so 4 nodes, depths 1, 2, 3, 4). Node A has depth 2 (root + A on its path), so $P(A \text{ chosen}) = 1/2$. Node B has depth 3, $P = 1/3$. Node C has depth 4, $P = 1/4$. Expected steps $= 1/2 + 1/3 + 1/4 = 6/12 + 4/12 + 3/12 = 13/12 \approx 1.08$. This makes intuitive sense -- on a long chain you usually just pick the node near the root and wipe out everyone below in one shot.
For a balanced binary tree of depth 3 (root + 2 children + 4 grandchildren = 7 nodes), depth-2 nodes contribute $2 \times 1/2 = 1$ and depth-3 nodes contribute $4 \times 1/3 \approx 1.33$. Expected steps $\approx 1 + 1.33 = 2.33$.
Approach: Linearity of expectation plus a symmetry argument to compute each node's selection probability.
Formal Solution:
Define depth so that the root has depth 0 and its children have depth 1. For any non-root node $i$, let $S_i = \{i, \text{parent}(i), \text{grandparent}(i), \ldots, \text{child-of-root}(i)\}$ be the set consisting of $i$ and all of its proper ancestors excluding the root (since the root is never chosen). Then $|S_i| = \text{depth}(i)$.
Node $i$ is directly chosen (contributes a step) if and only if $i$ is the first member of $S_i$ to be selected across the entire process. By the symmetry of uniform sampling, each member of $S_i$ is equally likely to be the first one selected. Therefore:
$$P(i \text{ is directly chosen}) = \frac{1}{|S_i|} = \frac{1}{\text{depth}(i)}$$
where depth is measured with root at depth 0, so $\text{depth}(i) \geq 1$ for all non-root nodes.
Define indicator $X_i = 1$ if node $i$ is directly chosen. The total number of steps is $X = \sum_{i \,:\, i \neq \text{root}} X_i$.
By linearity of expectation:
$$E[X] = \sum_{i \,:\, i \neq \text{root}} E[X_i] = \sum_{i \,:\, i \neq \text{root}} \frac{1}{\text{depth}(i)}$$
Justifying the symmetry argument: Why is the "first selected" uniform? At each step we draw uniformly among all remaining nodes. The relative order in which nodes in $S_i$ are reached (ignoring steps that touch neither) is a uniformly random permutation of $S_i$. This is a standard result: for any finite set of items drawn uniformly without replacement (or equivalently, a random permutation), each element is equally likely to appear first.
Answer:
$$\boxed{E[\text{steps}] = \sum_{i \,:\, i \neq \text{root}} \frac{1}{\text{depth}(i)}}$$
where $\text{depth}(i)$ counts the number of non-root ancestors of $i$ plus $i$ itself (equivalently, depth of root $= 0$, depth of root's children $= 1$, etc.).
Intuition
The core trick here is a classic one in probability on trees and random processes: instead of reasoning about the global state (which is complicated and path-dependent), you reason about each element's fate independently, then add up. The key question for each node is not "when will I be removed?" but "will I be the cause of my own removal, or will an ancestor take me out first?" That reframing immediately suggests the right calculation.
The "first in a random permutation" argument -- that among a set of nodes drawn uniformly, each is equally likely to be selected first -- is extraordinarily useful in quant interviews. It underlies solutions to problems ranging from random graph connectivity to order book priority queues to coupon collector variants. Whenever you see a uniform random process and you want to know the probability that a particular element "wins" a race to be selected, check if the symmetry argument applies. Here it does cleanly, and the result $1/\text{depth}(i)$ has a satisfying interpretation: deeper nodes are less likely to be directly chosen because they have more ancestors that could preempt them.