Diameter of Binary Tree
Find the largest number of edges on a path between any two nodes of a binary tree. The path need not pass through the root.
Work through the cases
3 examplesInput notation
A binary tree in level order on one line, using null for missing children. Omit trailing nulls; use null for an empty tree.Expected result
The diameter in edges.Case 1
Input
1 2 3 4 5
Expected output
3
Case 2
Input
7
Expected output
0
Case 3
Input
null
Expected output
0
These notes use simplified input/output notation. The linked platform defines the method signature and judge format.
FROM IDEA TO IMPLEMENTATION
Understand the approach.
Compare the documented approaches below. Brute force, better, and optimal versions appear where available; a direct exercise may need only one approach.
The diameter is the longest number of edges between any two nodes. Pairwise paths are unrealistic. Any diameter passes through some node as the sum of that node's two subtree heights. DFS returns height and, on the way up, updates a global answer with l+r, then returns 1+\max(l,r) to the parent. Each node is visited once.
We can enumerate each node of the binary tree, and for each node, calculate the maximum depth of its left and right subtrees, l and r, respectively. The diameter of the node is l + r. The maximum diameter among all nodes is the diameter of the binary tree.
The time complexity is O(n), and the space complexity is O(n). Here, 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() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
private int ans;
public int diameterOfBinaryTree(TreeNode root) {
dfs(root);
return ans;
}
private int dfs(TreeNode root) {
if (root == null) {
return 0;
}
int l = dfs(root.left);
int r = dfs(root.right);
ans = Math.max(ans, l + r);
return 1 + Math.max(l, r);
}
}Reference code. Platform solutions may use supplied node types, imports, or collection libraries; foundational examples are complete programs.
Solutions adapted from Doocs / LeetCode contributors, licensed under CC BY-SA 4.0. Formatting changed; TypeScript versions converted to JavaScript. Supplemental implementations and approach notes added. Adapted solution material is available under the same license.