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;
}

Edited 6 Years Ago by kunkunlol: n/a

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.

Edited 6 Years Ago by firstPerson: n/a

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?

This article has been dead for over six months. Start a new discussion instead.