Longest Uniform Chain

MediumTrees

Problem

Given the root of a binary tree, return the number of edges in the longest path in which every node has the same value. The path may bend at one node (go up through a node and down the other side) and need not touch the root.

Example 1

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

5 → 5 → 5 down the right side: two edges.

Example 2

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

4 → 4 → 4 bends at the left child.

Constraints

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

Hint

Show the first hint

Like the longest span, every path has a topmost node where it bends. What can a child contribute to it?

Walkthrough

How to approach it

01Clarify before coding

  • Edges or nodes? Edges: a single node scores 0.
  • Can the path bend? Yes, through at most one topmost node, like any tree path.
  • Must it include the root? No.

02Brute force

From every node, explore every same-valued path through it.

Cost: O(n²) in the worst case (all values equal).

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.