How do you solve Longest Univalue Path on LeetCode?

Longest Univalue Path (LeetCode #687) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(h) space complexity. Key insight: The longest path can be in any direction, not just through the root.

What is the brute force solution for Longest Univalue Path?

The brute force approach for Longest Univalue Path is Brute Force, with O(n²) time complexity and O(1) space complexity. In the brute force approach, we can explore all possible paths in the tree and check if they have the same value. This means we will traverse the tree multiple times, which can be inefficient. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Longest Univalue Path?

Longest Univalue Path uses the following concepts: Tree, Depth-First Search, Binary Tree. The recommended patterns to study are: Depth-First Search, Tree Traversal.

What are the interview tips for Longest Univalue Path?

Clarify the definition of the path length (number of edges). Think about edge cases like empty trees or trees with only one node. Explain your thought process clearly as you write the code.

What are common mistakes when solving Longest Univalue Path?

Not considering paths that do not pass through the root. Failing to correctly handle null nodes during traversal.

#687

Longest Univalue Path

Medium

TreeDepth-First SearchBinary TreeDepth-First SearchTree Traversal

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(h)

💡

Intuition

Time O(n)Space O(h)

In the optimal solution, we use a single DFS traversal to calculate the longest univalue path. We keep track of the maximum length found during the traversal, which allows us to avoid redundant calculations.

⚙️

Algorithm

3 steps

1Step 1: Initialize a variable to keep track of the maximum length of univalue paths.
2Step 2: Perform a DFS on the tree, checking for univalue paths as we go.
3Step 3: For each node, calculate the lengths of left and right univalue paths and update the maximum length accordingly.

solution.py21 lines

1# Full working Python code
2class TreeNode:
3    def __init__(self, val=0, left=None, right=None):
4        self.val = val
5        self.left = left
6        self.right = right
7
8class Solution:
9    def longestUnivaluePath(self, root: TreeNode) -> int:
10        self.max_length = 0
11        def dfs(node):
12            if not node:
13                return 0
14            left_length = dfs(node.left)
15            right_length = dfs(node.right)
16            left_path = left_length + 1 if node.left and node.left.val == node.val else 0
17            right_path = right_length + 1 if node.right and node.right.val == node.val else 0
18            self.max_length = max(self.max_length, left_path + right_path)
19            return max(left_path, right_path)
20        dfs(root)
21        return self.max_length

ℹ

Complexity note: The time complexity is O(n) because we visit each node exactly once. The space complexity is O(h) due to the recursion stack, where h is the height of the tree.

1The longest path can be in any direction, not just through the root.
2Using DFS allows us to efficiently calculate path lengths without redundant traversals.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.