Thread: Counting nodes in a tree (series?)

I have a tree with a root node at level d = 0. Each node in my tree has b children. If I'm trying to reach some goal node G, and I know that G is ALWAYS the first (leftmost) child on any level. How many nodes will I have to check if I use a breadth first search to traverse my tree?

Breadth first search refers to examining an entire level before moving onto the next level. That is, we first examine each node at depth d before examining any of their children.

I was thinking of this problem as a series type of problem. I set b = 2 to get a look at an example tree and then counted how many nodes needed to be checked at each level. I got the series : 1,4,13,40,121 from counting the accumulated total of nodes so far at level d, but I can't make anything out of this information.

Can anyone help me?

I think :

at lvl 0, you have explored 1 node, at 1st lvl, you have 1+b nodes, at 2nd, 1+b+b²... at lvl n, 1+b+b²+...+b^n. Because G is lefmost, you know that the number of nodes you have to explore before is exactly written 1+b+b²+...+b^ n, and n is the lvl before G, lvl(G)-1. so you have to explore 1+b+b²+...+b^(lvl(G)-1)
btw, we found the same thing for b=3 : (1,4,13,40,121)=(1,1+3,1+3+3²,1+3+3²+3^3,1+3+3^²+3 ^3+3^4)