In this guide, you will get 543. Diameter of Binary Tree LeetCode Solution with the best time and space complexity. The solution to Diameter of Binary Tree problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
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.
Example 1:
Input: root = [1,2,3,4,5]
Output: 3
Explanation: 3 is the length of the path [4,2,1,3] or [5,2,1,3].
Example 2:
Input: root = [1,2]
Output: 1
Constraints:
The number of nodes in the tree is in the range [1, 104].
-100 <= Node.val <= 100
Complexity Analysis
Time Complexity: O(n)
Space Complexity: O(h)
543. Diameter of Binary Tree LeetCode Solution in C++
class Solution {
public:
int diameterOfBinaryTree(TreeNode* root) {
int ans = 0;
maxDepth(root, ans);
return ans;
}
private:
int maxDepth(TreeNode* root, int& ans) {
if (root == nullptr)
return 0;
const int l = maxDepth(root->left, ans);
const int r = maxDepth(root->right, ans);
ans = max(ans, l + r);
return 1 + max(l, r);
}
}; /* code provided by PROGIEZ */
543. Diameter of Binary Tree LeetCode Solution in Java
class Solution {
public int diameterOfBinaryTree(TreeNode root) {
maxDepth(root);
return ans;
}
private int ans = 0;
int maxDepth(TreeNode root) {
if (root == null)
return 0;
final int l = maxDepth(root.left);
final int r = maxDepth(root.right);
ans = Math.max(ans, l + r);
return 1 + Math.max(l, r);
}
} // code provided by PROGIEZ
543. Diameter of Binary Tree LeetCode Solution in Python
class Solution:
def diameterOfBinaryTree(self, root: TreeNode | None) -> int:
ans = 0
def maxDepth(root: TreeNode | None) -> int:
nonlocal ans
if not root:
return 0
l = maxDepth(root.left)
r = maxDepth(root.right)
ans = max(ans, l + r)
return 1 + max(l, r)
maxDepth(root)
return ans # code by PROGIEZ
