diameter_of_tree.cpp

/**
 * @author ranaaditya
 */

#include<bits/stdc++.h>

using namespace std;

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

/**
 * This is optimized form for calculating the diameter of a binary tree
 * 
 * 
 */
int diameter_of_tree_optimized(Node* root, int& height) {

    int lh = 0, rh = 0;
    int ld = 0, rd = 0;

    if(root == NULL) {
        height = 0;
        return 0;
    }

    ld = diameter_of_tree_optimized(root->left, lh);
    rd = diameter_of_tree_optimized(root->right, rh);

    height = max(lh, rh) + 1;

    return max(lh + rh + 1, max(ld, rd));

}

// test this function here
int main() {

    // TODO(make a tree and test above function here)
    // diameter_of_tree_optimized(root, h);
    return 0;
}