Binary Tree · Diameter
Visual EditorTree Problems

Diameter of Binary Tree

Compute the longest path in one DFS by returning subtree heights and updating a running best.

RecursionDFSTree DP

Key concepts at a glance — for those who already know the basics.

Problem Statement

Diameter of Binary Tree

Given the root of a binary tree, return the length of the longest path between any two nodes. The length is measured in edges.
Example 1

Input: [1, 2, 3, 4, 5]

Output: 3

Longest path can be 4 - 2 - 1 - 3 (3 edges).

Example 2

Input: [1, 2, 3, 4, 5, 6, 7]

Output: 4

One longest path: 4 - 2 - 1 - 3 - 7.

Constraints

  • Nodes in the tree are in range [1, 10^4].
  • Node values are not important for this problem.
01

Core Formula

candidate(node) = leftHeight + rightHeight

Run one DFS. At each node update best=max(best, candidate), and return height=1+max(left, right).

02

How to Think

1

Ask each child for height

Every recursive call returns one integer: subtree height.

2

Compute local candidate

Path through current node uses one branch from left + one branch from right.

3

Return height upward

Parent only needs your best downward branch: 1 + max(left, right).

03

Dry Run

1234567Longest path example: 4 - 2 - 1 - 3 - 7 (4 edges)
Step
Node
State Update
1
4
left=0, right=0, candidate=0, height=1, best=0
2
5
left=0, right=0, candidate=0, height=1, best=0
3
2
left=1, right=1, candidate=2, height=2, best=2
4
6
left=0, right=0, candidate=0, height=1, best=2
5
7
left=0, right=0, candidate=0, height=1, best=2
6
3
left=1, right=1, candidate=2, height=2, best=2
7
1
left=2, right=2, candidate=4, height=3, best=4
04

Code

solution.py
def diameterOfBinaryTree(root):
best = 0
def height(node):
nonlocal best
if node is None: return 0
left = height(node.left)
right = height(node.right)
best = max(best, left + right)
return 1 + max(left, right)
height(root)
return best
05

Complexity

Time

O(n)

Each node is processed exactly once.

Space

O(h)

Recursion stack depth equals tree height.

06

Interview Uses

Balanced Binary Tree

You already compute left/right heights at every node, so balance checks are a natural extension.

Height of Binary Tree

Diameter helper is fundamentally a height DFS with one extra candidate update.

Maximum Path Sum

Same tree DP pattern: compute child contributions and update a global answer.

N-ary Tree Diameter

Generalize by keeping top two child heights instead of just left/right.

Ready to watch candidate updates live?

Open the visualizer and inspect leftHeight, rightHeight, and best at each node.

Open Visualizer