Points goes to best answer. The time delay of a long distance call can be determ
ID: 3546664 • Letter: P
Question
Points goes to best answer.
The time delay of a long distance call can be determined by multiplying a small fixed constant to the number of communication links on the telephone network between the caller and callee. Suppose the telephone network of RT&T; is a tree. The engineers of RT&T; want to compute the maximum possible time delay that may be experienced in a long-distance call. Given a tree T with N nodes, the diameter of T is the length of a longest path between two nodes of T. Give an efficient algorithm for computing the diameter of T.Explanation / Answer
#include <stdio.h>
#include <stdlib.h>
struct node
{
int data;
struct node* left;
struct node* right;
};
/* function to create a new node of tree and returns pointer */
struct node* newNode(int data);
/* returns max of two integers */
int max(int a, int b);
/* function to Compute height of a tree. */
int height(struct node* node);
/* Function to get diameter of a binary tree */
int diameter(struct node *root, int* height)
{
/* lh --> Height of left subtree
rh --> Height of right subtree */
int lh = 0, rh = 0;
/* ldiameter --> diameter of left subtree
rdiameter --> Diameter of right subtree */
int ldiameter = 0, rdiameter = 0;
if(root == NULL)
{
*height = 0;
return 0; /* diameter is also 0 */
}
/* Get the heights of left and right subtrees in lh and rh
And store the returned values in ldiameter and ldiameter */
ldiameter = diameter(root->left, &lh);
rdiameter = diameter(root->right, &rh);
/* Height of current node is max of heights of left and
right subtrees plus 1*/
*height = max(lh, rh) + 1;
return max(lh + rh + 1, max(ldiameter, rdiameter));
}
/* The function Compute the "height" of a tree. Height is the
number f nodes along the longest path from the root node
down to the farthest leaf node.*/
int height(struct node* node){
/* base case tree is empty */
if(node == NULL)
return 0;
/* If tree is not empty then height = 1 + max of left
height and right heights */
return 1 + max(height(node->left), height(node->right));
}
/* Helper function that allocates a new node with the
given data and NULL left and right pointers. */
struct node* newNode(int data){
struct node* node = (struct node*)
malloc(sizeof(struct node));
node->data = data;
node->left = NULL;
node->right = NULL;
return(node);
}
/* returns maximum of two integers */
int max(int a, int b){
return (a >= b)? a: b;
}
/* Driver program to test above functions*/
int main()
{
struct node *root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);
int height = 0;
printf("Diameter of the given binary tree is %d ", diameter(root,&height));
getchar();
return 0;
}