How do you approach Diameter of Binary Tree?

For any single node, the longest path THROUGH it is leftHeight + rightHeight (in edges).

What is the time complexity of Diameter of Binary Tree?

Time complexity: O(n). Space complexity: O(h).

What are common mistakes on Diameter of Binary Tree?

Handling the null node deep in the recursion instead of as the first base case. Returning early from a subtree when the answer needs both sides explored. Confusing height with depth. One counts up from the node, the other down from the root, and the off-by-one is silent.

gitGood.dev

← Back to problems

Diameter of Binary Tree

EasyData Structures

Description

Given a binary tree, return the length of its **diameter**: the number of edges on the longest path between any two nodes. The path does not have to pass through the root. The tree is given as a **level-order array with explicit nulls**, where the children of index `i` sit at `2i + 1` and `2i + 2`. An empty array is an empty tree.

Example 1

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

Output: 3

Example 2

Input: root = [1,2]

Output: 1

Example 3

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

Output: 4

Constraints

- 0 <= number of nodes <= 10^4 - The answer is measured in EDGES, so a single node has diameter 0.

Diameter of Binary Tree: approach, complexity and pitfalls

An easy trees problem, graded against 6 test cases (3 of them hidden).

The pattern: Trees

Recursive traversal of binary trees and BSTs - depth, validation, and path problems.

Reach for it when you see: A TreeNode input, or anything about depth, ancestry, or in-order ordering.

More Treesproblems →

If you are stuck

Show the 3-step hint ladder

For any single node, the longest path THROUGH it is leftHeight + rightHeight (in edges).
So compute heights recursively, and at each node update a running maximum with leftHeight + rightHeight.
The function returns the height for its parent to use; the diameter is tracked separately, because the best path may not include the root.

The optimal approach

Show the approach: The answer is a maximum over nodes, not a property of the root

The key reframing: for each individual node, the longest path passing *through* that node is `leftHeight + rightHeight` measured in edges. The diameter is the maximum of that quantity over all nodes.

So one post-order traversal does it. Each call computes its children's heights, updates a running maximum with their sum, and returns `1 + max(left, right)` for its own parent. The two quantities are different - what you return is not what you track - and conflating them is the usual bug.

The reason a separate maximum is needed at all is that the best path need not touch the root. A tree with a heavy subtree hanging off one side can have its diameter entirely inside that subtree, which is why returning the root's `left + right` alone is wrong.

Counting edges rather than nodes is the other trap: a leaf has height 1 in node terms but contributes 0 edges, so a single-node tree has diameter 0, not 1.

Time: O(n)
Space: O(h)

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Empty input. At least one case passes an empty collection. Make sure your loop bounds and any "first element" read survive a length of zero.
Single element. A one-element case is included. Two-pointer and window solutions frequently return the wrong thing when the two indices start out equal.
Duplicate values. Repeated values appear in the input, so any logic that assumes distinct elements - or that skips over equal neighbours - is exercised.
Null values. A null appears in the input. Guard your dereferences rather than relying on the shape of the sample case.

Common Trees mistakes

These apply to the pattern as a whole, not just this problem.

Handling the null node deep in the recursion instead of as the first base case.
Returning early from a subtree when the answer needs both sides explored.
Confusing height with depth. One counts up from the node, the other down from the root, and the off-by-one is silent.