Height of a binary tree

Question

Consider the following code:

public int heightOfBinaryTree(Node node)
{
    if (node == null)
    {
        return 0;
    }
    else
    {
        return 1 +
        Math.max(heightOfBinaryTree(node.left),
            heightOfBinaryTree(node.right));
    }
}

I want to know the logical reasoning behind this code. How did people come up with it? Does some have an inductive proof?

Moreover, I thought of just doing a BFS with the root of the binary tree as the argument to get the height of the binary tree. Is the previous approach better than mine?Why?

Solution 1

if (node == null)
{
    return 0;
}

The children of leaf nodes are null. Therefore this is saying that once we've gone past the leaves, there are no further nodes.

If we are not past the leaf nodes, we have to calculate the height and this code does so recursively.

return 1 +

The current node adds a height of 1 to the height of the subtree currently being calculated.

    Math.max(heightOfBinaryTree(node.left),
        heightOfBinaryTree(node.right));

We recursively calculate the height of the left subtree (node.left) and right subtree (node.right). Since we're calculating the maximum depth, we take the maximum of these two depths.

I've shown above that the recursive function is correct. So calling the function on the parent node will calculate the depth of the entire tree.

Here's a graphical representation of the height of a tree from this document. h is the height of the tree, hl and hr are the heights of the left and right subtrees respectively.

Moreover, I thought of just doing a BFS with the root of the binary tree as the argument to get the height of the binary tree. Is the previous approach better than mine?Why?

The code you provided is a form of DFS. Since you have to process all nodes to find the height of the tree, there will be no runtime difference between DFS and BFS, although BFS will use O(N) memory while DFS will use O(logN) memory. BFS is also slightly more complex to code, since it requires a queue while DFS makes use of the "built-in" recursive stack.

Solution 2

The logic behind that code is:

since a node will have two children, the height of the Tree will be maximum of the heights of tree whose roots are the left child and right child, and of course +1 for the walk to the children.

As you can see, the description above is recursive and so is the code.

BFS should also do, but it would be an overkill as both implementation and space/time complexity.

There is a say, recursive functions though hard to understand, but are very elegant to implement.

Solution 3

The height of a tree is the length of longest downward path from it's root. This function is a recursive way to count the levels of a binary tree. It just increments counters as it descends the tree, returning the maximum counter (the counter on the lowest node).

I hope I have helped.

Comments

[Dejell]

Why is there else after the if? I thought that return will quit the function!

[Ben Kremer]

The else block is used simply for readability purposes in this scenario. You could have only the if block with return 0; and return the recursive function underneath it. The result is the same.

[sorabh]

@marcog I came across this very old post. Just curious if node is NULL value should be 0 or -1 ?

[sorabh]

I think so I got the answer - it will depend on whether we are considering height as number of nodes or number of edges.

[Sidath Asiri]

Isn't it required to modify it like this to avoid add unnecessary 1 at leaves............ if (t == null) { return 0; } else if (t.left == null && t.right == null) { return 0; } else { return 1 + Math.max(height(t.left), height(t.right)); }