### Recursion and counting/incrementing

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.

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

So what I've come with is

 ``123456789`` ``````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?
You could use a static variable:

`static int x = #; `

Last edited on
Untested:

 ``1234567`` ``````unsigned count_nodes(Binode*p) { if ( p == nullptr ) return 0 ; return 1 + count_nodes(p->l) + count_nodes(p->r) ; }``````
 ``1234`` ``````size_t number( Binode* p ) { return ( p ? 1 + number( p->l ) + number( p->r ) : 0 ); }``````
In not quite real code:

 ``12345`` ``````int count(node* n) { if(n == null) return 0; return count(n.leftChild) + count(n.rightChild) + 1; }``````
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*?

 ``123456789101112131415`` ``````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...
Last edited on
 ``12345678910`` ``````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]
Last edited on
EDIT: I'm sure it works just trying to figure out how. lol. Its the last comparison thats baffling me.
Last edited on
Nothing is stopping you from playing around with the code or running it in a debugger to trace through it.