Diameter of Binary Tree

easyPROTrees & BFS/DFSMeta DSA

Given the root of a binary tree (as a level-order array), return the diameter — the length of the longest path between any two nodes.

The length is measured by the number of edges between them.

Example

Input

1,2,3,4,5

Output

Reasoning

Input: the level-order array 1,2,3,4,5 fills the tree row by row, left to right: 1 is the root, 2 and 3 are its left and right children, and 4 and 5 are both children of 2.
Paths between leaves: $4 \to 2 \to 5$ has $2$ edges. $4 \to 2 \to 1 \to 3$ has $3$ edges.
Why $3$ is the maximum: node 3 sits $1$ edge below the root, while 4 and 5 sit $2$ edges below it. A path joining the two sides of the root therefore has $2 + 1 = 3$ edges.
Output: 3, a count of edges, not nodes: the path $4 \to 2 \to 1 \to 3$ visits $4$ nodes but uses $3$ edges.
Notice: the longest path need not touch the root. Drop 3 and hang a child $6$ under 4 and a child $7$ under 5: then $6 \to 4 \to 2 \to 5 \to 7$ has $4$ edges, while any path touching the root has at most $3$ . A single-node tree has diameter $0$ .

Constraints

1 <= number of nodes <= 10^4
-100 <= Node.val <= 100

Learn this in

Depth First Search & TreesDSA Study Plan

More from Meta DSA

Valid Palindrome IIeasy Dot Product of Two Sparse Vectorseasy Random Pick with Weightmedium Copy List with Random Pointermedium Remove Nth Node From Endmedium

PRO

Editor locked

The code editor is locked for Pro problems. It is only available for free problems. Please upgrade to gain access to the code editor for all problems.

solution.py

Python 3.13

Test results