Finding the Height of the Node

[jhykima]

I got the following code from a youtube video. I am trying to understand this code, and I'm having a difficult time. And I'm not sure what the max function would be in this code. What happens if the left and the right is equivalent? How do we handle that situation? I'm assuming you return the value of either one in the case that left is equal to right?

int findHeight (node *root)
{
	if (root == NULL)
	{
		return -1; 
	}

	int left = findHeight (root->left); 
	int right = findHeight (root->right); 

	return 1 + max (left, right); 
}

[MiiNiPaa]

I'm not sure what the max function would be in this code.

It is the standard function.

What happens if the left and the right is equivalent?

We return their value. What is the maxumum of 2 and 2?

[jhykima]

@MiiNiPaa

I feel so dumb. Thank you so much for your response.

Also, every time there are two recursive function calls in a function, my brain twists abnormally and I cannot seem to wrap it around the concept (e.g., Tower of Hanobi). Any suggestions on how to understand this?

I've already tried to draw some diagrams and copied the function as many times it is called to try to understand it but without avail.

GAHHHHHH!!!

Best, Jae Kim

[MiiNiPaa]

It is helpful to look into common and terminal cases:
common case: height of node is maximum of heights of left and right childrens + 1;

                     ▓  ← Root height
                      ▓ ← Right child height
                      ▓
Left child height → ▓ ▓ 
                    ▓ ▓
                    ▓ ▓

Terminal case: height of nonexisting node is -1, therefore height of node without children is 0.

So you just ask your childrens about their heights, children asks another childrens and so on until you reach leaf node and then recursion is going back: children report to their parents, parents add 1 to highest number and report to their parents etc.

Towe of hanoi is simple too:
terminal case: to move one disc, we just move it. That is all.
common case: we move all discs but the larger one to the extra rod, move largest disc on target rod, move remaining discs on target rod. Function is going to delegate further and further moving of smaller stacks until it asks to move a single disc (terminal case) then will unwind back: 2 disc stack is able to complete, its completition helps 3disc stack, etc.

It is similar to mathematical induction: there you too formulates common case, prove that terminal case is true and by domino principle common case is true too.