Thread: recursion and binary trees

Hey guys, i was wondering if anyone could explain this to me

Code:

	int maxdepth (treeptr tree){
		int leftdepth = 0;
		int rightdepth = 0;

		if (tree == NULL)
			return 0;
		else{
			leftdepth = maxdepth(tree->left);
			rightdepth = maxdepth(tree->right);
			if (leftdepth > rightdepth)
				return leftdepth +1;
			else 
				return rightdepth + 1;
		}
	}

This is supposed to calculate the maximun 'depth' of the binary tree. However, I don't see the part in which left/right depth is ever incremented. Infact, is it not just reset to 0 all the time?

Also, in the code for traversing a tree

Code:

void traverse(treeptr tree){
		traverse(tree->left);
                cout  << tree->data;
		traverse(tree->right);
	}

How does the function ever break its recursion loop? Surely it would just keep going on and on.

many thanks,

Just a quick note, i think i understand the last bit

Code:

if (leftdepth > rightdepth)
				return leftdepth +1;
			else 
				return rightdepth + 1;

Basically, if the the tree is greater on the left side then return that number + 1, (+1 due to the 'root' or 'head' of the binary tree being included) am i right in thinking this?

I still am unsure how the value leftdepth,right depth is calculated.

The traverse function you posted is indeed broken in the way you describe.

leftdepth is calculated right there where it's assigned:

Code:

leftdepth = maxdepth(tree->left);

I'll give you the same advice I gave earlier: draw a silly little tree (two nodes, maybe) and trace through the algorithm. You'll see how it works.

you know, i think you're right. I think it did help. But when the does the tree == NULL?
is there a 'NULL' node at the end of each branch?

Originally Posted by rocketman50

you know, i think you're right. I think it did help. But when the does the tree == NULL?
is there a 'NULL' node at the end of each branch?

If you've built the tree in any kind of normal way, yes.

cool, thanks for the help.

Just to clarify - im being slow (its 4am ><)

The base case is tree == NULL.
So the function will start by traversing down the left most branch until it reaches the base case. From there, it will sort of work backwards to find the maxdepth of the leftside. It will then repeat for the right side, compare which is larger and return that side.

Originally Posted by rocketman50

cool, thanks for the help.

Just to clarify - im being slow (its 4am ><)

The base case is tree == NULL.
So the function will start by traversing down the left most branch until it reaches the base case. From there, it will sort of work backwards to find the maxdepth of the leftside. It will then repeat for the right side, compare which is larger and return that side.

Well, that side plus one, but yes.

great, I really appreciate the help. I have an exam tomorrow. I should really be asleep right about now...i really need to get my head around recursion first!