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.