Diameter of a Binary Tree in O ( n ) [ A new method ] | Simple C ++ program to find diameter of a binary tree . ; Tree node structure used in the program ; Function to find height of a tree ; update the answer , because diameter of a tree is nothing but maximum value of ( left_height + right_height + 1 ) for each node ; Computes the diameter of binary tree with given root . ; This will store the final answer ; A utility function to create a new Binary Tree Node ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; struct Node { int data ; Node * left , * right ; } ; int height ( Node * root , int & ans ) { if ( root == NULL ) return 0 ; int left_height = height ( root -> left , ans ) ; int right_height = height ( root -> right , ans ) ; ans = max ( ans , 1 + left_height + right_height ) ; return 1 + max ( left_height , right_height ) ; } int diameter ( Node * root ) { if ( root == NULL ) return 0 ; int ans = INT_MIN ; height ( root , ans ) ; return ans ; } struct Node * newNode ( int data ) { struct Node * node = new Node ; node -> data = data ; node -> left = node -> right = NULL ; return ( node ) ; } int main ( ) { struct Node * root = newNode ( 1 ) ; root -> left = newNode ( 2 ) ; root -> right = newNode ( 3 ) ; root -> left -> left = newNode ( 4 ) ; root -> left -> right = newNode ( 5 ) ; printf ( " Diameter ▁ is ▁ % d STRNEWLINE " , diameter ( root ) ) ; return 0 ; }