← all entries
A-048● Day 482026.06.23easyleetcode #543neetcode150

Diameter of Binary Tree

#tree#depth-first-search#binary-tree
↗ leetcode #543 · diameter-of-binary-tree
01

Problem

· problem
P.048

Diameter of Binary Tree

↗ leetcode #543

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.

constraints
  • · The number of nodes in the tree is in the range [1, 10^4]
  • · -100 ≤ Node.val ≤ 100
// paraphrased summary — see source for full text
examples
example 1input → output
[1,2,3,4,5]
3
example 2input → output
[1,2]
1
02

Pre-solve

· pre-solve
● 1list shown→● 2select→● 3reveal
  • ☐
    Must the diameter path always pass through the root?
  • ☐
    Is the path length measured by number of nodes or number of edges?
  • ☐
    What is the diameter of a tree with only one node?
  • ☐
    What should each node return in the DFS recursion?
  • ☐
    How is the maximum diameter calculated at each node?
  • ☐
    Can the time complexity be improved to O(1)?
  • ☐
    Can the diameter be equal to the tree height?
check the items you would ask, then press confirm
// session-only state — refresh resets (repeatable practice)
03

Logic Structure

· logic
● 1slots shown→● 2pick per slot→● 3reveal
// pick one code line per slot to assemble the algorithm flow. no typing — just the logic skeleton.
step 1· Initialize result variable
○
res = 0
○
res = -1
○
res = float('inf')
step 2· Define DFS function
○
def dfs(root):
○
def bfs(root):
○
def diameter(root):
step 3· Recursion base case│ nested
○
if not root:
○
if root is None: return -1
○
if not root.left and not root.right: return 1
step 4· Compute left and right subtree heights│ nested
○
left = dfs(root.left)
○
left = dfs(root.left) + 1
○
right = root.right.val
step 5· Update maximum diameter│ nested
○
res = max(res, left + right)
○
res = left + right
○
res += left + right
step 6· Return height of current subtree│ nested
○
return 1 + max(left, right)
○
return max(left, right)
○
return left + right
pick one option per slot
// format: slot — recursive / DP patterns use ordering / state-first formats. ADR-08 follow-up.
04

Solve · Trace

· solve
solution.py
1
# Definition for a binary tree node.
2
# class TreeNode:
3
#     def __init__(self, val=0, left=None, right=None):
4
#         self.val = val
5
#         self.left = left
6
#         self.right = right
7
class Solution:
8
    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
9
        res = 0
10
11
        def dfs(root):
12
            nonlocal res
13
14
            if not root:
15
                return 0
16
            left = dfs(root.left)
17
            right = dfs(root.right)
18
            res = max(res, left + right)
19
20
            return 1 + max(left, right)
21
22
        dfs(root)
23
        return res
mental dry-run cases
// walk each case in your head; expand the worked example below if stuck.
case 1
[1,2,3,4,5]
→
3
case 2
[1,2]
→
1
// UI does not walk-through — you do the dry-run mentally. Expand the worked example if stuck.