LeetCode 3879 - Maximum Distinct Path Sum in a Binary Tree

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

Solution

Problem Understanding

The problem asks us to find the maximum sum of node values along a path in a binary tree such that all values in the path are distinct. The path can start and end at any node, does not need to pass through the root, and must consist of connected nodes. Each node contains an integer, which may be negative, zero, or positive. The input is the root of a binary tree, and the output is a single integer representing the maximum sum of a valid path.

Constraints tell us that the number of nodes is relatively small (1 <= n <= 1000), which allows for a recursive solution with moderate overhead. Node values can be negative (-1000 <= Node.val <= 1000), which means paths with negative sums may need to be ignored if a higher sum is possible elsewhere.

Important edge cases include trees with duplicate values that prevent certain paths from being valid, negative values that could reduce the sum, and paths that consist of a single node.

Approaches

Brute Force

A brute-force approach would be to generate all possible paths in the tree and then filter for those with distinct values. For each valid path, we would calculate the sum and keep track of the maximum. This guarantees correctness but is exponentially slow because the number of possible paths grows rapidly with the number of nodes. Given up to 1000 nodes, this approach is impractical.

Optimal Approach

The key insight is that we can use depth-first search (DFS) with a backtracking hash set to maintain the set of values along the current path. At each node, we explore both left and right subtrees while maintaining a set of already-visited values. If a value is already in the set, we cannot include it in the path. We calculate the maximum sum as the sum of the current node value plus the maximum valid sums from its children. By doing DFS recursively and backtracking properly, we can explore all possible valid paths without explicitly generating them.

The optimal approach leverages a hash set to track distinct values along a path, and recursion ensures we explore all potential paths efficiently. We also maintain a global variable to track the maximum sum found so far.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(2^n)	O(n)	Generates all paths explicitly, checks distinctness
Optimal	O(n * h)	O(n)	DFS with backtracking, exploring each node and subtree once, maintaining hash set for path

Algorithm Walkthrough

Initialize a global variable max_sum to negative infinity to store the maximum sum of valid paths.
Define a recursive DFS function that takes a node and a hash set of values already in the current path.
If the node is None, return a sum of 0.
If the node value is already in the hash set, this path cannot continue through this node, so return 0.
Add the node value to the hash set.
Recursively calculate the maximum path sum in the left subtree and the right subtree, each using a copy of the current set or by proper backtracking.
The maximum sum including this node is the node value plus the maximum sums from left and right subtrees.
Update the global max_sum if this sum is larger.
Remove the current node value from the hash set to backtrack.
Return the maximum sum path that can be extended to parent nodes.

Why it works: The algorithm ensures that at each node, we explore all valid paths that include that node exactly once in any path. By using backtracking, we guarantee that no duplicate values are counted and all combinations are considered. The global max_sum captures the maximum across all starting points and path shapes.

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
class Solution:
    def maxSum(self, root: Optional[TreeNode]) -> int:
        self.max_sum = float('-inf')
        
        def dfs(node, path_set):
            if not node:
                return 0
            if node.val in path_set:
                return 0

            path_set.add(node.val)
            left_sum = dfs(node.left, path_set)
            right_sum = dfs(node.right, path_set)
            current_sum = node.val + left_sum + right_sum
            self.max_sum = max(self.max_sum, current_sum)
            path_set.remove(node.val)

            return node.val + max(left_sum, right_sum)
        
        dfs(root, set())
        return self.max_sum

Explanation: We use a recursive dfs function that takes the current node and a path_set to track distinct values along the path. If a node value is already present, we skip it. We explore left and right subtrees recursively and calculate the maximum sum for paths including the current node. The global variable self.max_sum is updated at every step. Backtracking ensures the set is correctly maintained.

Go Solution

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

    var dfs func(node *TreeNode, pathMap map[int]bool) int
    dfs = func(node *TreeNode, pathMap map[int]bool) int {
        if node == nil {
            return 0
        }
        if pathMap[node.Val] {
            return 0
        }

        pathMap[node.Val] = true
        leftSum := dfs(node.Left, pathMap)
        rightSum := dfs(node.Right, pathMap)
        currentSum := node.Val + leftSum + rightSum
        if currentSum > maxSum {
            maxSum = currentSum
        }
        delete(pathMap, node.Val)

        if leftSum > rightSum {
            return node.Val + leftSum
        }
        return node.Val + rightSum
    }

    dfs(root, make(map[int]bool))
    return maxSum
}

Go-specific notes: We use a map[int]bool instead of a set, since Go does not have a native set type. delete() is used to backtrack the map. All other logic is similar to the Python version.

Worked Examples

Example 1: root = [2,2,1]

Start DFS at root 2. path_set = {2}.
Left child is 2, already in set, return 0.
Right child is 1, not in set, include it: sum = 1.
Current sum at root = 2 + 0 + 1 = 3, update max_sum = 3.

Example 2: root = [1,-2,5,null,null,3,5]

Start DFS at 1. path_set = {1}.
Left child -2: sum = -2, update current = 1 + (-2) = -1 (ignored, max_sum still 0 or updated later)
Right child 5: path_set = {1,5}
Left child 3: path_set = {1,5,3}, sum = 3
Right child 5: duplicate, ignored
Current sum at node 5 = 5 + 3 + 0 = 8, current sum at root = 1 + (-2) + 8 = 7, finally max_sum = 9 through path 1→5→3

Example 3: root = [4,6,6,null,null,null,9]

Path 4→6→9, distinct, sum = 19, this becomes max_sum.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n * h)	Each node is visited once. The hash set operations for checking duplicates take O(h) time in worst case along a path of height h.
Space	O(n)	Recursive call stack can go up to the height of the tree, hash set also stores up to O(n) values.

This complexity is acceptable for n ≤ 1000.

Test Cases

# Provided examples
assert Solution().maxSum(TreeNode(2, TreeNode(2), TreeNode(1))) == 3  # Example 1
assert Solution().maxSum(TreeNode(1, TreeNode(-2), TreeNode(5, TreeNode(3), TreeNode(5)))) == 9  # Example 2
assert Solution().maxSum(TreeNode(4, TreeNode(6), TreeNode(6, None, TreeNode(9)))) == 19  # Example 3

# Edge cases
assert Solution().maxSum(TreeNode(5)) == 5  # Single node
assert Solution().maxSum(TreeNode(1, TreeNode(1), TreeNode(1))) == 1  # All duplicates
assert Solution().maxSum(TreeNode(-1, TreeNode(-2), TreeNode(-3))) == -1  # All negative

Test	Why
Single node	Checks basic case with only one node
All duplicates	Ensures path does not include duplicates
All negative	Ensures algorithm picks maximum even if all values are negative