🎨Now live: Try our Free AI Image Generation Feature

Description
The diameter of a binary tree is defined as the length of the longest path between any two nodes in the tree. This path may or may not pass through the root. The goal is to compute the diameter of a given binary tree.
Intuition
The diameter of a binary tree can be determined by finding the longest path that goes through each node and keeping track of the maximum of these paths. For each node, this longest path can be calculated by the sum of the heights of its left and right subtrees.
Approach
- Initialize a variable
maxDiameter
to keep track of the maximum diameter encountered. - Define a recursive function
dfs
that returns the height of a node. - In the
dfs
function: - If the node isnull
, return 0. - Recursively calldfs
for the left and right children to get their heights. - UpdatemaxDiameter
with the maximum value of the sum of the left and right heights. - Return the maximum height of the left or right subtree plus one (to account for the current node). - Call the
dfs
function with the root node. - Return the value of
maxDiameter
.
Complexity
Time Complexity:
O(n), where n is the number of nodes in the tree. Each node is visited once.
Space Complexity:
O(h), where h is the height of the tree. This space is used by the recursion stack.
Code
C++
class Solution {
public:
int diameterOfBinaryTree(TreeNode* root) {
int maxDiameter = 0;
std::function dfs = [&](TreeNode* node) {
if (!node) return 0;
int left = dfs(node->left);
int right = dfs(node->right);
maxDiameter = std::max(maxDiameter, left + right);
return std::max(left, right) + 1;
};
dfs(root);
return maxDiameter;
}
};
Python
class Solution:
def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
self.max_diameter = 0
def dfs(node):
if not node:
return 0
left_height = dfs(node.left)
right_height = dfs(node.right)
# Update the diameter if the path through the current node is larger
self.max_diameter = max(self.max_diameter, left_height + right_height)
# Return the height of the tree
return max(left_height, right_height) + 1
dfs(root)
return self.max_diameter
Java
class Solution {
private int maxDiameter = 0;
public int diameterOfBinaryTree(TreeNode root) {
dfs(root);
return maxDiameter;
}
private int dfs(TreeNode node) {
if (node == null) return 0;
int left = dfs(node.left);
int right = dfs(node.right);
maxDiameter = Math.max(maxDiameter, left + right);
return Math.max(left, right) + 1;
}
}
JavaScript
var diameterOfBinaryTree = function(root) {
let max = 0
function dfs(node) {
if (!node) return 0
const left = dfs(node.left)
const right = dfs(node.right)
console.log(node.val, left, right)
max = Math.max(max, left + right)
return Math.max(left, right) + 1
}
dfs(root)
return max
};