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.
 A: 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.
A: 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).
A: 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.
