Diameter of Binary Tree

Asked byFacebookAmazonBloombergGoogleMicrosoftApple

Problem

Given the root of a binary tree, return the length (in number of edges) of the longest path between any two nodes in the tree. This path may or may not pass through the root.

Examples

Example 1

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

Output:3

The longest path is [4,2,1,3] or [5,2,1,3], with 3 edges.

Constraints

1 <= number of nodes <= 10^4

Solve it in the editor. Sign in free to run your Python or JavaScript against test cases, get a verdict, and track your attempts.

Solve on FeatCode →

How to approach it: the Trees pattern

A tree is a hierarchical structure where each node has at most a fixed number of children (two, for binary trees). Almost every tree problem reduces to a traversal — decide what order you visit nodes in, and what you do at each one.

Look for this pattern when

The problem is naturally recursive: "the answer for this tree depends on the answer for its subtrees."
You need level-by-level information (BFS) versus depth-first structural information (DFS).

Read the full Trees guide →

Video walkthroughs

Original problem on LeetCode ↗