💡 Problem Formulation: The ‘maximum path sum’ in a binary tree is the greatest sum of node values that can be obtained by traversing a path from any node to any other node, where each node can only be used once in the path. The binary tree nodes have a ‘value’, and two children ‘left’ and ‘right’, which can be either a subtree or ‘None’ if there is no child. The task is to write a Python function that takes the root of this binary tree and returns its maximum path sum.
Method 1: Recursion with Global Variable
This method involves writing a recursive helper function that updates a global variable to track the maximum path sum found so far. The function computes the maximum contributions from each child and adds the current node’s value to the greater of the two contributions. The function does not return maximum sums involving both children because such a path cannot extend to the parent.
Here’s an example:
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
max_path_sum = float('-inf')
def max_path_down(node):
global max_path_sum
if not node:
return 0
left = max(max_path_down(node.left), 0)
right = max(max_path_down(node.right), 0)
max_path_sum = max(max_path_sum, left + right + node.val)
return max(left, right) + node.val
def maxPathSum(root):
max_path_down(root)
return max_path_sum
# Binary tree example
root = TreeNode(10)
root.left = TreeNode(2)
root.right = TreeNode(10)
root.left.left = TreeNode(20)
root.left.right = TreeNode(1)
root.right.right = TreeNode(-25)
root.right.right.left = TreeNode(3)
root.right.right.right = TreeNode(4)
print(maxPathSum(root))The output of this code snippet will be:
42
The provided code defines a TreeNode class for the binary tree nodes and a global variable max_path_sum. The max_path_down function recursively calculates the maximum path sum from a given node downwards and updates max_path_sum if a higher sum is found. The maxPathSum function is the main function that begins the recursion from the root of the binary tree. In the example, the maximum path sum in the tree is 42.
Method 2: Recursion without Global Variable
This approach utilizes a recursive function to return the maximum path sum without maintaining any global state. The idea is to return both the maximum path sum for the current subtree and the maximum path sum from the root of the current subtree to any leaf.
Here’s an example:
class TreeNode:
# ... (TreeNode definition is the same as above)
def maxPathSum(root):
def helper(node):
if not node:
return (0, float('-inf')) # (max root-to-leaf, max path)
left = helper(node.left)
right = helper(node.right)
max_root_to_leaf = max(left[0], right[0], 0) + node.val
max_path = max(left[1], right[1], left[0] + right[0] + node.val)
return (max_root_to_leaf, max_path)
return helper(root)[1]
# Use the same binary tree example as above
print(maxPathSum(root))The output of this code snippet will be:
42
The recursive helper function computes the maximum path sum that includes the current node’s value as either a path that can continue upwards (root-to-leaf), or a self-contained path (no further extension). It returns a tuple containing both values. The main function maxPathSum just kicks off the recursion and extracts the maximum path sum from the tuple. This method eliminates the use of a global state and is thus cleaner.
Method 3: Dynamic Programming on Trees
The dynamic programming approach treats the problem as an optimization problem, where each node returns the maximum sum of either starting a new path with itself as the highest node or extending the path by including itself. The dynamic programming states are stored implicitly in the recursion stack.
Here’s an example:
# Define your TreeNode class
def maxPathSum(root):
def max_gain(node):
nonlocal max_sum
if not node:
return 0
left_gain = max(max_gain(node.left), 0)
right_gain = max(max_gain(node.right), 0)
price_newpath = node.val + left_gain + right_gain
max_sum = max(max_sum, price_newpath)
return node.val + max(left_gain, right_gain)
max_sum = float('-inf')
max_gain(root)
return max_sum
# Use the same binary tree example as above
print(maxPathSum(root))The output of this code snippet will be:
42
In this method, the function max_gain is defined within maxPathSum to capture the max_sum in its enclosing scope using the nonlocal keyword in Python. This circumvents the need for a global variable and retains the benefits of the Method 1 recursive structure.
Method 4: Iterative Method with Post-order Traversal
Iterative post-order traversal can solve the same problem using a stack and without the system stack used in recursion. This method involves pushing nodes, and their children onto a stack, and calculating the maximum path sums as you pop them off, post-order style.
Here’s an example:
# Define your TreeNode class
def maxPathSum(root):
stack, node_max_sum = [(root, 0)], {}
max_sum = float('-inf')
while stack:
node, visited = stack.pop()
if node is None:
continue
if visited:
left_max_sum = node_max_sum.get(node.left, 0)
right_max_sum = node_max_sum.get(node.right, 0)
node_max = max(node.val + max(left_max_sum, right_max_sum), node.val)
max_sum = max(max_sum, node_max, node.val + left_max_sum + right_max_sum)
node_max_sum[node] = node_max
else:
stack.append((node, 1))
stack.append((node.right, 0))
stack.append((node.left, 0))
return max_sum
# Use the same binary tree example as above
print(maxPathSum(root))The output of this code snippet will be:
42
The iterative approach essentially replicates the post-order traversal using a stack. With each pop, we check if the node has been visited before; if not, we add its children and mark it as visited. If it has been visited, we compute the maximum path sum using the node’s value and the maximum contributions of its children. This iterative approach removes recursion’s potential stack overflow issue.
Bonus One-Liner Method 5: Pure Functional Style
This method is not necessarily practical but is a fun one-liner using a pure functional style. It is mainly for academic interest, as it is less readable and efficient than the other methods.
Here’s an example:
# Define your TreeNode class
maxPathSum = lambda root: max((
lambda f, root: f(f, root, float('-inf'))[1])(
(lambda rec, node, max_sum:
(node.val + max(0, (rec(rec, node.left, max_sum)[0] if node.left else 0),
(rec(rec, node.right, max_sum)[0] if node.right else 0)),
max(max_sum,
node.val +
max(0, (rec(rec, node.left, max_sum)[0] if node.left else 0)) +
max(0, (rec(rec, node.right, max_sum)[0] if node.right else 0))))
if node else (0, max_sum)
), root))
# Use the same binary tree example as above
print(maxPathSum(root))The output of this code snippet will be:
42
This one-liner uses a lambda function to define the recursive function in a way that Python allows recursion within lambdas. It captures the essence of the recursive approach but in a functional and stateless manner. However, this style severely lacks readability and is generally discouraged in Python programming.
Summary/Discussion
- Method 1: Recursion with Global Variable. This method is straightforward and can be easier to understand for those familiar with global state. However, using global variables is generally discouraged due to potential side-effects and code maintainability issues.
- Method 2: Recursion without Global Variable. This approach avoids the problems of global variables. It’s cleaner and safer in terms of managing state, but the recursive nature still exposes the risk of stack overflow for very deep trees.
- Method 3: Dynamic Programming on Trees. Improves on Method 1 by removing global state without compromising performance, but may still be prone to stack overflow problems and it can be somewhat complex to understand.
- Method 4: Iterative Method with Post-order Traversal. This method is stack-safe and mimics the recursive approach without using the system stack. It may be slightly harder to grasp than a simple recursive function, but it’s a robust solution.
- Method 5: Pure Functional Style. While intriguing and concise, this approach is impractical for real-world use due to major readability and efficiency concerns.