CODEWITHSUNDEEP
c++algorithmtree
Sarp Kaya
Sarp Kaya

Reputation: 3784

Diameter of a Tree

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).

tree

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

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

Sample Test Cases:

Input #00: Consider the tree:

tree2

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?

Upvotes: 6

Views: 3127

Answers (1)

Ivaylo Strandjev
Ivaylo Strandjev

Reputation: 70929

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.

Upvotes: 4

Related Questions