{ }SolveLogs
⌕
Home / Binary Trees / #543
LeetCode #543 Easy

Diameter of Binary Tree

Diameter of Binary Tree is LeetCode 543 (Easy). Given the root of a binary tree, return the diameter of a binary tree: the number of edges on the longest path between any two nodes.

  • The path may or may not pass through the root.
  • Length counts edges, not nodes, so a single node has diameter 0.

With up to 10⁴ nodes, recomputing heights at every node is O(n²); one post-order pass does it in O(n).

Constraints
  • The number of nodes in the tree is in the range [1, 10⁴].
  • -100 <= Node.val <= 100
treedfsrecursion
Open on LeetCode ↗
02

Intuition

Every path in a tree climbs to one highest node and then goes back down. Call that node the path's bend.

The longest path that bends at a node goes as deep as it can on both sides. If it can go l edges down on the left and r edges down on the right, that path has l + r edges. Trying every node as the bend covers every possible path, so the diameter of binary tree is the largest l + r found.

The usual height recursion already computes l and r at every node, so the check costs nothing extra. The one twist: the function returns the depth (what the parent needs) while the diameter is kept in a separate best.

How to spot this pattern

"Longest path between any two nodes" of a tree is the bend pattern: the recursive function returns one arm (the depth) while a separate variable records the best path through each node. Binary Tree Maximum Path Sum uses the same split with node values instead of edge counts.

03

Approach

Try it first

Before reading on: in [1,2,3,4,5], at which node does the longest path bend, and how many edges does it have? What must each child report so its parent can measure a path through itself?

1

Write the depth function

depth(node) returns the number of nodes on the longest downward path from node: 0 for an empty child, otherwise 1 + max(l, r). Seen from the parent, that same number counts the edges from the parent down to the deepest leaf on that side.

2

Finish both children first

Call depth on the left and right child before doing anything at the node (post-order). The node needs both numbers, l and r, before it can measure a path that bends through it.

3

Measure the path through this node

The longest path bending here has l + r edges: l down the left side plus r down the right. Update best = max(best, l + r). Do not add 1; that would count nodes instead of edges.

4

Return the depth, not the path

Return 1 + max(l, r). A path that bends here cannot also continue up to the parent, so the parent may only extend the deeper side. The diameter lives only in best.

5

Return best

When depth(root) finishes, every node has been tried as the bend, so best is the diameter. Each node is visited once: O(n) time, and O(h) stack space for a tree of height h.

04

Diameter of Binary Tree solution in Python | C++ | Java

