As a recursive function, this computes the height of each child node, using that result to compute the height of the current node by adding + 1
to it. The height of any node is always the maximum height of the two children + 1. A single-node case is probably the easiest to understand, since it has a height of zero (0).
A
Here the call stack looks like this:
height(A) =
max(height(A->left), height(A->right)) + 1
Since both left and right are null, both return (-1)
, and therefore this reduces to
height(A) = max (-1, -1) + 1;
height(A) = -1 + 1;
height(A) = 0
A slightly more complicated version
A
B C
D E
The recursive calls we care about are:
height(A) =
max(height(B), height(C)) + 1
height(B) =
max(height(D), height(E)) + 1
The single nodes D, E, and C we already know from our first example have a height of zero (they have no children). therefore all of the above reduces to
height(A) = max( (max(0, 0) + 1), 0) + 1
height(A) = max(1, 0) + 1
height(A) = 1 + 1
height(A) = 2
I hope that makes at least a dent in the learning curve for you. Draw them out on paper with some sample trees to understand better if you still have doubts.