We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Longest Univalue Path

Difficulty: Medium

Problem Description

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.

Key Insights

  • The path can start and end at any node, not necessarily passing through the root.
  • A univalue path can be formed by considering both left and right child nodes that have the same value as the current node.
  • We can use Depth-First Search (DFS) to traverse the tree and calculate the longest univalue path.

Space and Time Complexity

Time Complexity: O(N), where N is the number of nodes in the tree, since we visit each node once. Space Complexity: O(H), where H is the height of the tree, due to the recursion stack in DFS.

Solution

To solve the problem, we can use a Depth-First Search (DFS) approach. We will traverse the tree recursively and calculate the length of the univalue paths for both the left and right children of each node. If a child node has the same value as the current node, we can extend the univalue path by one edge. We will keep track of the maximum length found during the traversal.

  1. We define a helper function that takes a node as input and returns the length of the longest univalue path that extends from that node.
  2. As we traverse, we compare the current node's value with its children’s values.
  3. Update the maximum path length found so far whenever we calculate a new path length.

Code Solutions

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: TreeNode) -> int:
        self.max_length = 0
        
        def dfs(node):
            if not node:
                return 0
            
            left_length = dfs(node.left)
            right_length = dfs(node.right)
            
            # Lengths of paths that can be extended
            left_path = left_length + 1 if node.left and node.left.val == node.val else 0
            right_path = right_length + 1 if node.right and node.right.val == node.val else 0
            
            # Update maximum length found
            self.max_length = max(self.max_length, left_path + right_path)
            
            # Return the longest path extending from the current node
            return max(left_path, right_path)
        
        dfs(root)
        return self.max_length
← Back to All Questions