▶1class Solution:
▶2 def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
▶3 self.best = 0
▶4 
▶5 def depth(node):
▶6 if not node:
▶7 return 0
▶8 l, r = depth(node.left), depth(node.right)
▶9 self.best = max(self.best, l + r)
▶10 return 1 + max(l, r)
▶11 
▶12 depth(root)
▶13 return self.best
treeddepth returnedbest path123450bestbest = 0, children report first
best0longest path so far, in edges
Plan. Every path climbs to one highest node and goes back down. Each node will be tried as that bend, using the depths its children report, so children are finished first (post-order). best starts at 0: a single node is a path of 0 edges.
treeddepth returnedbest path123450left+0right=0path here0bestbend at 4: 0 edges, best stays 0
l0no left child
r0no right child
l + r0edges through 4
best0unchanged
4 is a leaf: both children are empty and report 0, so the only path bending here is the node alone, 0 edges.
treeddepth returnedbest path1234151this node+0no child=1returnsreturn 1 + 0 = 1 to node 2
return11 + max(l, r)
best0
A leaf's longest downward path is just itself, so it returns depth 1. From node 2, that is 1 edge down to 4.
treeddepth returnedbest path1234150left+0right=0path here0bestbend at 5: 0 edges, best stays 0
l0no left child
r0no right child
l + r0edges through 5
best0unchanged
5 is a leaf: both children are empty and report 0, so the only path bending here is the node alone, 0 edges.
treeddepth returnedbest path12341511this node+0no child=1returnsreturn 1 + 0 = 1 to node 2
return11 + max(l, r)
best0
A leaf's longest downward path is just itself, so it returns depth 1. From node 2, that is 1 edge down to 5.
treeddepth returnedbest path12341511left+1right=2path here2bestbend at 2: 2 edges > 0 → new best
l1depth of left child
r1depth of right child
l + r2edges through 2
best2improved
The longest path bending at 2 goes 1 edge down the left and 1 down the right (blue), 2 in total. That beats 0, so best becomes 2.
treeddepth returnedbest path122341511this node+1deeper side=2returnsreturn 1 + 1 = 2 to node 1
return21 + max(l, r)
best2
Node 1 can extend only one side of 2: a path that bends at 2 cannot also go up. So return the deeper side plus one for the edge up to 1: 2.
treeddepth returnedbest path122341510left+0right=0path here2bestbend at 3: 0 edges, best stays 2
l0no left child
r0no right child
l + r0edges through 3
best2unchanged
3 is a leaf: both children are empty and report 0, so the only path bending here is the node alone, 0 edges.
treeddepth returnedbest path1223141511this node+0no child=1returnsreturn 1 + 0 = 1 to node 1
return11 + max(l, r)
best2
A leaf's longest downward path is just itself, so it returns depth 1. From node 1, that is 1 edge down to 3.
treeddepth returnedbest path1223141512left+1right=3path here3bestbend at 1: 3 edges > 2 → new best
l2depth of left child
r1depth of right child
l + r3edges through 1
best3improved
The longest path bending at 1 goes 2 edges down the left and 1 down the right (blue), 3 in total. That beats 2, so best becomes 3.
treeddepth returnedbest path13223141511this node+2deeper side=3returnsroot returns 3, not the answer
return31 + max(l, r)
best3
The root returns its depth too, but nothing above uses it. The answer is best, which may bend anywhere in the tree.
treeddepth returnedbest path13223141513bestreturn best = 3
diameter3bends at node 1
work5 nodeseach visited once, O(n)
Diameter 3. The green path is the longest, 3 edges, bending at node 1. Each node was visited once.
05

Common pitfalls

Only checking the path through the root

✗ Wrong
return depth(root.left) + depth(root.right)
✓ Right
self.best = max(self.best, l + r)  # at every node

In [1,2,null,3,4,5,null,null,6] the root has no right child, so the root-only answer is 3. The longest path, 5 → 3 → 2 → 4 → 6, bends at node 2 and has 4 edges.

Returning the path length to the parent

✗ Wrong
return l + r
✓ Right
self.best = max(self.best, l + r)
return 1 + max(l, r)

The parent needs one arm it can extend. A path that already bends at this node cannot continue upward without visiting the node twice, so returning l + r inflates every depth above it.

Counting nodes instead of edges

✗ Wrong
self.best = max(self.best, l + r + 1)
✓ Right
self.best = max(self.best, l + r)

l and r already count the edges from this node down each side. Adding one returns 4 instead of 3 for [1,2,3,4,5].

Updating a plain local variable from the nested function

✗ Wrong
best = 0
def depth(node):
    ...
    best = max(best, l + r)
✓ Right
self.best = 0  # or: nonlocal best

Assigning to best inside depth makes Python treat it as a new local, so the first read raises UnboundLocalError. Store it on self or declare it nonlocal.

06

Edge cases

A single node

Both children report 0, so l + r = 0 and the diameter is 0: a path with no edges.

07

Complexity

Time
O(n)
Space
O(h)
One post-order pass; h is the tree height, up to n on a chain. Computing heights separately at every node is O(n²).
08

Diameter of Binary Tree FAQ

Is there a simpler O(n²) way to find the diameter of a binary tree?

Yes. For every node, call a separate height function on its left and right child and add the two results; the diameter is the largest sum. It is easy to write, but height revisits the same subtrees again and again, so a chain of n nodes costs O(n²). The approach above gets both heights from one post-order pass, so each node is visited once.

← Prev · #542
01 Matrix
Next · #545 →
Boundary of Binary Tree