leetExpert
Practice

Diameter of Binary Tree

Module 17 · Binary Trees

Problem

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 in the tree. This path may or may not pass through the root.

Examples

Example 1

Inputroot = [1,2,3,4,5]Output3

Explanation. longest path 4-2-1-3 or 5-2-1-3; three edges

Example 2

Inputroot = [1,2]Output1

Explanation. the single edge between 1 and 2

text
      1
     / \
    2   3
   / \
  4   5

Constraints

1 ≤ n ≤ 10⁴ nodes

Attempt it first

This is the problem where bottom-up recursion first bites back. It looks like maximum depth — and the height recursion from the last lesson is indeed the engine — but the answer you want and the value each call must return are two different things, and conflating them produces a wrong answer that passes on small symmetric trees. Try it before revealing. Specifically, wrestle with this: the longest path bending at a node (down its left, up through the node, down its right) is a great candidate for the answer — but can a function return that quantity to its parent and have the parent use it? Work out why not; that dead end is the whole lesson.