# 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)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://zedive.gitbook.io/project-l/part-1/basic_data_structure/binary_tree/divide_and_conquer/longest-univalue-path.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.