Calculating the height of a binary tree

Question

I need help with the theory on calculating the height of a binary tree, typically the notation.

I have read the following article:

Calculating height of a binary tree

And one of the posts gives the following notation:

height(node) = max(height(node.L), height(node.R)) + 1

Let's assume I have the following binary tree:

     10
   /   \  
  5    30
 / \   /  \ 
4  8  28  42

Do I therefore calculate the max value on the left node (8) and the max node on the right (42) and then add 1? I don't quite understand how this notation works in order to calculate the height of the tree.

Answer 1

I'll try to explain how this recursive algorithm works:

height(10) = max(height(5), height(30)) + 1

height(30) = max(height(28), height(42)) + 1
height(42) = 0 (no children)
height(28) = 0 (no children)

height(5) =  max(height(4), height(8)) + 1
height(4) = 0 (no children)
height(8) = 0 (no children)

So if you want to calculate height(10), you have to expand the recursion down, and than substitute results backwards.

height(5)  = max(0, 0) + 1
height(30) = max(0, 0) + 1
height(10) = max(1, 1) + 1
height(10) = 2

EDIT:

As noted in comments:
height of binary tree = number of layers - 1
Therefore there should be assumption that height of empty node is equal to -1 i.e:

height(empty) = -1 

or

height(null) = -1 

this way

height(42) = max(height(null), height(null)) + 1
height(42) = max(-1, -1) + 1
height(42) = -1 + 1
height(42) = 0

I have corrected calculation above.