Practice
Solution
Step 1: Understand the problem constraints
The path can start and end at any node, not necessarily the root or leaf, and node values can be negative.Step 2: Identify the approach that handles all cases optimally
Postorder recursion allows computing maximum gains from left and right subtrees, considering negative values by ignoring negative gains, and updating a global max path sum that includes both children and the current node.Final Answer:
Option A -> Option AQuick Check:
Postorder recursion with global max handles negative values and arbitrary paths [OK]
- Greedy approach fails on negative values and non-root paths
- Enumerating all paths is inefficient and impractical
- BFS does not capture arbitrary path sums
max_sum after the function completes?
Tree structure:
```
1
/
2 3
```
class TreeNode:
def __init__(self, val=0, left=null, right=null):
self.val = val
self.left = left
self.right = right
def maxPathSum(root):
if not root:
return 0
max_sum = float('-inf')
stack = []
node = root
last_visited = null
gain_map = {}
while stack or node:
if node:
stack.append(node)
node = node.left
else:
peek = stack[-1]
if peek.right and last_visited != peek.right:
node = peek.right
else:
left_gain = max(gain_map.get(peek.left, 0), 0)
right_gain = max(gain_map.get(peek.right, 0), 0)
current_path_sum = peek.val + left_gain + right_gain
max_sum = max(max_sum, current_path_sum)
gain_map[peek] = peek.val + max(left_gain, right_gain)
last_visited = stack.pop()
return max_sum
Solution
Step 1: Trace left subtree gain
Node 2 has no children, so left_gain=0, right_gain=0, current_path_sum=2, max_sum updated to 2, gain_map[2]=2.Step 2: Trace root and right subtree
Node 3 has no children, current_path_sum=3, max_sum updated to 3, gain_map[3]=3. For root 1, left_gain=2, right_gain=3, current_path_sum=1+2+3=6, max_sum updated to 6.Final Answer:
Option C -> Option CQuick Check:
Sum of path 2 -> 1 -> 3 is 6 [OK]
- Ignoring one child's gain leads to 5 or 4
- Off-by-one in gain_map updates
- Returning partial sums instead of max path sum
Solution
Step 1: Understand the problem requires the longest path between any two nodes, not necessarily passing through root.
The diameter can be found by checking the sum of left and right subtree heights at every node.Step 2: Recognize that a postorder traversal with recursion and a global variable to track diameter updates at each node ensures all paths are considered.
This approach visits each node once, updating the diameter with left_height + right_height.Final Answer:
Option A -> Option AQuick Check:
Postorder traversal with global diameter update covers all nodes [OK]
- Thinking diameter must pass through root
- Using greedy to pick deeper subtree only
- Confusing diameter with twice height
Solution
Step 1: Understand problem constraints
The problem requires finding the lowest common ancestor efficiently, ideally in O(n) time and O(n) space.Step 2: Evaluate approaches
Brute force (A) is correct but less optimal. Greedy (C) fails because it may pick incorrect ancestors. DP (D) is not applicable here. Building parent pointers and using ancestor sets (B) provides an optimal and clean solution.Final Answer:
Option B -> Option BQuick Check:
Parent pointer + ancestor set approach is standard optimal solution [OK]
- Assuming greedy traversal finds correct LCA
- Using DP where not applicable
- Brute force is optimal
Solution
Step 1: Identify problem with deep recursion
Recursive DFS can cause stack overflow on very deep trees.Step 2: Use iterative BFS with null markers
Iterative BFS avoids recursion stack issues and null markers preserve structure even with duplicates.Step 3: Avoid assumptions about uniqueness or balanced shape
Duplicates require storing all nodes explicitly; balanced assumptions break correctness.Final Answer:
Option A -> Option AQuick Check:
Iterative BFS with null markers handles deep trees and duplicates safely [OK]
- Removing null markers to save space breaks reconstruction
- Using recursion on deep trees causes stack overflow
- Assuming unique values or balanced trees
