hi, let Avik connect you.


** You can give your thought about this content and request modifications if needed from Ask For Modifications page. Thank You.

** You can check all the posts on the Posts page.

** More about me in the About Me section.

Binary Tree Maximum Path Sum


  • Approach:

    1. Started traversing the binary tree from the root.

    2. While moving toward the depth, we need to look for 3 things. For a root, we need to look for -

      • The maximum sum from the left sub-tree adds the value of the root say, Left_Sum.

      • The maximum sum from the right sub-tree adds the value of the root say, Right_Sum.

      • The sum of Left_Sum and Right_Sum adds the value of its root say, Whole_sum.

    3. Take the maximum between Left_Sum, Right_Sum, and Whole_sum.

    4. Return the maximum between Left_Sum and Right_Sum to its root.

    5. Repeat the process until we traversal completes.


  • Time and Space Complexity:

      • Time Complexity: O(N)

      • Space Complexity: O(1) + Auxilary Stack


Code [C++]

/**

* Definition for a binary tree node.

* struct TreeNode {

* int val;

* TreeNode *left;

* TreeNode *right;

* TreeNode() : val(0), left(nullptr), right(nullptr) {}

* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}

* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}

* };

*/

class Solution {

public:

int solve(TreeNode * root, int & ans){

if(!root) return 0;

int left = max(solve(root->left, ans), 0);

int right = max(solve(root->right, ans), 0);

ans = max(ans, left + right + root->val);

return max(left+root->val, right+root->val);

}


int maxPathSum(TreeNode* root) {

int ans = INT_MIN;

solve(root, ans);

return ans;

}

};