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.

Browse Curriculum

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 / 1

Empty Heap

Initializing...

Custom Input

Visualize how we reset counts when values mismatch.

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.