# Probability of finding a node in a binary tree

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.

• Can you define "hit this target"? Commented Sep 27, 2019 at 13:05
• @OliverRoche successfully reach the target, with the traversal starting from the root Commented Sep 27, 2019 at 13:07
• Like, with a $\frac{1}{2}$ probability of chosing each son at each step? Commented Sep 27, 2019 at 13:10
• What is the probability that the burned-out node is at depth $1$? Depth 2? Given that the burned-out node is at depth $x$, what is the probability that the target can be reached? Commented Sep 27, 2019 at 13:15
• The burnt node is uniformly random among all nodes (internal and leaves), but what about the target? Is that (A) uniformly random among all original nodes (internal & leaves) or (B) uniformly random among all original leaves (i.e. uniform random walk of length $6$)? Those are different questions. Commented Sep 27, 2019 at 13:23

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}.$$

• wow, thanks! This seems super math-heavy...I'm wondering if there's any intuition to get an approximate Commented Sep 27, 2019 at 13:35
• this answer assumes the "target" is a random leaf (as opposed to a random node (internal or leaf)) of the original tree. if this assumption is correct, a much faster way to arrive at $p=7/127$ is to realize that no matter which target leaf $L$ is picked, it no longer exists iff the burned node is along the path from root to $L$. there are $7$ such nodes (including root and $L$) along that path, among the $2^7-1 = 127$ nodes in the original tree. Commented Sep 27, 2019 at 16:59

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}$$.

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$$