# Expected time of tree search algorithm on random input

We have a perfect binary tree on 2^k-1 nodes. Every node in the tree is marked with probability 1/2, and a node is either marked or unmarked. We want to find a marked node and return it. Our algorithm is as follows

procedure find(v);
if (v is marked)
print(v)
else if (v is not a leaf)
v1 is the left child of v
v2 is the right child of v
find(v1) ( recursive call )
find(v2) ( recursive call )


So the algorithm basically starts from the top. Searches down the tree in a depth first fashion, and returns at least one marked node if there are any. Note that the algorithm can easily return multiple marked nodes.

Now what I want to do is to say something about the expected number of nodes the algorithm will consider on a random tree (1/2 probability of marking nodes), when the algorithm is run on the root of the tree.

-
It's easier if we assume the tree has $2^k-1$ nodes, is that what you meant? –  Yuval Filmus Nov 9 '10 at 17:03
Of course, I will edit it. –  utdiscant Nov 9 '10 at 17:32
A better algorithm will stop upon finding the first marked node. Make it into a function returning a Boolean value (found or not), and then only continue to find(v2) if find(v1) wasn't successful. –  Yuval Filmus Nov 9 '10 at 19:12
Exactly. For the purpose of this improvement/correction, you might consider a breadth-first traversal instead of recursion with bools passed around. –  Raphael Nov 10 '10 at 9:39

Let's assume as Yuval suggests that 2^k - 1 nodes are meant.

We can get a recursive expression for the expected number of nodes N(k), where the basis case is N(1) = 1, i.e. that if we have one node, we have to visit it (whether or not it turns out to be marked).

If k > 1, then with probability 1/2 the top node or root of the binary tree will be marked, and thus only the top node will be visited. In the alternative we have to visit both left and right subtrees. Thus:

N(k+1) = 1/2 + (1/2)*[N(k) + N(k)] = 1/2 + N(k)

The solution of this recurrence relation + initial condition is simply:

N(k) = (k+1)/2

regardless of whether there are or are not marked nodes.

regards, hm

Correction: As Ross points out (see comment), the recurrence is N(k) = 1 + N(k), with solution N(k) = k, due to the fact that we will always visit the top node (before finding out whether it's marked).

-
It should be $N(k+1)=1/2+1/2*(2N(k)+1)$ as if the first node is not marked you still visited it. This is $N(k)=k$. It does depend upon marking-if the marking is probability p then $N(k+1)=p+(1-p)*(2N(k)+1)$ –  Ross Millikan Nov 9 '10 at 17:29

Assuming nodes are marked by independent coin flips, then the order that you visit nodes has no effect whatsoever. So the expected number of nodes visited is exactly the expected number of fair coin flips to get heads: 2.

-
Almost (there's a finite number of coins out there). –  Yuval Filmus Nov 9 '10 at 19:07
Plus, the algorithm doesn't stop "upon impact". –  Yuval Filmus Nov 9 '10 at 19:10

Idea: calculate recursively the expected number of nodes the algorithm visits on a complete binary tree of height $n$ assuming at least one node is marked. Note that this assumptions alters slightly the probabilities of relevant events.

EDIT: This idea only makes sense if you stop after the first marked node is found, in which case JeffE's solution is much much better.

-