Find diameter of a binary tree - O(n2) time complexity

// Its basically the longest path between 2 nodes in a tree
// This solution give O(n2) time complexity

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

struct node 
{
    int data;
    struct node * left;
    struct node * right;
};

int max(int a, int b)
{
    return (a > b)? a: b;
}

// Height of a tree
int height(struct node * root)
{
    int leftdepth  = 0;
    int rightdepth = 0;
    
    if(root == NULL)    return 0;
    
    leftdepth  = height(root->left);
    rightdepth = height(root->right);
    
    return (leftdepth>rightdepth) ? (leftdepth+1): (rightdepth+1);
}

// Diameter of a tree
int diameter(struct node * tree)
{
    if(tree == NULL)    return 0;
    
    int lheight = height(tree->left);
    int rheight = height(tree->right);
    
    int ldiameter = diameter(tree->left);
    int rdiameter = diameter(tree->right);
    
    return max(lheight+rheight+1, max(ldiameter, rdiameter));
}

struct node* newNode(int value)
{
    struct node* node = (struct node *)malloc(sizeof(struct node));

    node->data   = value;
    node->left   = NULL;
    node->right  = NULL;

    return node;
}

int main(void)
{
    struct node *root = newNode(1);
    root->left        = newNode(2);
    root->right       = newNode(3);
    root->left->left  = newNode(2);
    root->left->right = newNode(3);
    
    printf("Height of tree is %d \n", height(root));
    
    return 0;
}


// There is another solution which gives O(n) time complexity

// Check the following link for O(n) time complexity solution

http://justalgorithmlogic.blogspot.com/2015/05/find-diameter-of-binary-tree-on-time.html