Problem Statement:
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.
Examples:
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
Approach
- Use DFS (Depth-First Search) to calculate the depth of each node.
- At each node:
- Calculate the left and right subtree depths.
- The diameter through that node =
leftDepth + rightDepth. - Update
maxDiameterif this is the largest so far.
- Return the maximum diameter found during the traversal.
Time Complexity:
Time Complexity = O(n)
Space Complexity:
Space Complexity = O(h) recursion stack space (h=tree height)
Dry Run
Function Call: diameterOfBinaryTree(root) where
root = TreeNode(1)
├── left: TreeNode(2)
│ ├── left: TreeNode(4)
│ └── right: TreeNode(5)
└── right: TreeNode(3)
Step 1:
→ Call findDepth(1)
Step 2:
→ Call findDepth(2)
Step 3:
→ Call findDepth(4)
Step 4:
→ Call findDepth(null) → return 0
→ Call findDepth(null) → return 0
→ Node 4 → leftDepth = 0, rightDepth = 0
→ currDiameter = 0
→ maxDiameter = max(0, 0) = 0
→ Return depth = 1
Step 5:
→ Back to Node 2
→ leftDepth = 1
→ Call findDepth(5)
Step 6:
→ Call findDepth(null) → return 0
→ Call findDepth(null) → return 0
→ Node 5 → leftDepth = 0, rightDepth = 0
→ currDiameter = 0
→ maxDiameter = max(0, 0) = 0
→ Return depth = 1
Step 7:
→ Back to Node 2
→ rightDepth = 1
→ Node 2 → leftDepth = 1, rightDepth = 1
→ currDiameter = 2
→ maxDiameter = max(0, 2) = 2
→ Return depth = 2
Step 8:
→ Back to Node 1
→ leftDepth = 2
→ Call findDepth(3)
Step 9:
→ Call findDepth(null) → return 0
→ Call findDepth(null) → return 0
→ Node 3 → leftDepth = 0, rightDepth = 0
→ currDiameter = 0
→ maxDiameter = max(2, 0) = 2
→ Return depth = 1
Step 10:
→ Back to Node 1
→ rightDepth = 1
→ Node 1 → leftDepth = 2, rightDepth = 1
→ currDiameter = 3
→ maxDiameter = max(2, 3) = 3
→ Return depth = 3
Final Result: 3
root = TreeNode(1)
├── left: TreeNode(2)
│ ├── left: TreeNode(4)
│ └── right: TreeNode(5)
└── right: TreeNode(3)
Step 1:
→ Call findDepth(1)
Step 2:
→ Call findDepth(2)
Step 3:
→ Call findDepth(4)
Step 4:
→ Call findDepth(null) → return 0
→ Call findDepth(null) → return 0
→ Node 4 → leftDepth = 0, rightDepth = 0
→ currDiameter = 0
→ maxDiameter = max(0, 0) = 0
→ Return depth = 1
Step 5:
→ Back to Node 2
→ leftDepth = 1
→ Call findDepth(5)
Step 6:
→ Call findDepth(null) → return 0
→ Call findDepth(null) → return 0
→ Node 5 → leftDepth = 0, rightDepth = 0
→ currDiameter = 0
→ maxDiameter = max(0, 0) = 0
→ Return depth = 1
Step 7:
→ Back to Node 2
→ rightDepth = 1
→ Node 2 → leftDepth = 1, rightDepth = 1
→ currDiameter = 2
→ maxDiameter = max(0, 2) = 2
→ Return depth = 2
Step 8:
→ Back to Node 1
→ leftDepth = 2
→ Call findDepth(3)
Step 9:
→ Call findDepth(null) → return 0
→ Call findDepth(null) → return 0
→ Node 3 → leftDepth = 0, rightDepth = 0
→ currDiameter = 0
→ maxDiameter = max(2, 0) = 2
→ Return depth = 1
Step 10:
→ Back to Node 1
→ rightDepth = 1
→ Node 1 → leftDepth = 2, rightDepth = 1
→ currDiameter = 3
→ maxDiameter = max(2, 3) = 3
→ Return depth = 3
Final Result: 3
var diameterOfBinaryTree = function(root) {
let maxDiameter = 0;
let findDepth = (curr) => {
if(!curr) return 0;
let leftDepth = findDepth(curr.left);
let rightDepth = findDepth(curr.right);
let currDiameter = leftDepth + rightDepth;
maxDiameter = Math.max(currDiameter, maxDiameter);
return 1+Math.max(leftDepth, rightDepth);
}
findDepth(root);
return maxDiameter;
};
class Solution:
def diameterOfBinaryTree(self, root):
self.maxDiameter = 0
def findDepth(node):
if not node:
return 0
left = findDepth(node.left)
right = findDepth(node.right)
self.maxDiameter = max(self.maxDiameter, left + right)
return 1 + max(left, right)
findDepth(root)
return self.maxDiameter
class Solution {
int maxDiameter = 0;
public int diameterOfBinaryTree(TreeNode root) {
findDepth(root);
return maxDiameter;
}
private int findDepth(TreeNode node) {
if (node == null) return 0;
int left = findDepth(node.left);
int right = findDepth(node.right);
maxDiameter = Math.max(maxDiameter, left + right);
return 1 + Math.max(left, right);
}
}
class Solution {
public:
int maxDiameter = 0;
int findDepth(TreeNode* node) {
if (!node) return 0;
int left = findDepth(node->left);
int right = findDepth(node->right);
maxDiameter = std::max(maxDiameter, left + right);
return 1 + std::max(left, right);
}
int diameterOfBinaryTree(TreeNode* root) {
findDepth(root);
return maxDiameter;
}
};
// C doesn't support OOP, so we assume TreeNode is defined and a helper is used.
int maxDiameter = 0;
int findDepth(struct TreeNode* node) {
if (node == NULL) return 0;
int left = findDepth(node->left);
int right = findDepth(node->right);
int currDiameter = left + right;
if (currDiameter > maxDiameter) maxDiameter = currDiameter;
return 1 + (left > right ? left : right);
}
int diameterOfBinaryTree(struct TreeNode* root) {
maxDiameter = 0; // reset global variable
findDepth(root);
return maxDiameter;
}
public class Solution {
int maxDiameter = 0;
public int DiameterOfBinaryTree(TreeNode root) {
FindDepth(root);
return maxDiameter;
}
private int FindDepth(TreeNode node) {
if (node == null) return 0;
int left = FindDepth(node.left);
int right = FindDepth(node.right);
maxDiameter = Math.Max(maxDiameter, left + right);
return 1 + Math.Max(left, right);
}
}
