I cannot understand why we should minus 1 in line 4. I think just returning height(root) is fine, what does minus 1 mean?
public int height() {
if(root == null)
return 0;
return height(root) - 1;
}
public int height(Node<K,V> node) {
if (node == null)
return 0;
int leftheight = height(node.left) + 1
int rightheight = height(node.right) + 1
if (leftheight > rightheight)
return leftheight;
return rightheight;
}
This minus one is necessary because the second height
function does not calculate the height, but one more than the height.
The height of a tree is defined as the number of edges on the longest path from the root to a leaf, but the second function calculates the number of nodes (or levels) on the longest path from the root to a leaf, which is always one more.
I agree that this is a strange way of doing it, as actually it makes the name of the second function wrong: it doesn't do what it says.
Moreover, the main function has a problem too, because when the root is null, the height should return -1.
It is more natural to change the base case, and make the second function really return the height of the node that is passed as argument:
public int height() {
return height(root); // Simple: if no argument was passed, the default is the root
}
public int height(Node<K,V> node) {
if (node == null)
return -1; // <-----
int leftheight = height(node.left) + 1
int rightheight = height(node.right) + 1
if (leftheight > rightheight)
return leftheight;
return rightheight;
}
It may be strange to have the value -1 there, but the reasoning is as follows:
This is a tree with height 1:
a
/ \
b c
... because the longest path from the root has one edge; it is a tree with 2 levels, and the height is one less than the number of levels.
This is a tree with height 0:
a
Here the number of levels is 1, and so the height is 0.
One step more, is an empty tree -- it doesn't even have a node, and zero levels, and so the corresponding height should be -1.