Height or Depth of Binary Tree

[spskhokhar]

hi,

i'm in interested to know what will be the height of binary tree with say 5 nodes (consider it balanced)

is it 2 or 3?

                  9
                /   \
               5    13    
             /  \   
            3    7

and for following tree also:

                   2
                /    \
               7      5
             /   \     \
            2     6     9    
                /   \  /
               5    11 4

is it 3 or 4?

i'm asking because, not able to find correct/one answer.

the algo i find is:

depth(struct tree*t)
{
    if ( t == NULL) return 0;
    return max( depth(tree->left), depth(tree->right) ) + 1;
}

according to it, ans for second will be 4
But as per image on wikipedia (url: http://en.wikipedia.org/wiki/Binary_tree )
the ans is 3

[keskiverto]

Wikipedia on trees: "The root node has depth zero."

[spskhokhar]

so, what will be the answer?

Is the algo mentioned in my early post is correct or not, to find the depth?

[Smac89]

http://leetcode.com/2010/04/maximum-height-of-binary-tree.html

[spskhokhar]

ok, height (or depth) of empty (or null) binary tree is ZERO

and considered there is only one node in tree, then height of root node is zero but height of tree is one

that means, the height of following tree is 4 and not 3 (its something not right on wikipedia)

                   2
                /    \
               7      5
             /   \     \
            2     6     9    
                /   \  /
               5    11 4

depth of above tree is 4

Kindly give me direct answer (had already visited the mentioned link, thanks for that Smac89)

[keskiverto]

There seems to be two different conventions:

1. Height of one (root) node tree is 1. Most of the recursive algorithms that a websearch returns, do use this.

2. Height of one (root) node tree is 0. Wikipedia (and its sources) do use this. Height of the tree is the height of the root node and the height of a node is the number of edges on longest simple path from it to a leaf. While the definition is explicit, there are practically no code examples.

[spskhokhar]

thanks keskiverto.