Longest Univalue Path - Practice Coding Problems

Longest Univalue Path - Problem

Given the root of a binary tree, return the length of the longest path, where each node in the path has the same value. This path may or may not pass through the root.

The length of the path between two nodes is represented by the number of edges between them.

Input & Output

Example 1 — Basic Tree

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

› Output: 2

💡 Note: The longest path with same values is 5→5→5 from root through right child to its right child, giving length 2 (2 edges)

Example 2 — Single Value Tree

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

› Output: 2

💡 Note: The longest same-value path is 4→4→4 in the left subtree, with length 2

Example 3 — All Same Values

$ Input: root = [1,1,1,1,1,1,1]

› Output: 4

💡 Note: Multiple paths exist, longest goes through root connecting both subtrees: 1→1→1→1→1 with length 4

Constraints

The number of nodes in the tree is in the range [0, 10⁴].
-1000 ≤ Node.val ≤ 1000
The depth of the tree will not exceed 1000.

Visualization

Tap to expand

Understanding the Visualization

Input Tree

Binary tree with various node values

Find Same-Value Paths

Identify all paths where nodes have identical values

Return Length

Count edges in the longest same-value path

Key Takeaway

🎯 Key Insight: Use DFS to combine left and right same-value path lengths at each node to find the global maximum

Asked in

G Google 35 f Facebook 28 a Amazon 22 M Microsoft 18

The key insight is to use DFS where each node returns the longest same-value path extending downward, while updating a global maximum with paths that pass through the current node. Best approach uses optimized DFS in a single traversal. Time: O(n), Space: O(h)

Common Approaches

Approach	Time	Space	Notes
✓ Optimized DFS	O(n)	O(h)	Single DFS traversal calculating longest same-value path at each node
Brute Force - Check All Paths	O(n²)	O(h)	For each node, explore all possible paths and find the longest univalue path

Optimized DFS — Algorithm Steps

Start DFS from root
At each node, calculate longest same-value paths going left and right
Update global maximum with path through current node
Return longest single-direction path to parent

Visualization

Tap to expand

Step-by-Step Walkthrough

DFS Traversal

Visit each node once using depth-first search

Calculate Paths

At each node, compute longest same-value paths from left and right

Update Maximum

Combine left and right paths through current node for global max

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
};

int maxLength = 0;

int dfs(struct TreeNode* node) {
    if (!node) return 0;
    
    int leftLength = dfs(node->left);
    int rightLength = dfs(node->right);
    
    if (node->left && node->left->val != node->val) {
        leftLength = 0;
    }
    if (node->right && node->right->val != node->val) {
        rightLength = 0;
    }
    
    int pathLength = leftLength + rightLength;
    if (pathLength > maxLength) {
        maxLength = pathLength;
    }
    
    return (leftLength > rightLength ? leftLength : rightLength) + 1;
}

int solution(struct TreeNode* root) {
    if (!root) return 0;
    
    maxLength = 0;
    dfs(root);
    return maxLength;
}

struct TreeNode* createNode(int val) {
    struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    node->val = val;
    node->left = NULL;
    node->right = NULL;
    return node;
}

int main() {
    struct TreeNode* root = createNode(5);
    root->left = createNode(4);
    root->right = createNode(5);
    root->left->left = createNode(1);
    root->left->right = createNode(1);
    root->right->right = createNode(5);
    
    int result = solution(root);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Visit each node exactly once in the tree

✓ Linear Growth

Space Complexity

O(h)

Recursion stack depth equals tree height h

✓ Linear Space

52.0K Views

Medium Frequency

~25 min Avg. Time

2.2K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Optimized DFS — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler