Diameter of Binary Tree 20 XP Easy

LeetCode Ctrl+Enter Run Ctrl+S Save

The diameter of a binary tree is the length of the longest path between any two nodes. The path may or may not pass through the root.

#       1
#      / \
#     2   3
#    / \
#   4   5
# Longest path: 4 → 2 → 1 → 3  (length = 3 edges)
# Or: 5 → 2 → 1 → 3 (also length = 3)
# Diameter = 3

Key insight: at each node, the diameter through that node = height of left subtree + height of right subtree.

Calculate the height of left and right subtrees at each node
The diameter at this node is left_height + right_height
Track the global maximum diameter across all nodes
The function returns the height (for parent calculations), while tracking diameter as a side effect

This is a pattern where you return one thing (height) but track another (diameter) — very common in tree problems.

📋 Instructions

Implement `diameter_of_binary_tree(root)` using DFS. Test with the tree above.

Use a nonlocal variable to track max diameter. DFS returns height. At each node: left_h = dfs(left), right_h = dfs(right). Update diameter = max(diameter, left_h + right_h). Return 1 + max(left_h, right_h).

🧪 Test Cases

Input

diameter_of_binary_tree(root)

Expected

3

Test case 1

Input

diameter_of_binary_tree(TreeNode(1, TreeNode(2)))

Expected

1

Test case 2

← Previous Next Exercise →

main.py

Hi! I'm Rex 👋

Output

Ready. Press ▶ Run or Ctrl+Enter.

›