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 the path between two nodes is represented by the number of edges between them.
Solution
It’s clear that we need to find the length of the longest path between two nodes in a tree. So here those nodes are either 4 and 3 or 5 and 3. Both 5 and 5 are the leaf nodes of the right subtree and 3 is the leaf node of the left subtree. The depth of the tree is the max length from root to leaf. It could be safely said, the max diameter will be the max depth of left subtree and right subtree at any time. For a node root of the tree, we need to do following –
- Find the depth of left child
- Find the depth of right child
- Update global variable diameter with the sum of left and right depth if it is more than depth’s current value.
- return depth of the root
Both the time and space complexity will of O(n) where n is the number of nodes in the binary tree.
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
/**
* DiameterOfBinaryTree.java
* Purpose: Find the diameter of Binary Tree
*
* @author Megha Rastogi
* @version 1.0 08/03/2020
*/
class DiameterOfBinaryTree {
// ans variable to track diameter
int ans = 0;
/**
* Find the diameter of Binary Tree
*
* @param root, TreeNode
* @return integer, diameter
*/
public int diameterOfBinaryTree(TreeNode root) {
if(root == null)
return 0;
depth(root);
return ans-1;
}
/**
* Helper method to find the diameter of a binary tree
*
* @param root, TreeNode
* @return integer, diameter
*/
public int depth(TreeNode root){
// return 0 when reaching leaf nodes
if(root == null)
return 0;
// left node depth
int left = depth(root.left);
// right node depth
int right = depth(root.right);
// update diameter with the max diameter till now
ans = Math.max(ans, left+right+1);
//return depth till this node
return Math.max(left, right)+1;
}
}
Source – leetcode
Code – DiameterOfBinaryTree.java