You are given a binary tree. Write a function to find the "sum of all nodes" on the…
- User
You are given a binary tree. Write a function to find the "sum of all nodes" on the longest path from root to a leaf. Please write a function that solves this problem, and explain your algorithm.
- Assistant
We are given a binary tree, and we need to find the sum of all nodes on the longest path from root to a leaf. If there are multiple paths with the same maximum length, we need to choose the one with the maximum sum? Actually, the problem says: "sum of all nodes on the longest path from root to a leaf". But note: if there are multiple longest paths (same length) then which one? The problem doesn't specify. We need to clarify. However, typical interpretation: we want the longest path (by number of nodes) and then the sum of nodes on that path. If multiple longest paths, then we have to choose one? The problem says "the longest path", implying there is one? But in a tree, there can be multiple longest paths (same length). So we need to decide: do we take the maximum sum among all longest paths? Or do we take any? The problem statement: "sum of all nodes on the longest path". It doesn't say which one if there are multiple. Usually in such problems, if there are multiple longest paths, we consider the one with the maximum sum. But let's read carefully: "Write a function to find the 'sum of all nodes' on the longest path from root to a leaf." That could be interpreted as: among all root-to-leaf paths, find the ones with maximum length, and then among those, compute the sum of nodes? But then there might be multiple sums? The problem says "the sum", implying one value. So we need to output one integer.
Common approach: We do a DFS (or BFS) to compute for each leaf the length of the path and the sum. Then we want the maximum length, and among those maximum length paths, the maximum sum? Or the minimum? The problem doesn't specify. But typically, when we say "the longest path", if there are multiple, we might need to break ties? Actually, maybe the problem expects: if there are multiple longest paths, then we take the one with the maximum sum? Or maybe it doesn't matter because the sum is computed for each longest path and we pick one? But the problem statement is ambiguous.
Let's look at examples? Not given. So we have to assume something. Perhaps the intended meaning: find the maximum sum among all root-to-leaf paths that have the maximum length? That is a two-step optimization: first maximize length, then among those with maximum length, maximize sum.
Alternatively, it could be: find the path with maximum sum, but only among paths that are longest? That is the same.
However, sometimes problems ask: "find the sum of the nodes on the longest path" meaning if there are multiple longest paths, then we need to choose the one with the maximum sum? Or maybe the problem expects that we return the sum of the nodes on any longest path? But then the sum might not be unique. So to have a unique answer, we need a tie-breaking rule.
Since the problem does not specify, I will assume that if there are multiple longest paths, we want the one with the maximum sum. That is a common variant: "maximum sum path of maximum length".
But let's think: if we simply want the longest path and then its sum, we could do:
For each leaf, compute (length, sum) for the path from root to that leaf. Then find the maximum length. Among all leaves with that maximum length, find the maximum sum.
However, there is another interpretation: maybe we want the sum of all nodes that lie on any longest path? That would be the union of nodes on all longest paths? But the problem says "on the longest path", singular. So it's one path.
So I'll go with: find the root-to-leaf path that has the maximum number of nodes (i.e., maximum depth). If there are multiple such paths, choose the one with the maximum sum of node values. Then return that sum.
But wait: what if the tree is empty? Then there is no leaf. We should handle that. Usually, for an empty tree, we return 0? Or maybe undefined? Let's assume the tree has at least one node? The problem says "binary tree", could be empty? We'll check.
We can design a recursive function that returns two values for each node: (max_depth_from_here, max_sum_for_that_depth) for the subtree rooted at that node? But careful: we are interested in root-to-leaf paths. So for a given node, we consider paths from this node to a leaf in its subtree. But the root is fixed. So we can do:
For a leaf node: depth = 1, sum = node.val. For an internal node: we get from left and right children the maximum depth and the corresponding maximum sum for that depth. But note: the path from the current node to a leaf goes through either left or right. So:
Let left_result = (left_depth, left_sum) for the longest path in left subtree (and maximum sum if multiple). Let right_result = (right_depth, right_sum) for the longest path in right subtree.
Then at current node, if left_depth > right_depth, then the longest path from current node goes left, so total_depth = left_depth + 1, total_sum = left_sum + node.val. If right_depth > left_depth, then go right. If left_depth == right_depth, then we have two paths of same length. We want the one with maximum sum, so we choose the one with maximum of left_sum and right_sum. Then total_depth = left_depth + 1, total_sum = max(left_sum, right_sum) + node.val.
But wait: what if one subtree is empty? Then we should consider only the non-empty one? Actually, if a node has only one child, then the longest path must go through that child. So:
If left is None and right is None: leaf. If left is None and right is not: then we take right. If left is not and right is None: take left. If both: compare.
However, note: if a node has only one child, then the longest path from that node is through that child. But what if the child subtree has multiple paths? We already computed the longest path in that subtree and its sum.
So the recursion:
function dfs(node): if node is None: return (0, 0) ? But careful: for an empty subtree, we don't want to count it. Actually, if node is None, then there is no path. But when we are at a leaf, we return (1, node.val). For a node with one child, say left is None, then we should only consider right. But if we return (0,0) for None, then for a node with one child, we would compare left (0,0) and right (some depth, sum). Then we would choose right because its depth > 0? But 0 vs positive depth? That works. However, if both are None, then we return (1, node.val) for the leaf? Actually, for a leaf, both children are None, so we would get from left and right (0,0). Then we are in the case where left_depth == right_depth (both 0). Then we take max(left_sum, right_sum)=0, and then total_sum = 0 + node.val = node.val, and total_depth = 0+1 = 1. That is correct.
But wait: for a leaf, we have two None children. So we get left_depth=0, right_depth=0. Then we choose max(left_sum, right_sum) which is 0, then add node.val. So that gives (1, node.val). Good.
However, what about a node with one child? Example: node with left child only. Then left returns (some depth, some sum), right returns (0,0). Then left_depth > right_depth (since left_depth at least 1), so we take left. That gives total_depth = left_depth+1, total_sum = left_sum + node.val. Correct.
But what if both children exist and have same depth? Then we take the child with maximum sum. That gives the path with maximum sum among the longest paths from that node.
However, note: we are computing for the subtree rooted at that node, the longest path from that node to a leaf and its sum. But what if the longest path from that node goes through one child, but there is another path of the same length in the other child with a larger sum? We want the maximum sum for the same maximum depth. So we do:
if left_depth > right_depth: choose left. if right_depth > left_depth: choose left. if equal: choose max(left_sum, right_sum).
But wait: what if left_depth == right_depth but left_sum < right_sum? We choose right. That gives the path with maximum sum among the two.
However, what about the case where one subtree has a longer path but a smaller sum? We always prefer longer path, regardless of sum. So that is correct.
So the recursion seems fine.
But note: the problem asks for the sum on the longest path from root to leaf. Our recursion returns for the root the maximum depth and the sum for that depth. But is that the maximum sum among the longest paths? Yes, because at each node we choose the child that gives the longest path, and if both children give the same longest path length, we choose the one with the larger sum. That ensures that for the entire tree, we get the maximum sum among all root-to-leaf paths that have maximum length.
However, consider a tree where there are two paths from root to leaf with same length but different sums. Our algorithm will pick the one with the larger sum because at the root, if left and right subtrees have the same depth, we compare the sums from the subtrees (which are the sums from the child to the leaf, not including the root). Then we add root's value to the larger one. But wait: the sum from the child subtree already includes the child's value and below. So when we add root's value, we are comparing:
path1: root + left_subtree_path (with sum left_sum) path2: root + right_subtree_path (with sum right_sum)
So if left_sum > right_sum, we choose left. That gives the total sum = root.val + left_sum. But note: left_sum already includes the left child's value and all the way to the leaf. So that is correct.
However, what if the two paths have the same depth but one has a larger sum at the child level, but then after adding root's value, they might be equal? That doesn't matter because we are comparing left_sum and right_sum, which are the sums from the child to the leaf. Since root.val is the same, comparing left_sum and right_sum is equivalent to comparing the total sums.
So the algorithm:
Define a helper function that returns (depth, sum) for the longest path from the given node to a leaf, and among those with maximum depth, the maximum sum.
Base case: if node is None, return (0, 0). But wait: if we return (0,0) for None, then for a leaf we get (1, node.val) as above. However, what about a node with one child? That works.
But consider: if a node has only one child, and that child is a leaf? Then the child returns (1, child.val). Then at the node, we get left_depth=1, right_depth=0 (if right is None). Then we choose left, so depth = 1+1=2, sum = child.val + node.val. Correct.
However, what if the tree has negative values? Our algorithm still works because we are comparing sums, and we want maximum sum. But note: if all values are negative, then the longest path might have a very negative sum. But we are still maximizing the sum among the longest paths. So that is fine.
But wait: what if the longest path has a very negative sum, but there is a shorter path with a less negative sum? We don't consider shorter paths because we only consider longest paths.
So the algorithm is:
def longest_path_sum(root): if root is None: return 0 # or maybe we should return 0? But if tree is empty, what is the sum? There is no path. So perhaps we return 0? Or maybe we should return None? The problem doesn't specify. Let's assume the tree is non-empty? But to be safe, we can return 0 for empty tree? Actually, if the tree is empty, there is no root-to-leaf path. So returning 0 might be misleading. But the problem says "binary tree", it might be empty. We'll have to decide. Usually, for an empty tree, we return 0 or some sentinel. Since the problem asks for sum of nodes on the longest path, and there is no path, returning 0 might be acceptable? But if there are negative values, 0 might be larger than the actual sum? That doesn't make sense. So perhaps we should return None or raise an exception? But the function is expected to return an integer. Let's assume the tree is non-empty. If we want to handle empty tree, we can check at the beginning: if root is None: return 0? But that would be inconsistent because there is no path. Alternatively, we can return 0 and say that the sum of an empty path is 0? That might be a convention. I'll assume the tree has at least one node. If not, we return 0.However, our recursive helper returns (0,0) for None. That means for an empty subtree, we consider it as having depth 0 and sum 0. That is convenient because when a node has only one child, we compare (0,0) with the other child's (depth, sum). But if we have a node with no children, then both are (0,0) and we take max(0,0)=0, then add node.val. So that gives (1, node.val). Good.
But what if the tree has only the root? Then we get (1, root.val). That is correct.
However, there is a catch: what if the tree has negative values and we have a choice between two paths with same depth but one has a larger sum? We pick the larger sum. That is what we want.
So the algorithm:
def dfs(node): if node is None: return (0, 0) left_depth, left_sum = dfs(node.left) right_depth, right_sum = dfs(node.right) if left_depth > right_depth: return (left_depth + 1, left_sum + node.val) elif right_depth > left_depth: return (right_depth + 1, right_sum + node.val) else: # equal # choose the maximum sum max_child_sum = max(left_sum, right_sum) return (left_depth + 1, max_child_sum + node.val)Then call dfs(root) and return the sum part.
But wait: what if both children are None? Then left_depth=0, right_depth=0, and max_child_sum=0, so we return (1, node.val). Correct.
However, what if one child is None and the other is not? Then we get one depth=0 and the other depth>0. We choose the one with larger depth. That is correct.
But what about the case where both children exist and have the same depth, but one has a larger sum? We choose the larger sum. That gives the maximum sum among the longest paths from this node.
However, is this greedy choice at each node optimal for the entire tree? Yes, because the longest path from the root must go through either the left or right subtree. And if both subtrees have the same maximum depth, then the longest path from the root will have the same length regardless of which subtree we take. So we can choose the subtree that gives the maximum sum for that depth. That will give the maximum sum among all longest paths from the root.
So the algorithm seems correct.
But let's test on a simple tree:
root / \ l r / \ \ a b cSuppose all values are 1. Then the longest path length is 3 (root->l->a or root->l->b or root->r->c). But note: from root, left subtree has depth 2 (from l to a or b) and right subtree has depth 2 (from r to c). So at root, left_depth=2, right_depth=2. Then we compare left_sum and right_sum. The left subtree: for node l, it has two leaves a and b. Both paths from l have depth 1 and sum 1 (from a or b) plus l's value? Wait, let's compute:
For leaf a: depth=1, sum=1. For leaf b: depth=1, sum=1. At node l: left_depth=1, right_depth=1, so max_child_sum = max(1,1)=1, then depth=1+1=2, sum=1+ l.val (which is 1) -> sum=2. Similarly for node r: it has only one child c, so at r: left_depth=0, right_depth=1 (from c), so it takes right: depth=1+1=2, sum= c.val (1) + r.val (1) = 2. Then at root: left_depth=2, left_sum=2; right_depth=2, right_sum=2. Then max_child_sum = max(2,2)=2, then depth=2+1=3, sum=2 + root.val (1) = 3.
So we get sum=3. But note: there are three paths of length 3, each with sum 3 (since all nodes are 1). So that is correct.
Now, what if the values are different? Example:
root(1) / \ l(2) r(3) / \ \ a(4) b(5) c(6)The longest paths: root->l->a: sum=1+2+4=7, length=3. root->l->b: sum=1+2+5=8, length=3. root->r->c: sum=1+3+6=10, length=3.
So the longest length is 3, and the maximum sum among these is 10 (from root->r->c). Let's see what our algorithm does:
For a: (1,4) For b: (1,5) For l: left_depth=1, left_sum=4; right_depth=1, right_sum=5. Since equal depth, we take max(4,5)=5. Then l: depth=1+1=2, sum=5+2=7. For c: (1,6) For r: left_depth=0, right_depth=1, so take right: depth=1+1=2, sum=6+3=9. For root: left_depth=2, left_sum=7; right_depth=2, right_sum=9. Equal depth, take max(7,9)=9. Then root: depth=2+1=3, sum=9+1=10.
That gives 10, which is correct.
What if the longest path is not unique in length but we have a shorter path with a larger sum? Example:
root(1) / \ l(2) r(3) / \ a(4) c(5) /d(6)
Paths: root->l->a: length=3, sum=1+2+4=7. root->l->a->d: length=4, sum=1+2+4+6=13. root->r->c: length=3, sum=1+3+5=9.
The longest length is 4 (only one path). So we want sum=13.
Let's compute: d: (1,6) a: left_depth=1 (from d), left_sum=6; right_depth=0. So a: depth=1+1=2, sum=6+4=10. l: left_depth=2 (from a), left_sum=10; right_depth=0. So l: depth=2+1=3, sum=10+2=12. c: (1,5) r: left_depth=0, right_depth=1, so r: depth=1+1=2, sum=5+3=8. root: left_depth=3, left_sum=12; right_depth=2, right_sum=8. So left_depth > right_depth, so we take left: depth=3+1=4, sum=12+1=13. Correct.
So the algorithm works.
However, note: what if the tree has negative values and the longest path has a negative sum, but there is a shorter path with a positive sum? We still take the longest path even if its sum is negative. That is what the problem asks: the sum of all nodes on the longest path. So we don't care about the sum being maximum among all paths, only among the longest ones.
So our algorithm is:
def sum_of_longest_path(root): def dfs(node): if not node: return (0, 0) left_depth, left_sum = dfs(node.left) right_depth, right_sum = dfs(node.right) if left_depth > right_depth: return (left_depth+1, left_sum + node.val) elif right_depth > left_depth: return (right_depth+1, right_sum + node.val) else: # same depth, choose the child with larger sum max_child_sum = max(left_sum, right_sum) return (left_depth+1, max_child_sum + node.val) _, total_sum = dfs(root) return total_sumBut wait: what if the tree is empty? Then dfs(None) returns (0,0) and we return 0. But is that acceptable? For an empty tree, there is no root-to-leaf path. So returning 0 might be considered as the sum of an empty path? Or we might want to return 0 as a convention. The problem does not specify. We can add a check at the beginning: if root is None: return 0. But our dfs already handles that because if root is None, we call dfs(None) and get (0,0). So we return 0. That seems fine.
However, what if the tree has only one node? Then dfs returns (1, node.val). That is correct.
But note: the problem says "from root to a leaf". So if the tree has only one node, that node is both root and leaf. So the path has one node.
So the code seems correct.
However, there is a nuance: the problem says "binary tree", not necessarily full. Our algorithm handles missing children correctly.
Let's write the function accordingly.
But wait: what if the tree has multiple longest paths and we want the one with maximum sum? Our algorithm does that.
However, consider this: what if at a node, the two subtrees have the same depth but one subtree has a path with a larger sum, but that larger sum might come from a path that is not the longest in that subtree? But we are storing for each subtree the maximum depth and the maximum sum for that maximum depth. So in the subtree, we already have the longest path and its sum. So when we compare at the parent, we are comparing the sums of the longest paths in the subtrees. That is correct.
Example: left subtree: longest path length = 3, sum = 10; another path of length 3 with sum = 12? But we store the maximum sum for the maximum depth. So if there are two paths of length 3, we take the one with sum 12. So at the parent, we use 12. That is what we want.
So the recursive function returns for a subtree: (max_depth, max_sum_for_that_depth). That is exactly what we need.
Therefore, the algorithm is as above.
Complexity: We visit each node exactly once, so O(n) time and O(h) space for recursion stack, where h is the height.
Let's code accordingly.
But wait: what if the tree has only left children? Then we always go left, and that is fine.
Edge: if the tree is a linked list (only one child at each node), then we go straight to the leaf.
So we are good.
However, note: the problem says "sum of all nodes on the longest path". So we are summing the node values. We assume the node values are integers (could be negative).
We'll implement accordingly.
Let me write the function in Python.
We assume the tree node has attributes: val, left, right.
Code:
def sum_of_longest_path(root): if root is None: return 0 def dfs(node): if node is None: return (0, 0) left_depth, left_sum = dfs(node.left) right_depth, right_sum = dfs(node.right) if left_depth > right_depth: return (left_depth + 1, left_sum + node.val) elif right_depth > left_depth: return (right_depth + 1, right_sum + node.val) else: # both same depth max_child_sum = max(left_sum, right_sum) return (left_depth + 1, max_child_sum + node.val) _, total_sum = dfs(root) return total_sumBut wait: what if the tree has negative values and we have two subtrees with same depth but one has a larger sum? We take the larger sum. That is correct.
However, what if both subtrees have same depth and same sum? Then it doesn't matter which we choose, the sum will be the same.
So this should work.
Let me test on the examples above.
Example 1: all ones, we got 3.
Example 2: we got 10.
Example 3: we got 13.
Now, what about a tree where the longest path is not unique and we have to choose the one with maximum sum? Our algorithm does that.
But what if there is a tie in depth and also in sum? Then we return that sum.
So I think it's correct.
However, note: the problem says "the longest path". If there are multiple longest paths, we are returning the sum of the one with the maximum sum. That is a reasonable interpretation. If the problem intended to return the sum of any longest path, then we could have returned the sum of the first one we find? But then the answer would not be deterministic. So I think the intended meaning is to return the maximum sum among the longest paths.
Therefore, I'll go with this.
But wait: what if the tree has only one node? Then we return that node's value.
What if the tree is empty? We return 0. But maybe we should return None or raise an error? Since the problem says "binary tree", it might be empty. Let's assume the input can be empty. We return 0 for empty. That is a common convention: the sum of an empty set is 0.
Alternatively, we could return 0 for empty tree because there are no nodes, so the sum is 0. But is an empty tree considered to have a root-to-leaf path? No. So maybe we should return 0? Or maybe we should return None? The problem says "sum of all nodes on the longest path". If there is no path, then the sum is 0? That doesn't sound right. But in programming problems, often for empty tree we return 0 or -infinity? Since the problem doesn't specify, I'll return 0 for empty tree.
We can change the top-level function:
if root is None: return 0But our dfs already returns (0,0) for None, and if root is None we call dfs(None) and get (0,0) and return 0. So it's the same.
However, what if the tree has negative values and we return 0 for empty tree? That might be larger than the actual sum of a non-empty tree? But that's okay because we are not comparing. For an empty tree, there is no path, so returning 0 might be considered as the sum of an empty path. But the problem says "from root to leaf", so if there is no root, there is no such path. So returning 0 is a bit arbitrary. But let's stick with it.
Alternatively, we can return None for empty tree? But the return type is integer. So we return 0.
I think it's acceptable.
Let's write the code accordingly.
But wait: what if the tree has all negative values? Then the longest path might have a very negative sum. Our algorithm will still return that negative sum. That is correct.
Example: root = -1 left = -2 (leaf) right = -3 (leaf)
The longest paths: both have length 2. The sums: root->left: -1-2=-3; root->right: -1-3=-4. So we should return -3 (the maximum among the longest). Let's see:
left leaf: (1, -2) right leaf: (1, -3) root: left_depth=1, right_depth=1, so max_child_sum = max(-2, -3) = -2. Then root: depth=1+1=2, sum=-2 + (-1) = -3. Correct.So it works.
Therefore, the algorithm is correct.
Now, we can also do it without returning depth and sum separately? We could compute the maximum depth first, then do another pass to compute the maximum sum among paths of that depth. But that would be two passes. Our method does it in one pass.
So we'll go with the above.
Let me write the function with proper docstring.
However, note: the above algorithm assumes that the tree nodes have integer values. We'll assume that.
Code:
class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right def sum_of_longest_path(root: TreeNode) -> int: if root is None: return 0 def dfs(node): if node is None: return (0, 0) left_depth, left_sum = dfs(node.left) right_depth, right_sum = dfs(node.right) if left_depth > right_depth: return (left_depth + 1, left_sum + node.val) elif right_depth > left_depth: return (right_depth + 1, right_sum + node.val) else: max_child_sum = max(left_sum, right_sum) return (left_depth + 1, max_child_sum + node.val) _, result = dfs(root) return resultBut wait: what if the tree has only one child at some node? We already handled.
Let's test on a tree with only root: dfs(root): left_depth=0, right_depth=0 -> else: max_child_sum=0, return (1, root.val). Correct.
So I think it's good.
However, there is a subtlety: what if the tree has a node with one child, and that child subtree has multiple paths? We already take the longest path in that subtree and its sum. So that is correct.
One more test:
root(1) \ r(2) \ c(3)Path: root->r->c: length=3, sum=1+2+3=6.
Compute: c: (1,3) r: left_depth=0, right_depth=1 -> take right: (1+1=2, 3+2=5) root: left_depth=0, right_depth=2 -> take right: (2+1=3, 5+1=6). Correct.
So it works.
Therefore, the function is as above.
But note: the problem says "write a function that solves this problem, and explain your algorithm." So we need to provide the explanation as well.
Explanation:
We use a post-order DFS traversal. For each node, we compute two values: the length of the longest path from that node to a leaf in its subtree, and the maximum sum among all such longest paths.
For a leaf node, the longest path is just the node itself, so length=1 and sum=node.val.
For an internal node, we get the (depth, sum) pairs from left and right subtrees. - If one subtree has a longer path, we extend that path by the current node. - If both subtrees have paths of the same maximum length, we choose the one with the larger sum and extend it by the current node.
This ensures that at the root, we get the maximum depth (which is the length of the longest root-to-leaf path) and the maximum sum among all root-to-leaf paths of that length.
The algorithm runs in O(n) time and O(h) space, where n is the number of nodes and h is the height of the tree.
We return the sum part from the root.
That's it.
However, note: what if the tree has only one node? Then we return that node's value.
Let me write the code accordingly.
But wait: what if the tree has negative values and we have a choice between two subtrees with same depth but one has a larger sum? We take the larger sum. That is correct.
So the code is ready.
But note: the problem says "sum of all nodes on the longest path". What if there are multiple longest paths with the same sum? Then we return that sum. It's the same.
So we are done.
However, one more edge: what if the tree is None? We return 0. But maybe we should return 0 only if the tree is empty? That's what we do.
Let's write the final function.
But wait: what if the tree has a node with value 0? That's fine.
So I think it's correct.
However, let's consider a tree where the longest path is not through the child with the maximum sum? But we are only comparing the sums of the longest paths in the subtrees. Since we are forced to take a longest path (because we want the longest from the current node), we must take a child that gives the maximum depth. If both children give the same maximum depth, then we have a choice, and we take the one with the larger sum. That is optimal for the sum given that we are constrained to the longest path.
So the greedy choice at each node is optimal for the overall problem because the longest path from the root must go through a child that provides the maximum depth. And if there are multiple children providing the same maximum depth, we choose the one that gives the maximum sum for that depth, which will lead to the maximum sum for the entire path (since the root's value is added anyway).
Therefore, the algorithm is correct.
I'll write the code accordingly. To solve this problem, we need to find the sum of all nodes on the longest path from the root to any leaf in a binary tree. If there are multiple paths with the same maximum length, we choose the one with the maximum sum. The solution involves a post-order depth-first search (DFS) traversal that computes for each node the length of the longest path from that node to a leaf and the corresponding maximum sum among such paths.
Approach
- Problem Analysis: The task is to identify the longest root-to-leaf path (by number of nodes) and return the sum of node values along that path. If multiple paths have the same maximum length, the path with the highest sum is selected.
- Intuition: For any node, the longest path to a leaf must go through either its left or right subtree. We can recursively compute the longest path and its sum for each subtree, then combine these results at the current node.
- Algorithm Selection:
- Use a helper function
dfs(node)that returns a tuple(depth, sum):depth: length of the longest path fromnodeto a leaf.sum: maximum sum among all paths of thatdepth.
- Base Case: If
nodeisNone, return(0, 0)(no path). - Recursive Step:
- Recursively get
(left_depth, left_sum)from left subtree and(right_depth, right_sum)from right subtree. - If
left_depth > right_depth, the longest path goes left: return(left_depth + 1, left_sum + node.val). - If
right_depth > left_depth, the longest path goes right: return(right_depth + 1, right_sum + node.val). - If depths are equal, choose the subtree with the larger sum: return
(left_depth + 1, max(left_sum, right_sum) + node.val).
- Recursively get
- Use a helper function
- Complexity Analysis:
- Time Complexity: O(n) – each node is visited exactly once.
- Space Complexity: O(h) – recursion stack uses space proportional to the tree height (worst-case O(n) for a skewed tree).
Solution Code
class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right def sum_of_longest_path(root: TreeNode) -> int: if root is None: return 0 def dfs(node): if node is None: return (0, 0) left_depth, left_sum = dfs(node.left) right_depth, right_sum = dfs(node.right) if left_depth > right_depth: return (left_depth + 1, left_sum + node.val) elif right_depth > left_depth: return (right_depth + 1, right_sum + node.val) else: max_child_sum = max(left_sum, right_sum) return (left_depth + 1, max_child_sum + node.val) _, total_sum = dfs(root) return total_sumExplanation
- Base Handling: If the tree is empty (
root is None), return0(no path exists). - DFS Helper: The
dfsfunction computes for each node:- Depth: Longest path length from the node to any leaf.
- Sum: Maximum sum among all paths of that length.
- Recursive Combination:
- Compare depths from left and right subtrees.
- Prefer the subtree with greater depth; if depths are equal, prefer the one with larger sum.
- Extend the chosen path by adding the current node's value.
- Result Extraction: After processing the root, return the sum from the tuple, which represents the sum of the longest path (with maximum sum in case of ties).
This approach efficiently computes the desired result in a single pass, leveraging post-order traversal to build solutions from the bottom up.