Taro Logo

Binary Tree Maximum Path Sum

Hard
Amazon logo
Amazon
Topics:
TreesRecursion

A path in a binary tree is a sequence of nodes where each pair of adjacent nodes in the sequence has an edge connecting them. A node can only appear in the sequence at most once. Note that the path does not need to pass through the root.

The path sum of a path is the sum of the node's values in the path.

Given the root of a binary tree, return the maximum path sum of any non-empty path.

For example, consider a binary tree represented as [1,2,3]. The optimal path is 2 -> 1 -> 3 with a path sum of 2 + 1 + 3 = 6.

As another example, consider a binary tree represented as [-10,9,20,null,null,15,7]. The optimal path is 15 -> 20 -> 7 with a path sum of 15 + 20 + 7 = 42.

Write an algorithm to efficiently determine the maximum path sum in a given binary tree. What is the time and space complexity of your solution?

Solution


Naive Solution

A brute-force approach would involve exploring all possible paths in the binary tree and calculating their sums. This could be done using recursion, where we traverse the tree and, at each node, consider paths that include the node and paths that don't. The maximum path sum encountered during this traversal would be the answer.

However, this approach is inefficient because it involves redundant calculations. We would be recalculating the sums of many subpaths multiple times.

Optimal Solution

A more efficient approach involves using recursion with memoization or dynamic programming principles. We can define a recursive function that returns two values:

  1. The maximum path sum that includes the current node and extends to one of its children.
  2. The maximum path sum that passes through the current node (i.e., includes the node and extends to both of its children, or just the node itself).

We can maintain a global variable to keep track of the maximum path sum encountered so far. During the recursion, we update this variable whenever we find a path with a greater sum.

Edge Cases

  • Empty tree: If the root is null, the maximum path sum is 0.
  • Nodes with negative values: The algorithm should handle cases where nodes have negative values, as these can decrease the path sum.
  • Single-node tree: If the tree consists of only one node, the maximum path sum is the value of that node.

Code (Java)

class Solution {
    int max_sum = Integer.MIN_VALUE;

    public int maxPathSum(TreeNode root) {
        maxPathSumHelper(root);
        return max_sum;
    }

    private int maxPathSumHelper(TreeNode node) {
        if (node == null) return 0;

        int left = Math.max(maxPathSumHelper(node.left), 0);
        int right = Math.max(maxPathSumHelper(node.right), 0);

        int price_newpath = node.val + left + right;

        max_sum = Math.max(max_sum, price_newpath);

        return node.val + Math.max(left, right);
    }
}

Explanation of the Code

  1. max_sum: A global variable to store the maximum path sum found so far, initialized to the smallest possible integer value.
  2. maxPathSum(TreeNode root): The main function that initiates the recursive calculation.
  3. maxPathSumHelper(TreeNode node): A recursive helper function that calculates the maximum path sum.
    • Base case: If the node is null, return 0.
    • Recursively calculate the maximum path sums for the left and right subtrees.
    • If the left or right path sums are negative, set them to 0 (because we want to maximize the sum, so negative paths are not useful).
    • Calculate the path sum including the current node, left subtree, and right subtree (price_newpath).
    • Update max_sum if price_newpath is greater than the current max_sum.
    • Return the maximum path sum that includes the current node and either the left or right subtree (whichever is larger).

Big O Notation

  • Time Complexity: O(N), where N is the number of nodes in the binary tree. This is because we visit each node once.
  • Space Complexity: O(H), where H is the height of the binary tree. In the worst case (skewed tree), H can be equal to N. In the average case (balanced tree), H is log(N). This space complexity is due to the recursive call stack.