# Diameter of Binary Tree

EASY

Given a binary tree, you need to compute the length of the diameter of the tree. The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root.

Example:
Given a binary tree

```          1
/ \
2   3
/ \
4   5
```

Return 3, which is the length of the path `[4 -> 2 -> 1 -> 3]` or `[5 -> 2 -> 1 -> 3]`.

Note: The length of path between two nodes is represented by the number of edges between them.

``````/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode() {}
*     TreeNode(int val) { this.val = val; }
*     TreeNode(int val, TreeNode left, TreeNode right) {
*         this.val = val;
*         this.left = left;
*         this.right = right;
*     }
* }
*/``````
```class Solution {

int max_diameter = 0;

public int diameterOfBinaryTree(TreeNode root) {
if(root == null){
return 0;
}
calculateMaximumDiameter(root);
return max_diameter;
}

private int calculateMaximumDiameter(TreeNode node){
if(node == null){
return 0;
}
int left_diameter = calculateMaximumDiameter(node.left);
int right_diameter = calculateMaximumDiameter(node.right);
int current_diameter = (left_diameter + right_diameter);
max_diameter = Math.max(max_diameter, current_diameter);
return Math.max(left_diameter, right_diameter) + 1;
}
}
```

The recursion tree will look like as following

``````                1 (3)
/        \
2        3
/    \        /   \
4   5      
/  \    /  \
     ``````

Complexity Analysis

• Time Complexity: `O(N)`. We visit every node once.
• Space Complexity: `O(N)`, the size of our implicit call stack during our depth-first search.

Categories: Binary Tree