Probability of finding a node in a binary tree

Question

I'm trying to solve this puzzle:

We're given a full binary tree of height $6$, and told that there exists $1$ node, $n$, in this tree that's burned down: that means $n$ and its descendants do not exist anymore. Each node has an equal chance of being burned out.

If we select a target at random and try to reach it starting from the root, what's the probability that we'll actually reach the target?

I'm not sure where to even start -- I can't quite get the intuition to solve this problem.

Answer 1

So with $d=6$, there are $2^{d+1}-1$ nodes in total. Depending on its position, the burned down node $n$ covers between $1$ leaf (only itself) and $2^d$ leaves (if $n$ is the root). More generally, if $E_d$ is the expected number of leaves covered by a random node in a full binary tree of height $d$, then we have the recursion $$ E_{d}=\frac1{2^{d+1}-1}\cdot 2^d+\left(1-\frac1{2^{d+1}-1}\right)\cdot E_{d-1}=\frac{2^d+2\cdot(2^{d}-1)E_{d-1}}{2^{d+1}-1}$$ with initial condition $E_0=1$. One finds (and then quickly verifies) that this leads to $$ E_d=\frac{(d+1)2^d}{2^{d+1}-1}.$$So in our situation, the expected number of leaves covered by $n$ is $$ E_6=\frac{7\cdot 64}{127}=\frac{448}{127}.$$ How does this help with the original question? A random walk from the root will end up at a leaf of the (un-burnt) tree, uniformly(!) picked from its $2^6$ leaves. On the way, we hit $n$ if and only if the final leaf is among the leaves covered by $n$. We conclude that the probability of hitting $n$ is $$ p=\frac{E_6}{2^6}=\frac 7{127}.$$

Answer 2

There are $1+2+4+\dots+64=127$ nodes in this tree.

• There is a $\frac{64}{127}$ chance that the burnt node is at the lowest level. In that case, the chance you hit the burnt node is $\frac1{64}$. The probability of hitting the burnt node at this level is therefore $\frac{64}{127}\cdot \frac{1}{64}=\frac1{127}$.

• There is a $\frac{32}{127}$ chance that the burnt node is at the second lowest level. In that case, the chance you hit the burnt node is $\frac1{32}$. The probability of hitting the burnt node at this level is therefore $\frac{32}{127}\cdot \frac{1}{32}=\frac1{127}$.

• There is a $\frac{16}{127}$ chance that the burnt node is at the third lowest level. In that case, the chance you hit the burnt node is $\frac1{16}$. The probability of hitting the burnt node at this level is therefore $\frac{16}{127}\cdot \frac{1}{16}=\frac1{127}$.

• $\vdots$

You see the pattern. For each level, the probability of hitting the burnt node at that level is $\frac1{127}$. Adding up for each level, the probability of hitting the burnt node is $\frac{7}{127}$.

Answer 3

There are two randomly chosen nodes, the burned one $B$, and the target $T$. You specified that $B$ is uniformly random among the $127$ nodes. However, the final answer also depends on how the target is chosen - in particular, is it uniformly random among the $127$ nodes or among just the $64$ leaves?

If $T$ is uniformly random among the $64$ leaves, the answers by Mike Earnest and Hagen von Eitzen already addressed this case. Here's a shorter proof: For whichever leaf $T$ you choose, it is unreachable iff $B$ is along $T$'s path to the root, and this path consists of $7$ nodes (including $T$ and the root). So the probability is $7/127$ for any leaf $T$, which means it is also $7/127$ averaged over all leaves $T$.

If $T$ is uniformly random among all $127$ nodes, let $H(T) \in [0, 6]$ denote the height of $T$, e.g. $H(root)=0$ and $H(any\ \ leaf)=6$. Then, for whichever $T$ you choose it is unreachable iff $B$ is along $T$'s path to the root, and this path consists of $H(T)+1$ nodes (including $T$ and the root). So the probability is ${H(T)+1 \over 127}$ for any given $T$. For the overall probability you need to average over all $T$, so the answer is ${E[H(T)]+ 1 \over 127}$.

Now you need to calculate the average height $E[H(T)]$. This is simple by explicit counting:

$$E[H(T)] = 0 \times {1 \over 127} + 1 \times {2 \over 127} + 2 \times {4 \over 127} + \dots 6 \times {64 \over 127}\approx 5.06$$

$$Prob(\text{$T$ is unreachable}) = {E[H(T)] + 1 \over 127} \approx {6.06 \over 127} \approx 0.048$$