Ok people, I understand stacks and heaps, but when it comes to recursivity and binary trees, i have a major problem trying to understand this.

if someone peopl explain me, how this recur. stuff works, I would be happy!
For example, where the value goes, wich function is called and processed etc.
I'll leave here a simple example code with a few questions, thanks!

``````int BT::sumleafs(){
int s=0;

if(root==NULL)
cout<<"empty!\n";
else
s+=sumleafs(root);   //1)IT SUMS WHAT?
cout<<"total: "<<s<<endl;
return 0;
}

int BT::sumleafs(NoTree *Ptree){
int s=0;

if(Ptree->right==NULL && Ptree->left==NULL){//sums the leafs if it doesn't has sons
s+= Ptree->value;
return s;
}

s+= sumleafs(Ptree->left); //2)what is this?It calls the same function, ok
//but if he is always going to the left, how its
//supose to go back to check the rest of the elements
//And what the s+= sums anyway? a node?

s+= sumleafs(Ptree->right);

return s;
}``````

That function is badly coded and harder to understand. I haven't tried it but
this should work and easier to read :

``````//calls a helper function
int sumLeafs(){
int sum = 0;
_sumLeafs(getRoot(),sum); //_sumLeafs is a private helper function
return sum;
}

//a node is a leaf, if it has No children
bool isLeaf(const Node* n){
return n.leftChild() == NULL && n.rightChild() == NULL;
}

//private helper function
void _sumLeafs(const Node* root, int& sum = 0){
if(isLeaf(root)) sum += root.getValue();
else{
_sumLeafs(root.leftChild(),sum); //sum the left side of the tree
_sumLeafs(root.rightChild(),sum); //sum the right side of the tree
}
}``````

The only way you will understand this, is if you trace out the call. Otherwise it
will be hard to explain. The code above might be wrong, so I make no promise, but
it should be good.

oh i got it! thanks!

oh i got it! thanks!

Are you sure? I feel like I made a mistake, and just given you a code you can copy/paste?

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.