Diameter of Binary Tree
Problem
Given the root of a binary tree, return the length of the diameter of the tree, where the diameter is defined as the length of the longest path between any two nodes in the tree. The path may or may not pass through the root.
- The number of nodes in the tree is in the range [1, 10⁴]
- −100 ≤ Node.val ≤ 100
Example
root = [1,2,3,4,5]3The longest path is [4,2,1,3] or [5,2,1,3], both with length 3 edges. The algorithm uses DFS to compute the depth of left and right subtrees for each node, updating the maximum diameter found as the sum of left and right depths. For example, at node 2, left depth is 1 (node 4), right depth is 1 (node 5), so diameter candidate is 2. At root 1, left depth is 2, right depth is 1, so diameter candidate is 3, which is the maximum.
Approach
Straightforward Solution
A brute-force approach would compute the longest path by checking all pairs of nodes, which is O(n^2) and inefficient for large trees.
Core Observation
The diameter of a binary tree is the maximum sum of the depths of the left and right subtrees at any node. This is because the longest path between two nodes passes through their lowest common ancestor, and the path length is the sum of the depths of the two subtrees rooted at that ancestor.
Path to Optimal
PreviewThe key insight is to use a post-order DFS traversal to compute the depth of each subtree while simultaneously updating the maximum diameter found so far. At each node, the diameter candidate is the sum of the left and right subtree depths…
Full step-by-step walkthrough on Pro →
Optimal Approach
PreviewPerform a DFS that returns the depth of the subtree rooted at the current node. During the recursion, update a global variable to track the maximum diameter found as the sum of left and right subtree depths at each node…
Full step-by-step walkthrough on Pro →
Want the full reasoning chain?
Unlock the complete walkthrough, line-by-line analysis, and recall drill.
Unlock ProTime
O(n)
Each node is visited exactly once during the DFS traversal, and constant work is done per node.
Space
O(h)
The recursion stack uses space proportional to the height of the tree, which is O(h). In the worst case (skewed tree), h can be O(n), but for balanced trees, h is O(log n).
Pattern Spotlight
DFS (Post-Order Traversal with State Propagation)
When a problem requires combining information from subtrees to compute a global property (like diameter), use post-order DFS to gather subtree results and propagate state upward, updating global answers along the way.
Solution
| 1 | class Solution:
|
| 2 | def diameterOfBinaryTree(self, root: TreeNode) -> int:
|
| 3 | res = 0
|
| 4 |
|
| 5 | def dfs(root):
|
| 6 | nonlocal res
|
| 7 | if not root:
|
| 8 | return 0
|
| 9 |
|
| 10 | left = dfs(root.left)
|
| 11 | right = dfs(root.right)
|
| 12 |
|
| 13 | res = max(res, left + right)
|
| 14 |
|
| 15 | return 1 + max(left, right)
|
| 16 |
|
| 17 | dfs(root)
|
| 18 | return res |
Step-by-Step Solution
Initialize Diameter Tracker and Define DFS to Compute Subtree Depths
| 3 | res = 0
|
| 5 | def dfs(root):
|
| 6 | nonlocal res
|
| 7 | if not root:
|
| 8 | return 0
|
Objective
To set up a variable to track the maximum diameter found and define a recursive DFS function that computes subtree depths while updating this diameter.
Key Insight
Using a nonlocal variable allows the DFS function to update the global maximum diameter during recursion. The DFS returns the depth of the subtree rooted at the current node, enabling the calculation of diameter candidates as the sum of left and right depths. This design tightly couples depth calculation with diameter tracking, enabling a single-pass solution.
Interview Quick-Check
Core Logic
The DFS returns the maximum depth of the current node's subtrees, while updating the global diameter as the sum of left and right depths.
State & Boundaries
The base case returns 0 for null nodes, representing zero depth.
Common Pitfalls & Bugs
Forgetting to use a nonlocal or global variable for diameter tracking would prevent updates from propagating outside the DFS function.
Recursively Compute Left and Right Subtree Depths and Update Diameter
To recursively compute the depths of left and right subtrees, update the maximum diameter with their sum, and return the depth of the current subtree.
Invoke DFS on Root and Return Final Diameter
To start the DFS traversal from the root and return the computed maximum diameter after traversal completes.
2 more steps with full analysis available on Pro.
Line Analysis
This solution has 3 Critical lines interviewers watch for.
res = max(res, left + right)Update the global diameter with the sum of left and right depths if larger.
This line is the core algorithmic move: it considers the longest path passing through the current node by summing left and right depths, updating the global maximum diameter accordingly.
nonlocal resDeclare that the DFS function will modify the nonlocal diameter variable.
Using 'nonlocal' allows the DFS function to update the diameter variable defined in the outer scope, enabling global state tracking during recursion.
return 1 + max(left, right)Return the depth of the current subtree as 1 plus the maximum of left and right depths.
Returning this value allows parent calls to correctly compute their subtree depths, enabling the recursive propagation of depth information necessary for diameter calculation.
Full line-by-line criticality + rationale for all 11 lines available on Pro.
Test Your Understanding
Why does summing the depths of the left and right subtrees at each node correctly compute the diameter?
See the answer with Pro.
Related Problems
DFS pattern
Don't just read it. Drill it.
Reconstruct Diameter of Binary Tree from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Diameter of Binary Tree drill