# Infinite Search Tree Probibility

I have a question on Search Trees.

I have a balanced, infinite, search tree.

If you check a node at level $l$, the probability of finding a solution at that node is $p^l$.

Questions

The first question is, using breadth-first search, how many solutions will you find on average in an infinitely large tree?

The second question is, using depth-first search, how many solutions will you find on average in an infinitely large tree?

My thinking...

For some reason, I can't get the answer for both out of my head as being 'all of them!' or infinite solutions!

Looking at the way breadth-first search works and taking into account it is a balanced tree, it appears to examine each parent node, and then each of the children of each parent node etc. (Sorry... I know its a crude way to describe - wikipedia does it quite well!) so surely given enough time it will find all of the solutions?

However, for the depth-first, it seems to look at the root node, then the left child, then the left child of that child etc so in an infinite tree surely it won't examine any node except the first one on each level?

Plea

So, hopefully that makes some sense and can someone give me some pointers please?

Thanks

George

• Thinking more deeply (and preparing to be shot down in flames!) For breadth-first search, if you take the number of nodes on a level ($k^l$) and multiply by the probability of a node on that level is a solution is ($p^l$) can you then do a sum to infinity? Oct 9, 2014 at 14:53