Longest Span Between Nodes

MediumTrees

Problem

A cable network is laid out as a binary tree. The span between two nodes is the number of edges on the path connecting them.

Given the root, return the largest span between any two nodes. The path does not have to pass through the root.

Example 1

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

4 → 2 → 1 → 3 (or 5 → 2 → 1 → 3) uses three edges.

Example 2

Input:
root = [1, 2]
Output:
1

Constraints

  • 0 ≤ number of nodes ≤ 10^4
  • Tree height ≤ 500
  • -100 ≤ node.val ≤ 100

Hint

Show the first hint

Every path has one highest node where it turns around. What does the longest path through a given turning node look like?

Walkthrough

How to approach it

01Clarify before coding

  • Counted in edges or nodes? Edges: a single node has span 0.
  • Must the path go through the root? No, see the hidden case where the best path lives in the left subtree.
  • Empty tree? Return 0.

02Brute force

For every node, compute left and right heights with a separate height function and take the best sum.

Cost: O(n²) on a chain because each height call re-walks its subtree.

The rest of the walkthrough is in the app

The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.

Solve it in the browserStart free

This problem is part of Pro.