TutorialStudyMite
Diameter of a Binary Tree
Sstudymite1 min read
Beginner friendly
Track completion, mastery, and revision.
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 main() {
/*
1
/
2 3
/ \ /
4 5 6 7
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)
Finished reading?