What is the Longest Univalue Path pattern?

The Longest Univalue Path is a common coding interview pattern in Depth First Search problems. It provides a structured approach to solving related algorithm challenges efficiently.

When should I use Longest Univalue Path?

Use the Longest Univalue Path pattern when you encounter problems matching its characteristics. Check the "When to Use" and "Clues" sections in the lesson for specific indicators.

Is Longest Univalue Path asked in FAANG interviews?

Yes, Longest Univalue Path is an essential pattern commonly tested in FAANG and top tech company technical interviews.

Depth-First Search

Medium

Longest Univalue Path

Find the length of the longest path where each node in the path has the same value.

10 min read

Solve on LeetCode

Examples

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

Output:2

Explain:

The longest path of value 5 is 5 -> 5 -> 5 (length 2).

Problem Understanding

We need the longest path (edges) where every node has the same value.

Like Diameter, the path does not need to pass through the root. It can form an inverted 'V' shape at any mode.

Algorithm Strategy

We use Post-Order DFS.

At each node:

Recursive calls get the longest univalue path extending down from left and right children.
Check Value:
- If node.left exists and node.left.val == node.val, we can extend the left path by 1.
- Otherwise, the path from the left stops here (RESET to 0).
- Same logic for right child.
Update Global Max: maxPath = max(maxPath, arrowLeft + arrowRight).
Return: max(arrowLeft, arrowRight) (we can only extend one branch up to the parent).

Interactive Visualization

Step 1 / 13

curr

Visiting Node 5. Asking children for univalue path extensions...

Custom Input

See the Logic in Motion

Stop memorizing code. Unlock the full interactive visualizer to master the logic step-by-step.

Unlock VisualizerPREMIUM FEATURE

Stop Guessing, Start Mastering.

Build the FAANG intuition. Master this pattern with optimized implementations, visual dry runs, and our curated collection of high-yield problems.

Start Your Premium Prep