---
tags: data_structure_python
---

# Longest Univalue Path

- https://leetcode.com/problems/longest-univalue-path/

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    
    def longestUnivaluePath(self, root: Optional[TreeNode]) -> int:
        
        def dfs(node):
            if node == None:
                return 0, 0
            
            curr_left, total_left = dfs(node.left)
            curr_right, total_right = dfs(node.right)
            
            same_left = same_right = 0
                
            if node.left != None and node.left.val == node.val: same_left = curr_left + 1
            if node.right != None and node.right.val == node.val: same_right = curr_right + 1
                
            return max(same_left, same_right), max(total_left, total_right, same_left + same_right)
            
        return dfs(root)[1]

- we need to return `max(same_left, same_right)` because otherwise, we will returns 3 edges (which is wrong) instead of 2:

      1
     / 
    1
   / \
  1  1