DAY 57 - Binary Tree Maximum Path Sum

Welcome to DAY 57. Today we will diverge once again into the Data Structure Trees and look at some more traversals. I suggest reading the previous article on Trees before reading this.
Content and Guidance Credits: Striver on Youtube

Question: Binary Tree Maximum Path Sum

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.

Example 1:

• Input: root = [1,2,3]
• Output: 6
• Explanation: The optimal path is 2 -> 1 -> 3 with a path sum of 2 + 1 + 3 = 6.

Example 2:

• Input: root = [-10,9,20,null,null,15,7]
• Output: 42
• Explanation: The optimal path is 15 -> 20 -> 7 with a path sum of 15 + 20 + 7 = 42.

Intuition:

• Let's start by breaking down the question first.
• To say simply, a path is the way through which we connect two nodes. Say Node A and Node B If we can connect them to each other using other nodes such that there is an edge between them, that's a path.
• In last question we found if the tree is balanced using height function.
• What we basically have to find for every node is the maximum path sum and it does not specifically have to pass through the root node.
• So what we can do is go to node, find the max Sum we can get from that and add them up.
• If we do this for every node , we can find the maximum Path sum here.

Algorithm and Code:

• The function maxPathSum takes the root of a binary tree as input and returns the maximum path sum as an integer.
• The algorithm uses a helper function helper to calculate the maximum path sum for each subtree rooted at the current node.
• The helper function takes the root node and a reference to the maximum sum (maxi) as inputs and returns the maximum path sum for the subtree rooted at the current node.
• If the current node is NULL (i.e., there is no node), the function returns 0, as there is no path.
• The function recursively calculates the maximum path sum for the left and right subtrees using the helper function.
• To ensure that the path sum is positive, the function takes the maximum of 0 and the maximum path sum of the left and right subtrees.
• The current node's value is stored in the val variable.
• The function updates the maxi variable by taking the maximum of the current maximum path sum (maxi) and the sum of maxL (maximum path sum of the left subtree) and maxR (maximum path sum of the right subtree) plus the current node's value.
• The function returns the maximum of maxL and maxR plus the current node's value.
• The maxPathSum function initializes the ans variable to a very small value (INT_MIN) and calls the helper function to find the maximum path sum.
• The helper function updates the ans variable, which holds the maximum path sum.
• Finally, the function returns the ans, representing the maximum path sum in the binary tree.

   int findMaxPathSum(TreeNode * root, int & maxi) {
  if (root == NULL) return 0;

  int leftMaxPath = max(0, findMaxPathSum(root -> left, maxi));
  int rightMaxPath = max(0, findMaxPathSum(root -> right, maxi));
  int val = root -> val;
  maxi = max(maxi, (leftMaxPath + rightMaxPath) + val);
  return max(leftMaxPath, rightMaxPath) + val;

}

int maxPathSum(TreeNode * root) {
  int maxi = INT_MIN;
  findMaxPathSum(root, maxi);
  return maxi;

}

Complexity Analysis:

• *Time: O(N) *
• Space: O(H) where H is the height of tree