LeetCode 687 - Longest Univalue Path

Difficulty: 🟡 Medium
Topics: Tree, Depth-First Search, Binary Tree

Solution

Problem Understanding

This problem asks us to find the longest path in a binary tree where every node along the path has the same value. The key detail is that the path length is measured in edges, not nodes. Additionally, the path does not need to pass through the root, meaning the longest valid path can exist entirely inside a subtree.

The input is the root of a binary tree. Each node contains an integer value and pointers to left and right children. Our task is to return an integer representing the maximum number of edges in any path where all connected nodes share the same value.

A path in a binary tree does not have to move only downward. It can go from one child, up to a parent, and then down to another child. For example, a valid path could connect nodes from the left subtree to the right subtree through a common parent, as long as every node on that path has the same value.

The constraints provide important guidance for solution design:

The tree contains at most 10^4 nodes, which is large enough that repeatedly traversing subtrees would likely be too slow.
The tree depth does not exceed 1000, which suggests recursion is safe in most environments, although it approaches Python's recursion limit.
Node values range from -1000 to 1000, but the actual values are not especially important since we only compare equality.

Several edge cases are important to recognize upfront.

An empty tree (root = None) should return 0, because there are no nodes and therefore no edges.

A tree with only one node should also return 0, since a single node contains no edges.

A tree where all values differ should return 0, because no two adjacent nodes can form a univalue path.

A tree where the longest path exists entirely inside a subtree, rather than through the root, can easily break naive implementations that only consider paths involving the root.

Finally, because paths can combine a left branch and right branch through a parent, we must carefully distinguish between:

The best path passing upward to the parent.
The best path found anywhere in the tree.

These are not always the same value.

Approaches

Brute Force Approach

A brute-force solution would consider every node as a potential center of a univalue path and attempt to compute the maximum same-value extension from that node into its descendants.

For each node, we could recursively explore both left and right children to determine how far a same-value chain extends. Then, we would combine those lengths to calculate the longest path passing through the current node.

The issue is redundancy. The same subtree gets recomputed repeatedly from different ancestors. For example, if a subtree rooted at node x is evaluated many times, we repeatedly calculate the same downward path lengths.

Because every node may trigger traversals over large portions of the tree, the overall complexity can degrade to O(N²) in skewed trees.

This approach is correct because it eventually checks every possible univalue path, but it is inefficient for the input size.

Key Insight for an Optimal Solution

The crucial observation is that this problem has an overlapping subproblem structure that fits naturally with postorder depth-first search (DFS).

At every node, we want to know:

"What is the longest downward path starting from this node where all values are the same?"

This information can be computed from its children.

For a given node:

First, recursively compute the longest same-value extension from the left child.
Then compute the same for the right child.
If the child has the same value as the current node, extend that path.
Otherwise, the contribution from that child becomes zero.

The important realization is that:

The value returned upward to the parent must represent only one direction, either left or right, because paths passed upward cannot branch.
But the global answer at a node may combine both left and right contributions, creating a longer path through the current node.

This allows us to process every node exactly once.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(N²)	O(H)	Repeatedly recomputes subtree information
Optimal DFS	O(N)	O(H)	Single postorder traversal, computes answer incrementally

Here, N is the number of nodes and H is the tree height.

Algorithm Walkthrough

Initialize a variable longest_path to 0. This stores the maximum univalue path length found anywhere in the tree.
Define a recursive DFS helper function. The purpose of this function is to return the longest downward same-value path starting from the current node.
If the current node is None, return 0. A null node contributes no path.
Recursively compute the longest same-value paths from the left and right children.
Initialize two variables, left_path and right_path, to 0.
If the left child exists and has the same value as the current node, extend the left contribution by:

left_path = left_length + 1

The +1 represents the edge connecting the current node to the child. 7. Apply the same logic for the right child. 8. At this point, the longest path passing through the current node is:

left_path + right_path

This works because a valid path can go from the left subtree, through the current node, into the right subtree. 9. Update the global maximum:

longest_path = max(longest_path, left_path + right_path) 10. Return the longer of the two directions:

max(left_path, right_path)

This is necessary because a parent can only continue one path upward.

Why it works

The algorithm works because each DFS call computes a precise invariant:

The helper function always returns the longest downward univalue chain beginning at the current node.

Since every node combines information from its children exactly once, every possible univalue path is considered. The global maximum ensures paths entirely inside subtrees are preserved, while returning only the longer branch upward prevents invalid branching in parent paths.

Python Solution

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

from typing import Optional

class Solution:
    def longestUnivaluePath(self, root: Optional[TreeNode]) -> int:
        longest_path = 0

        def dfs(node: Optional[TreeNode]) -> int:
            nonlocal longest_path

            if node is None:
                return 0

            left_length = dfs(node.left)
            right_length = dfs(node.right)

            left_path = 0
            right_path = 0

            if node.left and node.left.val == node.val:
                left_path = left_length + 1

            if node.right and node.right.val == node.val:
                right_path = right_length + 1

            longest_path = max(
                longest_path,
                left_path + right_path
            )

            return max(left_path, right_path)

        dfs(root)
        return longest_path

The implementation follows the postorder DFS strategy described earlier.

The variable longest_path stores the best answer globally. Since the recursive helper only returns a single directional path upward, we need a separate variable to preserve paths that branch through intermediate nodes.

The dfs function first recursively processes the left and right children. This ordering is important because we must already know the best downward same-value paths before computing the current node's contribution.

After receiving results from the children, we determine whether those paths can be extended. If a child's value matches the current node's value, we add one edge to continue the path. Otherwise, the contribution resets to zero.

