← DSA Atlas
Dedicated problem page · #543

Diameter of Binary Tree

EasyTrees and Binary Search TreesPost-order height with a running bestDFS returning height while tracking the max path through each node
Solve on LeetCode ↗
543
EasyTrees and Binary Search TreesDFS returning height while tracking the max path through each nodePost-order height with a running best

Diameter of Binary Tree

Given the root of a binary tree, return the length of its diameter: the number of edges on the longest path between any two nodes. This path may or may not pass through the root.

Open official problem prompt ↗
In plain English

Find the number of edges on the longest chain connecting any two nodes in the tree.

Picture it like this

Like finding the two most distant leaves on a real tree: at every branch point you measure how far the longest twig reaches on each side and see if joining them beats the current record.

Example
Input
root = [1, 2, 3, 4, 5]
Output
3
Why
The longest path is 4 -> 2 -> 1 -> 3 (or 5 -> 2 -> 1 -> 3), which uses 3 edges.
Constraints
The number of nodes is in the range [1, 10^4]-100 <= Node.val <= 100
Pattern lesson

See the pattern, then code

Post-order height with a running best
Recognition clue

You want the longest path between any two nodes, and the best path 'bends' at some node — a signal to compute heights bottom-up while checking each node as a potential turning point.

↗
Trees and Binary Search Trees

Hierarchies, subtree aggregation, path properties, or ordered tree queries.. The longest path that turns at a node equals leftHeight + rightHeight (in edges); computing heights once lets you test every node as the turning point in a single pass.

New words, made simpleKnow these before the algorithm
Diameter
The longest path between two nodes, measured in edges.
Height (in edges)
The number of edges from a node down to its deepest leaf; a leaf has height 0.
Turning point
The highest node on a path, where the path goes down-left then down-right.
Approaches from first idea to best ideaCompare the trade-offs
ApproachHow it thinksCost
Brute force per node

Recomputes heights repeatedly; too slow on skewed trees.

For every node, separately compute left and right heights and sum them.

Time O(n^2)Space O(h)
Best choiceSingle post-order pass

Each node visited once; heights reused as they bubble up.

Compute each subtree's height once and update a global best with left+right at every node.

Time O(n)Space O(h)
The rule we keep true

Invariant

After height(node) returns, best holds the largest left+right edge sum seen among all nodes processed so far.

Why this is correct

Reasoning

Any simple path has a unique highest node; at that node the path is exactly leftHeight + rightHeight edges. Since we test every node as the highest point, we necessarily test the true diameter's turning point.

The algorithm in three movesSay these aloud before coding
1Define a height helper that returns edge-height of a subtree

h(4)=0, h(5)=0

2At each node compute leftHeight and rightHeight

at 2: left=1,right=1 -> best=2

3Update a global best with leftHeight + rightHeight

at 1: left=2,right=1 -> best=3

4Return 1 + max(leftHeight, rightHeight) as this node's height

5Return the best after the traversal

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example
10
21
32
43
54
1 · Readnode 4 then 5
2 · AskHeight of leaf?
3 · Update statechildren null
4 · Resultreturn 0; best stays 0
Key takeaway

The path 4 -> 2 -> 1 -> 3 bends at the root and spans 3 edges.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

  1. 1
    Lines 17-18Base case

    A null subtree has edge-height 0, the anchor for the height count.

  2. 2
    Lines 19-21Measure and record

    Get both child heights, then treat this node as a turning point: left+right edges is a candidate diameter.

  3. 3
    Lines 22Return height upward

    The parent only needs the single deeper branch plus one edge, not the bent path.

Make it stick

Edge cases, mistakes, and one self-check

E

Edge cases to test

  • Single node returns 0 (no edges)
  • A straight skewed tree returns n-1
  • Best path not through the root — handled because every node is tested
!

Common beginner mistakes

  • Returning best as a count of nodes instead of edges
  • Returning left+right from the helper instead of 1+max(...), which corrupts parent heights
  • Forgetting nonlocal, so updates to best are lost
Check your understanding

Why can the helper return only max(left,right)+1 even though we recorded left+right?

More in Trees and Binary Search Trees

#104Maximum Depth of Binary TreePost-order height aggregation#102Binary Tree Level Order TraversalLevel-by-level BFS#98Validate Binary Search TreeRange-bounded validation#236Lowest Common Ancestor of a Binary TreeBottom-up LCA search#105Construct Binary Tree from Preorder and InorderPreorder root + inorder split#124Binary Tree Maximum Path SumPost-order gain with global best