Results 1 to 2 of 2

Math Help - Counting nodes in a tree (series?)

  1. #1
    Member
    Joined
    Sep 2010
    Posts
    96

    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?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Junior Member
    Joined
    Nov 2012
    From
    Hyrule
    Posts
    39
    Thanks
    10

    Re: Counting nodes in a tree (series?)

    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)
    Last edited by Link; November 28th 2012 at 04:10 PM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. draw a graph with nodes
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: October 4th 2011, 08:40 PM
  2. k Shortest Paths between several nodes
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: April 4th 2010, 05:22 AM
  3. Displacements at the nodes and for the forces
    Posted in the Calculus Forum
    Replies: 0
    Last Post: November 4th 2009, 04:23 PM
  4. Saddles and Nodes
    Posted in the Differential Geometry Forum
    Replies: 2
    Last Post: March 17th 2009, 01:25 PM
  5. Number of nodes in a tree
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: February 10th 2009, 07:02 AM

Search Tags


/mathhelpforum @mathhelpforum