Skip to main content
Talentd

Maximum Distinct Path Sum in a Binary Tree - Solution & Explanation

MediumPremiumFree on FleetCode13 min read
Practice this problem

Problem Statement

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:

  • The path can start and end at any node in the tree.
  • The path does not need to pass through the root.
  • All node values along the path are distinct.

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:

  • The path 2 → 2 is invalid because the value 2 is not distinct.
  • The maximum-sum valid path is 2 → 1, with a sum = 2 + 1 = 3.

Example 2:

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

Output: 9

Explanation:

  • The path 3 → 5 → 5 is invalid due to duplicate value 5.
  • The maximum-sum valid path is 1 → 5 → 3, with a sum = 1 + 5 + 3 = 9.

Example 3:

ā€‹ā€‹ā€‹ā€‹ā€‹ā€‹ā€‹

Input: root = [4,6,6,null,null,null,9]

Output: 19

Explanation:

  • The path 6 → 4 → 6 → 9 is invalid because the value 6 appears more than once.
  • The maximum-sum valid path is 4 → 6 → 9, with a sum = 4 + 6 + 9 = 19.

 

Constraints:

  • The number of nodes in the tree is in the range [1, 1000].
  • -1000 <= Node.val <= 1000ā€‹ā€‹ā€‹ā€‹ā€‹ā€‹ā€‹

Approach Overview

Problem 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.

Solution

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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor ā†’

Detailed Complexity Analysis

ApproachTimeSpaceWhen 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 BacktrackingO(n)O(h)General optimal solution; avoids repeated traversals and prunes duplicate-value paths early

Frequently Asked Questions

Is Maximum Distinct Path Sum in a Binary Tree easy or hard?
This problem is generally classified as Medium difficulty. The traversal itself is standard DFS, but the challenge is managing path state correctly with backtracking while enforcing the distinct-value constraint. Candidates comfortable with recursion and hash sets typically solve it within typical interview time limits.
Maximum Distinct Path Sum in a Binary Tree Python/Java solution
Most implementations follow the same DFS + backtracking pattern. Maintain a global or external variable for the maximum sum, pass the current sum and a hash set into recursive calls, and remove values when returning from recursion. The logic translates directly across Python, Java, C++, Go, and TypeScript.
How to solve Maximum Distinct Path Sum in a Binary Tree in O(n)?
Run a single DFS traversal while maintaining a hash set of values on the current path and a running path sum. When visiting a node, check if its value already exists in the set. If it does, stop exploring that branch; otherwise add the value, update the sum, explore children, then remove the value during backtracking. This ensures each node contributes to the computation only once.
What is the best approach for Maximum Distinct Path Sum in a Binary Tree?
The most efficient approach uses Depth-First Search with a hash set to track values currently present in the path. During traversal, if a value already exists in the set, the branch is stopped because the path would violate the distinct constraint. With backtracking, each node is added and removed exactly once, producing an O(n) time solution with O(h) recursion space.
Is Maximum Distinct Path Sum in a Binary Tree asked at Google/Amazon/Meta?
Tree traversal problems combined with hash-based constraints appear frequently in interviews at companies like Google, Amazon, and Meta. Variations include longest unique path, path sum constraints, and tree DFS with state tracking. This problem tests recursion design, pruning logic, and efficient use of hash structures.
What data structure is used in Maximum Distinct Path Sum in a Binary Tree?
The core data structure is a hash set or hash table used to store values currently present in the DFS path. It enables constant-time duplicate detection while traversing the binary tree. The algorithm also relies on recursion or an explicit stack to perform depth-first traversal.
What is the time complexity of Maximum Distinct Path Sum in a Binary Tree?
The optimal DFS + hash table solution runs in O(n) time where n is the number of nodes in the tree. Each node is visited once, and hash set operations such as insert, lookup, and delete take O(1) on average. Space complexity is O(h) due to recursion stack and the set storing values along the current path.

Ready to solve this problem?

Practice Maximum Distinct Path Sum in a Binary Tree with our built-in code editor and test cases.

Practice on FleetCode