You are given the root of a binary tree, where each node contains an integer value.
A valid path in the tree is a sequence of connected nodes such that:
Return an integer denoting the maximum possible sum of node values among all valid paths.
Example 1:
Input: root = [2,2,1]
Output: 3
Explanation:
2 → 2 is invalid because the value 2 is not distinct.2 → 1, with a sum = 2 + 1 = 3.Example 2:
Input: root = [1,-2,5,null,null,3,5]
Output: 9
Explanation:
3 → 5 → 5 is invalid due to duplicate value 5.1 → 5 → 3, with a sum = 1 + 5 + 3 = 9.Example 3:
Input: root = [4,6,6,null,null,null,9]
Output: 19
Explanation:
6 → 4 → 6 → 9 is invalid because the value 6 appears more than once.4 → 6 → 9, with a sum = 4 + 6 + 9 = 19.
Constraints:
[1, 1000].-1000 <= Node.val <= 1000Problem Overview: You are given a binary tree and need the maximum sum of a path where every node value on that path is distinct. While traversing the tree, the moment a duplicate value appears, that path becomes invalid and must stop. The goal is to explore all valid paths and keep track of the highest sum.
Approach 1: Start DFS From Every Node (Brute Force) (Time: O(n^2), Space: O(h))
The straightforward idea is to treat every node as a potential start of a path. From each node, run a DFS while maintaining a set of values already used in the current path. If the next node's value already exists in the set, the path cannot continue. Otherwise, add the value, update the running sum, and keep exploring left and right children. Because DFS may run from every node and potentially explore a large portion of the tree each time, the worst-case time complexity becomes O(n^2). The auxiliary space comes from the recursion stack and the value set, both bounded by the tree height O(h).
Approach 2: Single DFS with Backtracking + Hash Table (Time: O(n), Space: O(h))
A more efficient strategy performs a single DFS traversal while maintaining the set of values currently on the path. As you move down the tree, insert the node value into a hash table (or set) and add it to the running path sum. If the value already exists, the branch is invalid and you return immediately. Each recursive call explores the left and right children, updating the global maximum whenever a larger valid sum appears. After finishing a node's children, remove the value from the set before returning so other branches can reuse it. This backtracking pattern ensures every node is processed once while still enforcing distinct values along the path.
The key insight is that a binary tree path can be explored incrementally while tracking the current state (visited values and path sum). The hash table provides O(1) average lookup for duplicate detection, which keeps the traversal efficient. Because each node is added and removed from the set once during DFS, the total runtime is O(n), and memory usage is proportional to the recursion depth O(h).
Recommended for interviews: Interviewers typically expect the DFS + hash table approach with backtracking. The brute-force version demonstrates that you understand how to explore paths and enforce uniqueness, but the optimized single traversal shows stronger control over recursion state and pruning. It also keeps the complexity linear, which is the best achievable for scanning all nodes in a tree.
We can treat the tree as an undirected graph, using a hash table g to store the adjacent nodes of each node, where g[node] contains the parent node, left child node, and right child node of node.
We use depth-first search to traverse the tree and build the hash table g. For each node, we add its parent node, left child node, and right child node to g[node].
Next, we use another depth-first search to compute the maximum path sum starting from each node. During this process, we use a hash set vis to record the node values already visited on the current path, ensuring all node values along the path are distinct. For each node, we first check whether it is already in vis; if so, we return 0. Otherwise, we add the node value to vis and compute the path sum starting from that node. We traverse the adjacent nodes in g[node], recursively compute the path sum starting from each adjacent node, and update the current best. Finally, we remove the current node value from vis and return the current node value plus the best path sum.
We perform the above computation for every node in the tree and track the maximum path sum. The final answer is the maximum path sum.
The time complexity is O(n^2), and the space complexity is O(n), where n is the number of nodes in the tree.
Python
Java
C++
Go
TypeScript
| Approach | Time | Space | When to Use |
|---|---|---|---|
| DFS from Every Node (Brute Force) | O(n^2) | O(h) | Useful for understanding path exploration and constraints before optimizing |
| Single DFS + Hash Table Backtracking | O(n) | O(h) | General optimal solution; avoids repeated traversals and prunes duplicate-value paths early |
Practice Maximum Distinct Path Sum in a Binary Tree with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor