# Diameter of a Binary Tree

Written By -

## Problem

Calculate the height of the given binary tree.

## Brute force approach

We can traverse each and calculate the diameter for each node.

max(lh + rh + 1, max(left_dia, right_dia)); .

TC – O(N2)

## Better Approach

We can traverse each node one by one and keep its height and diameter(if diameter passes through that node) in a variable, and we will keep updating the global diameter of the tree.

``````#include<bits/stdc++.h>
using namespace std;

struct Node{
int data;
Node* left;
Node* right;
Node(int data){
this->data = data;
left = right = NULL;
}
};

int diameterOfTree(Node* root, int &result){
if(!root) return 0;

int lh = diameterOfTree(root->left, result);
int rh = diameterOfTree(root->right, result);

int heightOfCurrNode = max(lh, rh) + 1;
int currDiameter = lh + rh;
result = max(currDiameter, result); // this contains the diameter
return heightOfCurrNode;
}

int main() {
/*
1
/    \
2      3
/   \   /  \
4     5 6    7
*/
struct Node* root = new Node(1);
root->left = new Node(2);
root->left->left = new Node(4);
root->left->right = new Node(5);
root->left->right->left = new Node(15);
root->right = new Node(3);
root->right->left = new Node(6);
root->right->right = new Node(7);
int result = INT_MIN;
diameterOfTree(root, result);
cout<<result;
return 0;
}``````

TC – O(N)

Related Posts:

Online Compilers