Recursion and counting/incrementing

[Ramzi89]

Hey

I'm practicing with recursion. I'm trying to write a function that will count all the nodes in a binary tree. given the following class definition.

  class Binode
{public:
    int n;
    Binode* l, *r;
}

So what I've come with is

int number(Binode* p, int& x)
{ if (p == NULL)
     return x;
  else
     {
      n++;
       return (number (p -> l, x)+ number (p -> r, x));
     }
}

Is there anyway to intialise x at the beggining? Also can anyone think of way to do this without having x as a parameter? So just a Binode* as a paramater?

[xish]

You could use a static variable:

static int x = #;

Better answers below.

[cire]

Untested:

unsigned count_nodes(Binode*p)
{
    if ( p == nullptr )
         return 0 ;

    return 1 + count_nodes(p->l) + count_nodes(p->r) ;
}

[vlad from moscow]

size_t number( Binode* p )
{ 
   return ( p ? 1 + number( p->l ) + number( p->r ) : 0 );
}

[ResidentBiscuit]

In not quite real code:

int count(node* n)
{
    if(n == null) return 0;
    return count(n.leftChild) + count(n.rightChild) + 1;
}

[Ramzi89]

That would work. Why didn't I think of that...

Thanks.

I' trying this one now which counts the depth of a tree. This is untested but I think it should work. Is their anyway you could do this with one parameter a Binode*?

int depth (Binode*p, int&x, int& y)
{  
      if ( p == NULL)
        {  
                if(x > y)
                  {
                        y =  x;
                        x = 0;                        
                        return y;
                  }
      else
         {x++;
           return depth(p-> l, x, y) > depth(p -> r, x, y) ? return depth(p-> l, x, y) : depth(p -> r, x, y);
         }
}

I I know this is inefficient as well...

[cire]

unsigned depth(Binode* p)
{
    if  ( p == nullptr )
        return 0 ;

    unsigned rdepth = depth(p->r);
    unsigned ldepth = depth(p->l) ;

    return rdepth < ldepth ? 1+ldepth : 1+rdepth ;
}

[edit: corrected bug]

[Ramzi89]

EDIT: I'm sure it works just trying to figure out how. lol. Its the last comparison thats baffling me.

[cire]

Nothing is stopping you from playing around with the code or running it in a debugger to trace through it.

Maybe this will help you visualize what's going on:
http://ideone.com/4vI4e4

[Ramzi89]

I can see whats going on but piecing the actual logic together is another issue. Got it now. The power of sleep.. Thank you for the help.