Find center of a tree


#include<stdio.h>
#include<math.h>
#include<stdlib.h>

struct node
{
    int data;
    struct node *left;
    struct node *right;
    int height;
}*root=NULL;

void insert(struct node **root,int num){
    struct node *temp=(struct node *)malloc(sizeof(struct node));
    temp->left=NULL;
    temp->right=NULL;
    temp->height=0;
    temp->data=num;
    if((*root)==NULL){
        (*root)=temp;
        return ;
    }
    if(num>(*root)->data)
        insert(&((*root)->right),num);
    else
        insert(&((*root)->left),num);
}
int max(int a,int b){
    return a>b?a:b;
}
int height(struct node *root){
    if(root==NULL)
        return 0;
    root->height=max(height(root->left),height(root->right));
    return 1+root->height;
}
int min(int a,int b)
{
    return a<b?a:b;
}
int findcenter(struct node *root)
{
    if(root==NULL)
        return 0;
    static int center=0;
    int lh=0,rh=0;
    if(root->left)
        lh=root->left->height;
    if(root->right)
        rh=root->right->height;
    int larger=max(lh,rh);
    int smaller=min(lh,rh);
    center=1+max(center,smaller);

    if(abs(center-1-larger)<=1)
        return root->data;
    else if(larger==rh)
        return findcenter(root->right);
    else
        return findcenter(root->left);
}

void display(struct node *root)
{
    if(!root)
        return;
    display(root->left);
    printf(" %d %d\n",root->data,root->height);
    display(root->right);
}

int main()
{
    insert(&root,6);
    insert(&root,5);
    insert(&root,3);
    insert(&root,1);
    insert(&root,9);
    insert(&root,7);
    insert(&root,8);
    height(root);
    display(root);
    printf("Congrats ,so you got the center %d\n",findcenter(root));
    return 0;
}

Comments

  1. Hey! What do I change and how in the code to be able to solve the problem: http://www.quora.com/How-do-I-find-the-node-that-has-the-least-maximum-distance-to-all-the-other-nodes-in-a-graph

    ReplyDelete

Post a Comment

Popular Posts