Method to count edges from root to furthest node in tree

Question

I am trying to write a method that will calculate the largest amount of edges taken to get from the root to the furthest node.

public static int depth(Tree t) {
    if(t == null) return 0;
    else return 1 + Math.max(depth(t.left), depth(t.right));
}

The method should show an answer of 3 for this tree, however it is currently giving a result of 4 as it is counting the nodes rather than the edges, therefore counting the initial root. How would I go about changing this to give the correct result?

Answer 1

Wrap your recursive method in an outer method that tests for a null tree and subtracts one from the result:

public static int depth(Tree t) {
  return (t == null) ? 0 : calculateDepth(t) - 1;
}

private static int calculateDepth(Tree t) {
  if (t == null)
    return 0;
  else
    return 1 + Math.max(calculateDepth(t.left), calculateDepth(t.right));
}