Problem

Submissions

Hints & solutions

Discuss

Diameter Of Binary Tree

Moderate

0/80

1 upvote

Asked in companies

Problem statement

For a given Binary of type integer, find and return the ‘Diameter’.

Diameter of a Tree

The diameter of a tree can be defined as the maximum distance between two leaf nodes.
Here, the distance is measured in terms of the total number of nodes present along the path of the two leaf nodes, including both the leaves.

Example:

The maximum distance can be seen between the leaf nodes 8 and 9. 
The distance is 9 as there are a total of nine nodes along the longest path from 8 to 9(inclusive of both). Hence the diameter according to the definition will be 9.

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first and the only line of input will contain the node data, all separated by a single space. Since -1 is used as an indication whether the left or right node data exist for root, it will not be a part of the node data.

Output Format:

The only line of output prints an integer, representing the diameter of the tree.

Note:

You are not required to print anything explicitly. It has already been taken care of.

Constraints:

1 <= N <= 10^5
Where N is the total number of nodes in the binary tree.

Time Limit: 1 sec

Sample Input 1:

2 4 5 6 -1 -1 7 20 30 80 90 -1 -1 8 -1 -1 9 -1 -1 -1 -1 -1 -1

Sample Output 1:

Sample Input 2:

1 2 3 4 5 6 7 -1 -1 -1 -1 -1 -1 -1 -1

Sample Output 2:

Diameter Of Binary Tree

Nilesh Sunil Kudale

Interview problems

Easy Feasy Solution in C++

pair<int,int> diameterOfBinaryTreeFast(BinaryTreeNode<int>* root){

if(root==NULL){

pair<int,int>p=make_pair(0,0);

return p;

}

pair<int,int> left=diameterOfBinaryTreeFast(root->left);

pair<int,int> right=diameterOfBinaryTreeFast(root->right);

int op1=left.first;

int op2=right.first;

int op3=left.second+right.second+1;

pair<int,int>ans;

ans.first=max(op1,max(op2,op3));

ans.second=max(left.second,right.second)+1;

return ans;

}

int diameterOfBinaryTree(BinaryTreeNode<int>* root) {

// Write your code here

return diameterOfBinaryTreeFast(root).first;

}

22 views

0 replies

0 upvotes

Suraj Kumar Yadav

Interview problems

C++|| easy to understand

int height(BinaryTreeNode<int>* root)

{

if(root==nullptr)

{

return 0;

}

int left=height(root->left);

int right=height(root->right);

int ans = max(left,right) + 1;

return ans;

}

int diameterOfBinaryTree(BinaryTreeNode<int>* root) {

if(root == nullptr)

{

return 0;

}

int len1 = diameterOfBinaryTree(root->left);

int len2 = diameterOfBinaryTree(root->right);

int len3 = height(root->left) + height(root->right) + 1;

int ans = max(len1,max(len2,len3));

return ans;

}

34 views

0 replies

0 upvotes

Umang

Interview problems

Java Solution:

public class Solution {

static int diameterOfBinaryTreeUtil(BinaryTreeNode<Integer> root, int[] max){

if(root == null) return 0;

int left = diameterOfBinaryTreeUtil(root.left, max);

int right = diameterOfBinaryTreeUtil(root.right, max);

max[0] = Math.max(max[0], left + right + 1);

return 1 + Math.max(left, right);

}

public static int diameterOfBinaryTree(BinaryTreeNode<Integer> root){

//Your code goes here

int[] res = {-(int)1e9};

diameterOfBinaryTreeUtil(root, res);

return res[0];

}

24 views

0 replies

0 upvotes

Irfan Gouri

Interview problems

Simplest C++ Solution | Recursion.

/**********************************************************

Following is the Binary Tree Node class structure

template <typename T>

class BinaryTreeNode {

public :

T data;

BinaryTreeNode<T> *left;

BinaryTreeNode<T> *right;

BinaryTreeNode(T data) {

this -> data = data;

left = NULL;

right = NULL;

}

};

***********************************************************/

int height(BinaryTreeNode<int> *root, int cnt) {

if(root == NULL) return cnt;

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

}

void solve(BinaryTreeNode<int> *root, int &ans) {

int left = height(root->left, 0);

int right = height(root->right, 0);

if(ans < left + right) ans = left + right;

if(root->left) solve(root->left, ans);

if(root->right) solve(root->right, ans);

}

int diameterOfBinaryTree(BinaryTreeNode<int>* root) {

int ans = 0;

solve(root, ans);

return ans+1;

}

49 views

0 replies

0 upvotes

Aditya Chhawal

Interview problems

Diameter Of Binary Tree-via recursion

int height(BinaryTreeNode<int>* node,int &diameter){ if(!node){ return 0; } int lh=height(node->left,diameter); int rh=height(node->right,diameter); diameter =max(diameter,lh+rh); return 1+max(lh,rh); } int diameterOfBinaryTree(BinaryTreeNode<int>* root) { int diameter=0; height(root,diameter); return diameter+1; }

120 views

0 replies

0 upvotes

Priyanshu Negi

Interview problems

answer dekho seekho aur thank you bolo

pair<int, int>diametere( BinaryTreeNode<int>* root ){
 
    if( root == NULL){
        pair<int, int>p = make_pair(0,0);
        return p;
    }
  pair<int , int>left = diametere( root->left);  
  pair<int,  int>right = diametere( root->right);  
    
   int op1 = left.first;
   int op2 = right.first; 
   int op3 = left.second + right.second + 1; 
    
   pair<int, int>ans; 
    ans.first = max( op1, max(op2, op3) );
    ans.second = max( left.second , right.second) + 1;
    return ans;
}
int diameterOfBinaryTree(BinaryTreeNode<int>* root) {
	// Write your code here

return diametere(root).first;
}