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
Level of Question
Medium

Longest Univalue Path LeetCode Solution
Table of Contents
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 Complexity | Space Complexity | |
C++ | O(n) | O(h) |
Java | O(n) | O(h) |
JavaScript | O(n) | O(h) |
Python | O(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, andself.max_val
in Python) is used to track the maximum univalue path length during the traversal.