> For the complete documentation index, see [llms.txt](https://zedive.gitbook.io/project-l/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://zedive.gitbook.io/project-l/part-1/basic_data_structure/binary_tree/divide_and_conquer/longest-univalue-path.md).

# Longest Univalue Path

## Question ([LC.687](https://leetcode.com/problems/longest-univalue-path/))

> Given the root of a binary tree, find the length of the longest univalue path. An univalue path is a path between any two nodes where all the nodes have the same value. The length of the path is the number of edges. 

## Example 

```
Input: [5,4,5,1,1,5]
Output: 2

Input: [1,4,5,4,4,5]
Output: 2

Input: [1,null,1,1,1,1,1,1]
Expected: 4
```

<div align="left"><img src="/files/-MPgseRxMJkZhSq80sDx" alt=""></div>

The last example is a good one. Same value nodes can only connect in one direction but not both.&#x20;

## Analysis&#x20;

Divide and conquer is build for these path related problems. The return type needs to hold a couple info including the longest univalue path so far, the current univalue path, and the current value.&#x20;

## Code&#x20;

```python
class Solution:
    
    class ResultType:
        def __init__(self, curVal, curLen, maxLen):
            self.curVal = curVal
            self.curLen = curLen
            self.maxLen = maxLen
    
    
    def longestUnivaluePath(self, root: TreeNode) -> int:
        if root is None:
            return 0
        
        return self.pathHelper(root).maxLen - 1
        
    
    def pathHelper(self, node: TreeNode) -> ResultType:
        
        # base 
        if node is None:
            return self.ResultType(None, 0, 0)
        
        # divide 
        leftTree = self.pathHelper(node.left)
        rightTree = self.pathHelper(node.right)
        
        # merge 
        
        # compute current length 
        
        curLen = 1
        combinedLen = 1
        
        if leftTree.curVal == node.val:
            curLen = max(curLen, leftTree.curLen + 1)
            combinedLen += leftTree.curLen
        
        if rightTree.curVal == node.val:
            curLen = max(curLen, rightTree.curLen + 1)
            combinedLen += rightTree.curLen
        
        
        # compute max length 
        
        maxLen = max(combinedLen, leftTree.maxLen, rightTree.maxLen)
        
        return self.ResultType(node.val, curLen, maxLen)
```

## Complexity&#x20;

Time O(n)&#x20;

Space O(n)