Day 11 of 30-Day LeetCode Challenge

Given a binary tree, you need to compute the length of the diameter of the tree. The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root

* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
class Solution {
int getHeight(TreeNode* root){
if(root==NULL) return 0;

return 1+max(getHeight(root->left), getHeight(root->right));

int getHeight2(TreeNode *root, int &max_diameter){
if(root==NULL) return 0;

int lh = getHeight2(root->left, max_diameter);
int rh = getHeight2(root->right, max_diameter);

max_diameter = max(max_diameter, 1+lh+rh);
return 1+max(lh, rh);

int diameterOfBinaryTree(TreeNode* root) {

// //O(n²) approach
// if(root==NULL) return 0;

// int leftDiameter = diameterOfBinaryTree(root->left);
// int myDiameter = getHeight(root->left) + getHeight(root->right);
// int rightDiameter = diameterOfBinaryTree(root->right);

// return max(leftDiameter, max(myDiameter, rightDiameter));

//O(n) approach
int max_diameter = 1;
getHeight2(root, max_diameter);
return max_diameter-1;



We never really grow up, we only learn how to act in public

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store