The global answer is updated using left_path + right_path, because the best path through the current node may combine both directions.

Finally, the function returns the larger of the two branches, since only one direction can continue upward to the parent.

Go Solution

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func longestUnivaluePath(root *TreeNode) int {
    longestPath := 0

    var dfs func(node *TreeNode) int

    dfs = func(node *TreeNode) int {
        if node == nil {
            return 0
        }

        leftLength := dfs(node.Left)
        rightLength := dfs(node.Right)

        leftPath := 0
        rightPath := 0

        if node.Left != nil && node.Left.Val == node.Val {
            leftPath = leftLength + 1
        }

        if node.Right != nil && node.Right.Val == node.Val {
            rightPath = rightLength + 1
        }

        if leftPath+rightPath > longestPath {
            longestPath = leftPath + rightPath
        }

        if leftPath > rightPath {
            return leftPath
        }

        return rightPath
    }

    dfs(root)

    return longestPath
}

The Go implementation mirrors the Python logic closely. Since Go does not support nonlocal, the variable longestPath is captured by the closure naturally.

nil is used instead of None, and explicit pointer checks are necessary before accessing child values.

There are no integer overflow concerns because the maximum number of edges is bounded by the number of nodes, at most 10^4.

Worked Examples

Example 1

Tree:

We process nodes bottom-up.

Node	Right Contribution	Updated Global Max	Return Value
1	0	0	0
1	0	0	0
4	0	0	0
5 (leaf)	0	0	0
5 (right child)	1	1	1
5 (root)	2	2	2

Final answer: 2

The longest path is:

5 -> 5 -> 5

This path contains 2 edges.

Example 2

Tree:

Node	Left Contribution	Right Contribution	Updated Global Max	Return Value
4	0	0	0	0
4	0	0	0	0
4 (parent)	1	1	2	1
5 (leaf)	0	0	2	0
5 (parent)	0	1	2	1
1 (root)	0	0	2	0

Final answer: 2

The longest path is:

4 -> 4 -> 4

with 2 edges.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(N)	Every node is visited exactly once
Space	O(H)	Recursion stack depends on tree height

The algorithm performs a single DFS traversal of the tree. Each node executes only constant work after visiting its children, making the runtime linear in the number of nodes.

The auxiliary space comes from the recursion stack. In a balanced tree this is O(log N), while in the worst case of a completely skewed tree it becomes O(N).

Test Cases

# Helper TreeNode class for testing
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

solution = Solution()

# Example 1
root1 = TreeNode(
    5,
    TreeNode(4, TreeNode(1), TreeNode(1)),
    TreeNode(5, None, TreeNode(5))
)
assert solution.longestUnivaluePath(root1) == 2  # example case with value 5

# Example 2
root2 = TreeNode(
    1,
    TreeNode(4, TreeNode(4), TreeNode(4)),
    TreeNode(5, None, TreeNode(5))
)
assert solution.longestUnivaluePath(root2) == 2  # example case with value 4

# Empty tree
assert solution.longestUnivaluePath(None) == 0  # no nodes

# Single node
root3 = TreeNode(1)
assert solution.longestUnivaluePath(root3) == 0  # one node, no edges

# All nodes same value
root4 = TreeNode(
    1,
    TreeNode(1, TreeNode(1), TreeNode(1)),
    TreeNode(1)
)
assert solution.longestUnivaluePath(root4) == 3  # path crosses root

# No matching adjacent values
root5 = TreeNode(
    1,
    TreeNode(2),
    TreeNode(3)
)
assert solution.longestUnivaluePath(root5) == 0  # no valid path

# Skewed tree with same values
root6 = TreeNode(
    1,
    TreeNode(
        1,
        TreeNode(
            1,
            TreeNode(1)
        )
    )
)
assert solution.longestUnivaluePath(root6) == 3  # chain length

# Longest path inside subtree
root7 = TreeNode(
    1,
    TreeNode(
        2,
        TreeNode(2),
        TreeNode(2)
    ),
    TreeNode(3)
)
assert solution.longestUnivaluePath(root7) == 2  # does not involve root

# Negative values
root8 = TreeNode(
    -1,
    TreeNode(-1),
    TreeNode(-1)
)
assert solution.longestUnivaluePath(root8) == 2  # negative values work

Test	Why
Example 1	Validates standard branching case
Example 2	Verifies longest path inside left subtree
Empty tree	Ensures `None` input returns `0`
Single node	Verifies no edges case
All nodes same value	Tests path crossing root
No matching values	Ensures answer remains `0`
Skewed tree	Tests deep recursive chain
Longest path inside subtree	Confirms root is not required
Negative values	Verifies equality logic works for all integers

Edge Cases

Empty Tree

An empty tree contains no nodes and therefore no edges. A buggy implementation might attempt to recurse without checking for None, causing runtime errors. This implementation handles it safely because the DFS base case immediately returns 0 for null nodes.

Single Node Tree

A tree with only one node may seem like it should return 1, but the problem measures edges, not nodes. Since there are no edges, the correct answer is 0. The implementation naturally handles this because leaf nodes return zero-length paths.

Longest Path Does Not Include Root

A common mistake is assuming the best path must involve the root node. In reality, the optimal path may exist entirely within a subtree. The global longest_path variable prevents this issue by updating the answer at every node, not just the root.

Branching Path Through a Node

Another subtle case occurs when both left and right children match the current node value. The path may extend in both directions through the parent. However, only one branch can continue upward to ancestors. The implementation correctly handles this distinction by updating the global maximum using both sides, while returning only the maximum single branch upward.