data-structuresred-black-tree

What does minus 1 means in the method about calculating height of red-black tree?


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;
}


Solution

  • 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.

    See also What is the definition for the height of a tree?.