Embercode: AI-powered software engineer course

1. Why does best start at negative infinity (float('-inf')) and not at 0?

0 is not a valid number in Python.Starting at 0 would allow the empty path, so an all-negative tree would wrongly return 0.max cannot compare a value with 0.The answer must always be positive, so the start must be above zero.

2. What does gain return to its parent?

Only the node's own value.The node's value plus both clipped child gains.The node's value plus the larger of the two clipped child gains.The best candidate found so far in the whole tree.

3. What does this program print? ``

python
class TreeNode:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

best = float('-inf')

def max_path_sum(root):
    global best
    best = float('-inf')
    gain(root)
    return best

def gain(node):
    global best
    if node is None:
        return 0
    left = max(0, gain(node.left))
    right = max(0, gain(node.right))
    through = node.value + left + right
    best = max(best, through)
    return node.value + max(left, right)

root = TreeNode(2, TreeNode(-1, TreeNode(5)), TreeNode(3))
print(max_path_sum(root))

``

45119

4. What does this program print? ``

python
class TreeNode:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

best = float('-inf')

def gain_no_clip(node):
    global best
    if node is None:
        return 0
    left = gain_no_clip(node.left)
    right = gain_no_clip(node.right)
    through = node.value + left + right
    best = max(best, through)
    return node.value + max(left, right)

root = TreeNode(3, TreeNode(-4), TreeNode(1))
gain_no_clip(root)
print(best)

``

401-4

5. True or false: a child whose gain is -5 is clipped to 0, so its parent leaves that branch out of the path. Give the reason.

True, because adding a negative gain can only lower the total, so clipping it to 0 lets the parent skip that branch.False, because clipping changes the node's own value, so the parent must still add the -5.

Maximum path sum