Longest Univalue Path

Problem Statement

Given the root of a binary tree, the challenge is to ascertain the maximal extent of a path where every node shares the same value. This path might either pass through or circumvent the root of the tree. To clarify, the 'length of the path' in this context refers to the count of edges that connect sequential nodes along the path. The objective is not just to find a path but to find the longest one where the same numerical value is repeated throughout consecutive nodes in the tree.

Examples

Example 1

Input:

root = [5,4,5,1,1,null,5]

Output:

2

Explanation:

The longest path of same values consists of two nodes with value 5 connected through the right subtree: 5 -> 5.

Example 2

Input:

root = [1,4,5,4,4,null,5]

Output:

2

Explanation:

The longest path of same values consists of two nodes with value 4 connected through the left subtree: 4 -> 4.

Constraints

• The number of nodes in the tree is in the range [0, 10^4].
• -1000 <= Node.val <= 1000
• The depth of the tree will not exceed 1000.

Approach and Intuition

The task involves tracing the longest unbroken sequence where all nodes hold the same value. This scenario requires a continuous comparison of node values during traversal and simultaneous tracking of sequence length.

1. Recursive Depth-First Search (DFS):

   • Use DFS to explore every node in the tree.
   • For each node, recursively determine the longest univalue path in the left and right subtrees.

2. Path Extension Logic:

   • If the child node's value equals the current node's value, the path can be extended.
   • Track the length of the left and right univalue paths separately.

3. Calculate and Update Global Maximum:

   • At each node, compute the combined path length if both left and right univalue paths extend from it.
   • Update the global maximum with this combined value.

4. Return Extension Lengths to Parent:

   • For recursive purposes, return only the longer of left or right univalue path lengths to the parent, since paths can't split upward.

5. Edge Cases:

   • If the tree is empty or has only one node, the maximum path is 0.

This DFS-based approach ensures all paths are checked once, giving an efficient solution with a time complexity of O(n), where n is the number of nodes.

Solutions

class Solution {
public:
    int longestPathResult;
    
    int calculate(TreeNode* node, int prevVal) {
        if (node == NULL) {
            return 0;
        }
    
        int leftPath = calculate(node->left, node->val);
        int rightPath = calculate(node->right, node->val);
    
        longestPathResult = max(longestPathResult, leftPath + rightPath);
    
        // Path count is zero if node value doesn't match with its parent value.
        // We include the node itself in the count by adding 1.
        return node->val == prevVal ? max(leftPath, rightPath) + 1 : 0;
    }
    
    int longestUnivaluePath(TreeNode* root) {
        // Initial parent value is set as -1, assuming no node value is negative.
        calculate(root, -1);
            
        return longestPathResult;
    }
};