Practice
Solution
Step 1: Understand problem requirements
The problem requires summing numbers formed by concatenating node values from root to leaf, so partial paths must not be summed prematurely.Step 2: Identify correct traversal pattern
DFS naturally explores root-to-leaf paths, allowing accumulation of the current number and summing only at leaf nodes, ensuring correctness.Final Answer:
Option A -> Option AQuick Check:
DFS accumulates path values correctly and sums only at leaves [OK]
- Summing at non-leaf nodes
- Using BFS without path tracking
Solution
Step 1: Identify handling of empty tree
The code does not check if root is None before starting traversal, which can cause errors or incorrect results.Step 2: Verify other lines
Other lines handle null children safely using heights.get with default 0, and last_visited logic is correct.Final Answer:
Option A -> Option AQuick Check:
Missing early return for empty root causes bug [OK]
- Forgetting to handle empty tree as balanced
- Incorrectly comparing last_visited causing infinite loops
- Not defaulting heights for null children
def maxPathSum(root):
max_sum = float('-inf')
def max_gain(node):
nonlocal max_sum
if not node:
return 0
left_gain = max_gain(node.left)
right_gain = max_gain(node.right)
current_path_sum = node.val + left_gain + right_gain
max_sum = max(max_sum, current_path_sum)
# Bug: returns sum of both left and right gains to parent
return node.val + left_gain + right_gain
max_gain(root)
return max_sum
Solution
Step 1: Understand return value meaning
The function returns the maximum gain from the current node to its parent, which must be a single path (not both children).Step 2: Identify the bug
Returning node.val + left_gain + right_gain sums both children, which is invalid for parent gain; only one child path can be extended.Final Answer:
Option D -> Option DQuick Check:
Return should be node.val + max(left_gain, right_gain) [OK]
- Returning sum of both children gains
- Ignoring negative gains
- Updating max_sum incorrectly
def postorderTraversal(root):
result = []
stack = []
last_visited = None
current = root
while current or stack:
while current:
stack.append(current)
current = current.left
peek_node = stack[-1]
if peek_node.right and last_visited == peek_node.right:
current = peek_node.right
else:
result.append(peek_node.val)
last_visited = stack.pop()
return result
What is the bug in this code?Solution
Step 1: Examine condition for traversing right subtree
Correct logic requires moving to right child if it exists and was not visited yet, so condition must be last_visited != peek_node.right.Step 2: Identify effect of wrong condition
Using last_visited == peek_node.right causes skipping right subtree traversal or infinite loops.Final Answer:
Option B -> Option BQuick Check:
Fixing condition restores correct postorder traversal [OK]
- Using == instead of !=
- Not updating last_visited
- Appending too early
def preorderTraversal(root):
result = []
current = root
while current:
if current.left is None:
result.append(current.val)
current = current.right
else:
predecessor = current.left
while predecessor.right and predecessor.right != current:
predecessor = predecessor.right
if predecessor.right is None:
predecessor.right = current
result.append(current.val)
current = current.left
else:
# Bug here
current = current.right
return result
Solution
Step 1: Identify missing restoration of tree structure
In Morris traversal, after visiting left subtree, predecessor.right must be reset to None to restore original tree.Step 2: Locate missing line
The else block lacks the linepredecessor.right = None, causing the threaded link to persist.Final Answer:
Option A -> Option AQuick Check:
Without resetting, tree remains modified after traversal [OK]
- Forgetting to restore tree structure
- Appending nodes in wrong order
- Incorrect loop conditions
