Longest Univalue Path LeetCode Solution

Last updated on January 13th, 2025 at 09:45 pm

Here, we see a Longest Univalue Path LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.

List of all LeetCode Solution

Topics

Hash Table

Companies

LinkedIn

Level of Question

Medium

Longest Univalue Path LeetCode Solution

Longest Univalue Path LeetCode Solution

1. Problem Statement

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.

Example 1:

Input: root = [5,4,5,1,1,null,5]
Output: 2
Explanation: The shown image shows that the longest path of the same value (i.e. 5).

Example 2:

Input: root = [1,4,5,4,4,null,5]
Output: 2
Explanation: The shown image shows that the longest path of the same value (i.e. 4).

2. Coding Pattern Used in Solution

The coding pattern used in the provided code is Tree Depth First Search (DFS). The code traverses the binary tree recursively using DFS to calculate the longest univalue path (a path where all nodes have the same value). This involves exploring each node’s left and right subtrees and comparing their values with the current node’s value.

3. Code Implementation in Different Languages

3.1 Longest Univalue Path C++

class Solution {
public:
    int longestUnivaluePath(TreeNode* root) {
        int maxlen = 0;
        DFS(root, maxlen);
        return maxlen;
    }
    int DFS(TreeNode* root, int& maxlen){
        if(!root) return 0;
        int left = DFS(root->left, maxlen);
        int right = DFS(root->right, maxlen);
        if(!root->left || root->left->val != root->val) left = 0;
        if(!root->right || root->right->val != root->val) right = 0;
        maxlen = max(maxlen, left + right);
        return max(left, right) + 1;
    }
};

3.2 Longest Univalue Path Java

class Solution 
{
    private int Lpath= 0;
    public int longestUnivaluePath(TreeNode root) 
    {
        pathCalculator(root); 
        return  Lpath;
    }
    private int pathCalculator(TreeNode root)
    {
       if(root == null)
          return 0;
       int left= pathCalculator(root.left);
       int right= pathCalculator(root.right);
       int Tleft= 0, Tright= 0;
       if(root.left != null && root.left.val == root.val)
          Tleft+= left + 1;
       if(root.right != null && root.right.val == root.val)
          Tright+= right+ 1;
       Lpath= Math.max(Lpath, Tleft + Tright);
       return Math.max(Tleft, Tright);
    }
}

3.3 Longest Univalue Path JavaScript

var longestUnivaluePath = function(root) {
   let level = 0 
   function helper( parent, current) {
		if (current === null) return 0
		let left = helper(current.val, current.left)
		let right = helper(current.val, current.right)
		level = Math.max(level, left + right)
		return current.val === parent ? Math.max(left, right) + 1 : 0
   }
   if (root !== null) helper(root.val, root)
   return level
}

3.4 Longest Univalue Path Python

class Solution(object):
    def longestUnivaluePath(self, root):
        def dfs(node, prev_val):
            if node is None:
                return 0
            left=dfs(node.left, node.val)
            right=dfs(node.right, node.val)
            self.max_val=max(self.max_val, left+right)
            if node.val==prev_val:
                return max(left, right)+1
            return 0
        self.max_val=0
        if root is None:
            return 0
        dfs(root,root.val)
        return self.max_val

4. Time and Space Complexity

Time ComplexitySpace Complexity
C++O(n)O(h)
JavaO(n)O(h)
JavaScriptO(n)O(h)
PythonO(n)O(h)

where, n is the number of nodes in the tree and h is the height of the tree.

  • The logic is identical across all four languages, with minor syntactic differences.
  • The recursive DFS approach is efficient for this problem, as it ensures each node is processed only once.
  • The global variable (maxlen in C++, Lpath in Java, level in JavaScript, and self.max_val in Python) is used to track the maximum univalue path length during the traversal.
Scroll to Top