Longest Univalue Path — Solution in Python, Java & C++
Longest Univalue Path solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Longest Univalue Path is a medium coding problem on depth-first search and trees, asked in Amazon and Google interviews.
- Difficulty: Medium
- Topics: Depth-First Search, Trees
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given the root of a binary tree, return the length of the longest path in which every node has the same value. The path may or may not pass through the root, and it may bend at one node (go up through it from one child and down into the other).
The length of a path is the number of edges on it.
Example 1
Input: root = [5,4,5,1,1,null,5]
Output: 2
Explanation: The path 5 → 5 → 5 down the right side has two edges.
Example 2
Input: root = [1,4,5,4,4,null,5]
Output: 2
Explanation: The path 4 – 4 – 4 runs through the left child of the root and both its children: two edges.
Example 3
Input: root = []
Output: 0
Explanation: An empty tree has no path.
Constraints
The number of nodes in the tree is in the range [0, 10^4]-1000 <= Node.val <= 1000The depth of the tree will not exceed 1000
Hints for Longest Univalue Path
Hint 1
Every path has one highest node. At that node, the path is an arm going down the left plus an arm going down the right.
Hint 2
Compute, for every node, the longest downward arm of equal values starting there. A child extends the arm only if its value equals the node's.
Hint 3
In one post-order DFS: return the longer arm to the parent, but update the global answer with the sum of both arms.
How to solve Longest Univalue Path
Like the diameter of a tree, but an edge only counts when both its ends hold the same value. A post-order DFS returns, for each node, the longest single downward arm of equal values, and combines the two arms at the node to try the bent path.
Approach
arm(node): return 0 for null; otherwise computel = arm(left)andr = arm(right)first.al = l + 1if the left child exists and has the same value asnode, else 0;arlikewise on the right.- Update
best = max(best, al + ar)— the path that bends atnode. - Return
max(al, ar): a path continuing upward can use only one side.
Why it works
Any univalue path has a unique topmost node, and from it the path is two downward arms of that value (either possibly empty). al and ar are exactly the longest such arms, so al + ar is the longest path topped at that node, and the maximum over all nodes is the answer.
Complexity
- Time —
O(n) - Space —
O(h) for the recursion
Pitfalls
- Count edges, not nodes — a single node is a path of length 0.
- Recurse into a child even when its value differs: a longer path may lie entirely below it.
- Return only one arm upward; returning
al + arwould let a path fork.
Reference solution
Python
from typing import Optional
def longestUnivaluePath(root: Optional[TreeNode]) -> int:
best = 0
def arm(node):
nonlocal best
if node is None:
return 0
l = arm(node.left)
r = arm(node.right)
al = l + 1 if node.left is not None and node.left.val == node.val else 0
ar = r + 1 if node.right is not None and node.right.val == node.val else 0
best = max(best, al + ar)
return max(al, ar)
arm(root)
return bestJava
public static int longestUnivaluePath(TreeNode root) {
int[] best = new int[1];
arm(root, best);
return best[0];
}
static int arm(TreeNode node, int[] best) {
if (node == null) return 0;
int l = arm(node.left, best), r = arm(node.right, best);
int al = node.left != null && node.left.val == node.val ? l + 1 : 0;
int ar = node.right != null && node.right.val == node.val ? r + 1 : 0;
best[0] = Math.max(best[0], al + ar);
return Math.max(al, ar);
}C++
int univalueArm(TreeNode* node, int& best);
int longestUnivaluePath(TreeNode* root) {
int best = 0;
univalueArm(root, best);
return best;
}
int univalueArm(TreeNode* node, int& best) {
if (!node) return 0;
int l = univalueArm(node->left, best), r = univalueArm(node->right, best);
int al = node->left && node->left->val == node->val ? l + 1 : 0;
int ar = node->right && node->right->val == node->val ? r + 1 : 0;
best = max(best, al + ar);
return max(al, ar);
}JavaScript
var longestUnivaluePath = function(root) {
var best = 0;
var arm = function(node) {
if (node === null) return 0;
var l = arm(node.left), r = arm(node.right);
var al = node.left !== null && node.left.val === node.val ? l + 1 : 0;
var ar = node.right !== null && node.right.val === node.val ? r + 1 : 0;
if (al + ar > best) best = al + ar;
return Math.max(al, ar);
};
arm(root);
return best;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 201 depth-first search problems · the whole catalogue
Learn the technique: Depth-First Search (DFS) · Binary Trees and Tree Traversals