Binary Tree Maximum Path Sum

 Clarify the problem

  • The problem asks us to find the maximum path sum in a binary tree.
  • A path can start and end at any node in the tree.
  • The path must go downwards (i.e., parent to child nodes).
  • The path can be a single node.
  • We need to return the maximum sum of any path in the given binary tree.

Analyze the problem

  • Input: The root of a binary tree.
  • Output: The maximum path sum.
  • Constraints: The binary tree can be empty. The values of the nodes can be both positive and negative integers.

Design an algorithm

  • We can solve this problem using recursion and a helper function.
  • The helper function will recursively calculate the maximum path sum for each node in the tree.
  • At each node, we need to consider four possibilities:
    1. The current node itself (forming a single node path).
    2. The maximum path sum in the left subtree (excluding the current node).
    3. The maximum path sum in the right subtree (excluding the current node).
    4. The maximum path sum that includes the current node and extends into both the left and right subtrees.
  • We can update a global variable to keep track of the maximum path sum seen so far.
  • The base case is when we reach a null node, where we return 0.
  • The recursive calls will return the maximum sum of paths starting from the current node and extending downward.

Explain your approach

  • We'll define a recursive helper function maxPathSumHelper(node) that takes a node as input and returns the maximum path sum starting from that node.
  • The function will calculate the maximum path sum for the left and right subtrees using recursion.
  • We'll consider the four possibilities mentioned earlier and choose the maximum sum among them.
  • At each node, we'll update the global maximum path sum if the sum including the current node is greater.

Write clean and readable code

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


def maxPathSum(root):
    # Global variable to store the maximum path sum
    max_sum = float('-inf')

    def maxPathSumHelper(node):
        nonlocal max_sum
        if not node:
            return 0

        # Calculate the maximum path sums of the left and right subtrees
        left_sum = max(0, maxPathSumHelper(node.left))
        right_sum = max(0, maxPathSumHelper(node.right))

        # Update the maximum path sum if necessary
        max_sum = max(max_sum, node.val + left_sum + right_sum)

        # Return the maximum path sum starting from the current node
        return node.val + max(left_sum, right_sum)

    maxPathSumHelper(root)
    return max_sum

Test your code

  • Let's test the code with some test cases:
# Test case 1:
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
print(maxPathSum(root))  # Output: 6
# Explanation: The maximum path sum is the path with nodes 2 -> 1 -> 3, which gives a sum of 6.

# Test case 2:
root = TreeNode(-10)
root.left = TreeNode(9)
root.right = TreeNode(20)
root.right.left = TreeNode(15)
root.right.right = TreeNode(7)
print(maxPathSum(root))  # Output: 42
# Explanation: The maximum path sum is the path with nodes 15 -> 20 -> 7, which gives a sum of 42.

# Test case 3:
root = None
print(maxPathSum(root))  # Output: 0
# Explanation: The tree is empty, so the maximum path sum is 0.

Optimize if necessary

  • The algorithm has a time complexity of O(N), where N is the number of nodes in the tree. We visit each node once.
  • The space complexity is O(H), where H is the height of the tree. In the worst case, the height of the tree is equal to the number of nodes in the tree, resulting in O(N) space complexity.

Handle error cases

  • The code already handles the case when the input tree is empty (i.e., root is None).

Discuss complexity analysis

  • Time complexity: O(N), where N is the number of nodes in the tree.
  • Space complexity: O(H), where H is the height of the tree.
  • The algorithm has a linear time complexity as we visit each node once and perform constant-time operations at each node.
  • The space complexity depends on the height of the tree, as the recursion stack can go as deep as the height of the tree. In the worst case, the height of the tree is equal to the number of nodes, resulting in O(N) space complexity.
Next Post Previous Post