Diameter of a Binary Tree

Written by

studymite

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-&gt;left, result);
int rh = diameterOfTree(root-&gt;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)