Given the root of a binary tree, return the length of the diameter of the tree.
LeetCode-543: Given the root
of a binary tree, return 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
.
The length of a path between two nodes is represented by the number of edges between them.
The longest path between two nodes in a binary tree will always be between two leaf nodes as otherwise we can always increase the length of the path by moving to next child node.
To solve this problem, our algorithm will identify the node where the combined length of its longest left and right branches is the greatest. This value represents the diameter of the binary tree.
Following is a java based recursive approach to solve this problem:
private int diameter = 0;
public int diameterOfBinaryTree(TreeNode root) {
calc(root);
return diameter;
}
private int calc(TreeNode root){
if(null == root){
return 0;
}
int left = calc(root.left);
int right = calc(root.right);
diameter = Math.max(diameter, left + right);
// return height of the current node
return Math.max(left, right) + 1;
}
The diameter of the binary tree is the sum of the heights of the left and right subtrees of the current node. This does not include the current node itself as the diameter is represented by the number of edges between two nodes.
The time complexity for this approach is n
is the number of nodes in the binary tree. This is because we visit each node exactly once.
The space complexity is n
in case of a skewed binary tree. If the binary tree is balanced, the space complexity will be
Be notified of new posts. Subscribe to the RSS feed.