Binary Tree Maximum Path Sum

This page explains Java solution to problem Binary Tree Maximum Path Sum using Post Order Traversal of Tree data structure.

Problem Statement

Given a non-empty binary tree, find the maximum path sum.

For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path must contain at least one node and does not need to go through the root.

Input: [1,2,3]
   1
  / \
 2   3

Output: 6

Input: [-10,9,20,null,null,15,7]
   -10
   / \
  9  20
    /  \
   15   7

Output: 42

Solution

package com.vc.hard;

class BinaryTreeMaximumPathSum {
    int max = Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        solve(root);
        return max;
    }

    private int solve(TreeNode root) {
        if(root != null) {
            int left = solve(root.left);
            int right = solve(root.right);

            if(left <= 0 && right <= 0) {
                max = Math.max(max, root.val);
                return root.val;
            }
            else if(left <= 0) {
                max = Math.max(max, right + root.val);
                return root.val + right;
            }
            else if(right <= 0) {
                max = Math.max(max, left + root.val);
                return root.val + left;
            }
            else {
                max = Math.max(max, root.val + left + right);
                return root.val + Math.max(left, right);
            }
        }
        return 0;
    }
}

Time Complexity

O(N) Where
N is total number of elements in an input tree

Space Complexity

O(1)