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 by kunkunlol: n/a

8 Years
Discussion Span
Last Post by firstPerson

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 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 topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.