Diameter of a Tree

Question

I was doing the sample test of interviewstreet.com. It comes with 3 questions and these are publicly available. So I see no harm discussing these questions.

My question is

Question 2 / 3 (Diameter of Tree) The diameter of a tree is the number of nodes on the longest path between two leaves in the tree. The diagram below shows a tree with diameter nine, the leaves that form the ends of a longest path are shaded (note that there is more than one path in each tree of length nine, but no path longer than nine nodes).

In particular, note that the diameter of a tree T is the largest of the following quantities:

• the diameter of T's left subtree
• the diameter of T's right subtree
• the longest path between leaves that goes through the root of T

Given the root node of the tree, return the diameter of the tree

Sample Test Cases:

Input #00: Consider the tree:

Output #00: 5

Explanation: The diameter of the tree is 5

My Answer in C++ is:

int traverse(node* r) {
    if (r == NULL) { return 0;}
    return max(traverse(r->left),traverse(r->right))+1;
}
int diameterOfTree(node * r) {
    return traverse(r->left)+traverse(r->right)+1;
}

There are 14 test cases, however 2 of them are wrong with this answer. I could not find what cases am I missing. I don't really think it is a base case, so what am I missing?

Answer 1

You may have the diameter of a tree not passing through its root. imagine this tree:

             / E - F - G - H - I
A - B - C - D  
             \ J - K - L - M 

(Sorry for the ugly ASCII art). Here the diameter is I-H-G-F-E-D-J-K-L-M.