CODEWITHSUNDEEP
c++algorithmtree
Invictus
Invictus

Reputation: 4328

Finding Diameter of a Tree

I have written code for finding the diameter of binary tree. But I am unable to figure out where is it going wrong . The two functions that I have written and their definition are as follows :- 

    int btree::diameteroftree(node* leaf)
    { 
     if (leaf==NULL) 
     return 0;

     int lheight = hieghtoftree(leaf->left);
     int rheight = hieghtoftree(leaf->right);

     int ldiameter = diameteroftree(leaf->left);
     int rdiameter = diameteroftree(leaf->right);

     return max(lheight + rheight + 1,max(ldiameter,rdiameter));
   }


   int btree::hieghtoftree(node* leaf)
   {
    int left=0,right=0;
    if(leaf==NULL)
    return -1;
    else
    {
     left=hieghtoftree(leaf->left);
     right=hieghtoftree(leaf->right);
     if(left > right)
     return left +1;
     else
     return right+1;   
    }
   }

I am unable to figure out where am I going wrong here . Can someone let me know ...

Upvotes: 0

Views: 2487

Answers (3)

Nico Schertler
Nico Schertler

Reputation: 32587

You want to return the number of nodes on the longest path. Therefore, the problem in your algorithm is this line:

return max(lheight + rheight + 1,max(ldiameter,rdiameter));

where 

rootDiameter = lheight + rheight + 1

is the length of the path from the deepest node of the left tree to the deepest node of the right tree. However, this calculation is not correct. A single node returns a height of 0, so it will not be counted. You have two options:

  1. Change hieghtoftree to return the number of nodes on the deepest path and not the number of "hops"
  2. Address this problem in your summation

.

return max(lheight + rheight + 3,max(ldiameter,rdiameter));

Upvotes: 1

goodwind89
goodwind89

Reputation: 21

Consider a 3-node tree with root R and 2 leaves L1, L2. Then heightoftree(L1) == heightoftree(L2) == -1. Diameteroftree(R) would therefore be (-1)+(-1)+1 = -1 ?!?

I suggest return -1; --> return 0; and return max(lheight + rheight + 1,max(ldiameter,rdiameter)); --> return max(lheight + rheight + 2,max(ldiameter,rdiameter));

The result would be the number of edges on the path. If you count the number of nodes, then add one or subtract one from the final result according to your need.

Upvotes: 0

Fred Foo
Fred Foo

Reputation: 363487

In a directed, rooted tree, there is always at most one path between any pair of nodes and the longest path to any node always starts at the root. It follows that the diameter is simply the height of the entire tree height(root), which can be computed with the recursion

height(leaf) = 0
height(node) = max(height(node.left), height(node.right)) + 1

EDIT: the page you link to in the comment describes the diameter of an undirected tree. You need a different tree representation, e.g. an adjacency matrix.

Upvotes: 0

Related Questions