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;
		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();
    _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.