Max weight in binary tree
Filed under Amazon
Free read 1 of 3Understand how weights are defined (node value plus all descendants) and confirm constraints on node values.
The question
Given the root of a binary tree, find the maximum weight among all subtrees, where the weight of a subtree is defined as the sum of all node values within that subtree.
Constraints
- The number of nodes in the tree is in the range [1, 10^4].
- -1000 <= Node.val <= 1000
Examples
- Input
- root = [1, 2, 3]
- Output
- 6
- Why
- Subtree sums are: left child = 2, right child = 3, root = 1 + 2 + 3 = 6. Maximum weight is 6.
Approach
Understand how weights are defined (node value plus all descendants) and confirm constraints on node values.
For each node, compute the sum of its entire subtree recursively and track the maximum. This results in O(N^2) time complexity.
Use a post-order DFS traversal. Each recursive call returns the sum of the current subtree and updates a global maximum weight variable. This reduces time complexity to O(N).
Handle empty trees (though constraints say at least 1 node) and trees with all negative values.
Solution
O(N) time, O(H) space
class Solution:
def maxWeight(self, root):
self.max_w = float('-inf')
def dfs(node):
if not node:
return 0
left = dfs(node.left)
right = dfs(node.right)
curr_weight = node.val + left + right
self.max_w = max(self.max_w, curr_weight)
return curr_weight
dfs(root)
return self.max_w
Tips
- What they are testing: Test with negative node values, single-node trees, and left-skewed or right-skewed trees.
- Common mistake: Recomputing subtree sums from scratch for every node instead of using bottom-up post-order traversal.
Related Amazon questions
Collected from public candidate posts and coding forums. Updated Nov 2026.