Maximum Path Sum (revisited) 🎯

Welcome back! Today, we're going to revisit a classic problem called Maximum Path Sum. This problem is a great way to understand and practice data structures and algorithms. Let's dive in! 🐳

What is Maximum Path Sum?

Maximum Path Sum is a problem that involves traversing a binary tree to find the maximum sum of any path from root to leaf. This problem can be solved using various techniques, and today, we'll focus on using Depth-First Search (DFS) and Memoization. 📝

Binary Trees and Nodes

Before we jump into the problem, let's briefly discuss binary trees and nodes. A binary tree is a tree data structure in which each parent node has at most two children: a left child and a right child. Each node in the binary tree has a value associated with it. 📝

Maximum Path Sum Algorithm

Here's the step-by-step process of our Maximum Path Sum algorithm:

Initialize a variable max_sum and set it to a small negative number (e.g., float(-inf) in Python). This variable will store the maximum sum found so far.
Perform a Depth-First Search (DFS) on the binary tree using recursion.
During DFS, visit each node and perform the following steps:
- Calculate the sum of the current node and the maximum sum of the subtree rooted at the left child (if it exists) and the maximum sum of the subtree rooted at the right child (if it exists).
- If the calculated sum is greater than the current value of max_sum, update max_sum with the new sum.
- After visiting a node, memoize the maximum sum of the subtree rooted at the current node to avoid redundant calculations.
Once DFS is complete, the final value of max_sum will store the maximum path sum in the binary tree.

Code Example

Here's a Python code example that demonstrates the Maximum Path Sum algorithm:

python

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

def max_path_sum_util(node, max_sum):
    if node is None:
        return 0

    # Calculate the maximum sum of the left and right subtrees
    left_sum = max_path_sum_util(node.left, max_sum)
    right_sum = max_path_sum_util(node.right, max_sum)

    # Memoize the maximum sum of the subtree rooted at the current node
    max_sum_left_subtree = max(0, left_sum)
    max_sum_right_subtree = max(0, right_sum)
    max_sum[0] = max(max_sum[0], max_sum_left_subtree + max_sum_right_subtree + node.value)

    # Return the maximum sum of the left and right subtrees, or the value of the current node if the subtrees are empty
    return max(node.value + max_sum_left_subtree, max_sum_right_subtree)

def max_path_sum(root):
    # Initialize max_sum with a small negative number
    max_sum = [float(-inf)]

    # Perform DFS and calculate the maximum path sum
    max_path_sum_util(root, max_sum)

    return max_sum[0]

Quiz 📝

Conclusion

Today, we revisited the Maximum Path Sum problem and learned how to solve it using Depth-First Search (DFS) and Memoization. This problem is a great way to understand recursion, DFS, and memoization. Now that you've got the basics down, you can practice the problem with different binary trees to improve your understanding and master the concept. Happy coding! 🎯