Wednesday, 11 September 2013

What's wrong with the most cited binary tree depth calculation algorithm?

What's wrong with the most cited binary tree depth calculation algorithm?

There is something that eats into my brain: how can the depth of the
following tree
b
/ \
a c
be 3, after the most cited algorithm (here in Java):
int depth(Node n)
{
if(n == null)
{
return 0;
}
int lDepth = depth(n.left);
int rDepth = depth(n.right);
return 1 + ((lDepth > rDepth) ? lDepth : rDepth);
}
when the depth of a tree with only a single (root) node is 0 according to
Wikipedia and many of my other sources where the depth is defined as
length of path to the deepest node? Obviously, the length of the path to
the deepest node for a tree with only a single node is 0, while the above
algorithm will never yield anything smaller than 1.
Is the depth of a tree with a single root node 0 or is it 1? If it is 0
then the algorithm above is faulty, because it will yield 1.
I never thought such a trivial thing would turn inside out on me.

No comments:

Post a Comment