💡 The algorithm starts with the root and prepares to explore all paths.
traverse
Recurse Left Child of Root
The recursion moves to the left child node with value 2 to compute its max gain.
💡 We must find the max gain from the left subtree before processing the root fully.
Line:left = max(helper(node.left), 0)
💡 Recursion explores left subtree first to gather information for the root's max path calculation.
traverse
Recurse Left Child of Node 2 (None)
Node 2's left child is null, so recursion returns 0 as max gain from this path.
💡 Null children contribute 0 to path sums, preventing negative impact.
Line:if not node:
return 0
💡 Base case of recursion returns 0 for null nodes.
traverse
Recurse Right Child of Node 2 (None)
Node 2's right child is also null, so recursion returns 0 as max gain.
💡 Both children of leaf nodes return 0, so leaf node's gain is its own value.
Line:if not node:
return 0
💡 Leaf nodes have no children, so gains from children are zero.
compare
Calculate Max Gain at Node 2
At node 2, left and right gains are both 0. The max path through node 2 is 2 + 0 + 0 = 2. Update max_sum to 2.
💡 We update global max_sum if current path sum is better.
Line:left = max(helper(node.left), 0)
right = max(helper(node.right), 0)
max_sum = max(max_sum, node.val + left + right)
💡 Leaf node's value can be a candidate for max path sum.
traverse
Return Max Gain from Node 2 to Parent
Return max gain from node 2 to its parent: 2 + max(0, 0) = 2.
💡 This gain will be used by the root node to compute its max path sum.
Line:return node.val + max(left, right)
💡 The recursion returns the best gain path upwards.
traverse
Recurse Right Child of Root
Now recursion moves to the right child node with value 3 to compute its max gain.
💡 We explore the right subtree to gather gains for the root node.
Line:right = max(helper(node.right), 0)
💡 Right subtree is explored after left subtree.
traverse
Recurse Left Child of Node 3 (None)
Node 3's left child is null, so recursion returns 0 as max gain.
💡 Null children return 0 to avoid negative impact on path sums.
Line:if not node:
return 0
💡 Base case applies to right subtree leaves as well.
traverse
Recurse Right Child of Node 3 (None)
Node 3's right child is null, so recursion returns 0 as max gain.
💡 Both children of node 3 return 0, so node 3's gain is its own value.
Line:if not node:
return 0
💡 Leaf node 3 contributes its own value as max gain.
compare
Calculate Max Gain at Node 3
At node 3, left and right gains are 0. Max path through node 3 is 3 + 0 + 0 = 3. Update max_sum to max(2,3) = 3.
💡 Global max_sum updates if current path sum is better.
Line:max_sum = max(max_sum, node.val + left + right)
💡 Max path sum can come from right subtree leaf nodes.
traverse
Return Max Gain from Node 3 to Parent
Return max gain from node 3 to root: 3 + max(0, 0) = 3.
💡 This gain will be used by the root node to compute its max path sum.
Line:return node.val + max(left, right)
💡 Recursion returns best gain path upwards.
compare
Calculate Max Gain at Root Node
At root node 1, left gain is 2, right gain is 3. Max path through root is 1 + 2 + 3 = 6. Update max_sum to max(3,6) = 6.
💡 Root node combines left and right gains to find max path sum including both sides.
Line:max_sum = max(max_sum, node.val + left + right)
💡 Max path sum can pass through root connecting left and right subtrees.
traverse
Return Max Gain from Root to Parent (None)
Return max gain from root to parent (none): 1 + max(2, 3) = 4. This is the max gain root can contribute upwards.
💡 Return value is used if root had a parent; here it ends recursion.
Line:return node.val + max(left, right)
💡 Max gain returned is the best single path from root down.
reconstruct
Final Result Returned
Recursion completes and max_sum holds the maximum path sum 6, which is returned as the final answer.
💡 The global max_sum is the answer to the problem.
Line:helper(root)
return max_sum
💡 The algorithm returns the maximum path sum found in the entire tree.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def maxPathSum(root):
max_sum = float('-inf') # STEP 1
def helper(node):
nonlocal max_sum
if not node: # STEP 3,4,8,9
return 0
left = max(helper(node.left), 0) # STEP 2,7
right = max(helper(node.right), 0) # STEP 7
max_sum = max(max_sum, node.val + left + right) # STEP 5,10,12
return node.val + max(left, right) # STEP 6,11,13
helper(root) # STEP 1
return max_sum # STEP 14
📊
Binary Tree Maximum Path Sum - Watch the Algorithm Execute, Step by Step
Watching the recursion unfold and how the algorithm chooses paths helps you understand the problem's complexity and the importance of ignoring negative gains.
Step 1/14
·Active fill★Answer cell
traverse
node
1
0
2
1
3
2
Result: "-inf"
traverse
1
0
node
2
1
3
2
Result: "-inf"
traverse
1
0
2
1
3
2
Result: "-inf"
traverse
1
0
2
1
3
2
Result: "-inf"
compare
1
0
node
2
1
3
2
Result: 2
move_right
1
0
node
2
1
3
2
Result: 2
traverse
1
0
2
1
node
3
2
Result: 2
traverse
1
0
2
1
3
2
Result: 2
traverse
1
0
2
1
3
2
Result: 2
compare
1
0
2
1
node
3
2
Result: 3
move_left
1
0
2
1
node
3
2
Result: 3
compare
node
1
0
2
1
3
2
Result: 6
move_left
node
1
0
2
1
3
2
Result: 6
record
1
0
2
1
3
2
Result: 6
Key Takeaways
✓ The maximum path sum can include both left and right children of a node, not just a single path downwards.
This is hard to see from code alone because the return value only represents one path, but the global max_sum tracks combined paths.
✓ Negative gains from children are ignored by taking max with 0, ensuring paths only add positive contributions.
This prevents paths with negative sums from reducing the overall maximum, a subtle but crucial insight.
✓ The recursion explores the entire tree bottom-up, computing gains from leaves up to the root, updating max_sum at each node.
Seeing the recursion order and how gains propagate clarifies the algorithm's flow better than reading code.
Practice
(1/5)
1. Consider the following code snippet implementing the optimal DFS approach for the Path Sum problem. Given the tree below and targetSum = 22, what is the return value of the function call hasPathSum(root, 22)?
Tree structure:
- root = TreeNode(5)
- root.left = TreeNode(4)
- root.right = TreeNode(8)
- root.left.left = TreeNode(11)
- root.left.left.left = TreeNode(7)
- root.left.left.right = TreeNode(2)
- root.right.left = TreeNode(13)
- root.right.right = TreeNode(4)
- root.right.right.right = TreeNode(1)
def hasPathSum(root: Optional[TreeNode], targetSum: int) -> bool:
def dfs(node, curr_sum):
if not node:
return False
curr_sum += node.val
if not node.left and not node.right:
return curr_sum == targetSum
return dfs(node.left, curr_sum) or dfs(node.right, curr_sum)
return dfs(root, 0)
easy
A. True
B. False
C. Raises an exception due to null pointer
D. Returns True only if the root value equals targetSum
Solution
Step 1: Trace the path sums
Check root-to-leaf paths:
- 5↔4↔11↔7 = 27
- 5↔4↔11↔2 = 22 (matches targetSum)
- 5↔8↔13 = 26
- 5↔8↔4↔1 = 18
Since one path sums to 22, the function returns True.
Step 2: Confirm code logic
The DFS returns True as soon as it finds the matching path sum at a leaf node.
Final Answer:
Option A -> Option A
Quick Check:
Path 5↔4↔11↔2 sums to 22, so return True [OK]
Hint: Check all root-to-leaf paths, not just partial sums [OK]
Common Mistakes:
Stopping at non-leaf nodes
Ignoring leaf node condition
2. You are given a binary tree and need to determine if it is a mirror of itself (i.e., symmetric around its center). Which approach guarantees an optimal solution that efficiently checks this property by comparing nodes in a mirrored fashion?
easy
A. Use a recursive DFS that simultaneously compares the left subtree of one node with the right subtree of the other node, returning false immediately on mismatch.
B. Perform a level-order traversal and compare nodes at each level from left to right.
C. Traverse the tree in preorder and check if the sequence of node values is a palindrome.
D. Use a brute force approach that generates all subtree permutations and checks for symmetry.
Solution
Step 1: Understand the problem requires mirrored subtree comparison
The problem asks if the tree is symmetric, meaning the left subtree is a mirror reflection of the right subtree.
Step 2: Identify the approach that compares mirrored nodes recursively with early exit
The recursive DFS approach compares left subtree nodes with right subtree nodes in mirrored positions and returns false immediately if any mismatch is found, ensuring efficiency.
Final Answer:
Option A -> Option A
Quick Check:
Mirrored recursive DFS matches problem requirements [OK]
Assuming preorder traversal palindrome check works
Using level-order traversal without mirrored comparison
Trying brute force subtree permutations
3. What is the time complexity of the brute force approach that separately computes height for each node to check if a binary tree is balanced?
medium
A. O(n^2)
B. O(n)
C. O(n log n)
D. O(n h) where h is tree height
Solution
Step 1: Analyze height computation calls
Height is computed recursively for each node, and each height call traverses subtree nodes.
Step 2: Calculate total calls
For n nodes, height is called at each node, and each call can take O(n) in worst case, leading to O(n^2) total time.
Final Answer:
Option A -> Option A
Quick Check:
Repeated height calls cause quadratic time [OK]
Hint: Repeated height calls cause O(n²) time [OK]
Common Mistakes:
Assuming height calls are O(1) leading to O(n) time
Confusing height with depth or tree height h
Thinking O(n log n) due to balanced tree assumption
4. Consider the following buggy code for inverting a binary tree. Which line contains the subtle bug that causes incorrect inversion?
medium
A. Line 3: Swapping children before recursive calls
B. Line 5: Recursive call on right child
C. Line 4: Recursive call on left child
D. Line 2: Missing check for empty tree
Solution
Step 1: Analyze order of operations
The code swaps children before recursively inverting subtrees, which means subtrees are swapped but not inverted themselves.
Step 2: Identify why swapping before recursion is incorrect
Swapping first causes recursion to invert the wrong subtrees, leading to partial or incorrect inversion.
Final Answer:
Option A -> Option A
Quick Check:
Swapping must happen after recursive calls to invert subtrees correctly [OK]
Hint: Swap after recursion, not before, to invert subtrees properly [OK]
Common Mistakes:
Swapping children before recursion
Ignoring null root checks
Confusing left and right subtree recursion order
5. Suppose the problem is modified so that paths can move both downwards and upwards (i.e., any connected path in the tree, not necessarily parent-to-child). Which of the following changes to the algorithm is necessary to correctly count all such paths?
hard
A. Convert the tree to an undirected graph and use DFS from every node with prefix sums, resetting counts after each start.
B. Use the brute force approach checking all paths from every node without prefix sums.
C. Use the same prefix sum DFS approach but run it twice: once from root down and once from leaves up.
D. Modify the prefix sum map to store sums for paths in both directions simultaneously during one DFS.
Solution
Step 1: Understand path direction relaxation
Allowing upward and downward moves means paths are any connected sequences, not just parent-to-child.
Step 2: Model tree as undirected graph and run DFS from every node
To count all paths, treat tree as undirected graph and run DFS from each node, using prefix sums and resetting counts to avoid cross-branch contamination.
Final Answer:
Option A -> Option A
Quick Check:
Undirected DFS from every node with prefix sums counts all connected paths [OK]
Hint: Undirected graph DFS needed for arbitrary path directions [OK]
Common Mistakes:
Trying to reuse one-directional prefix sum DFS without modification
Assuming running DFS twice covers all paths
Trying to store both directions in one prefix sum map
Recommended
Ready to prove it?
Pass the test and this pattern moves unknownstrongwhile earning +1 Grip toward your certificate.