Tree: Depth-First Search - Binary Tree Maximum Path Sum
Consider the following iterative postorder traversal code to compute the maximum path sum in a binary tree. Given the tree below, what is the final value of
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