2
$\begingroup$

We have a perfect binary tree on $2^k-1$ nodes. Every node in the tree is marked with probability $\frac{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 ($\frac{1}{2}$ probability of marking nodes), when the algorithm is run on the root of the tree.

$\endgroup$
4
  • $\begingroup$ It's easier if we assume the tree has $2^k-1$ nodes, is that what you meant? $\endgroup$
    – Yuval Filmus
    Nov 9, 2010 at 17:03
  • $\begingroup$ Of course, I will edit it. $\endgroup$
    – utdiscant
    Nov 9, 2010 at 17:32
  • 1
    $\begingroup$ 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. $\endgroup$
    – Yuval Filmus
    Nov 9, 2010 at 19:12
  • $\begingroup$ Exactly. For the purpose of this improvement/correction, you might consider a breadth-first traversal instead of recursion with bools passed around. $\endgroup$
    – Raphael
    Nov 10, 2010 at 9:39

3 Answers 3

Reset to default
2
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Almost (there's a finite number of coins out there). $\endgroup$
    – Yuval Filmus
    Nov 9, 2010 at 19:07
  • $\begingroup$ Plus, the algorithm doesn't stop "upon impact". $\endgroup$
    – Yuval Filmus
    Nov 9, 2010 at 19:10
1
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ 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)$ $\endgroup$
    – Ross Millikan
    Nov 9, 2010 at 17:29
0
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .