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?
Answer
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.