Leetcode discuss: 124. Binary Tree Maximum Path Sum

May 12, 2021

Here is the link. 

C# | Post order traversal | optimal time and space complexity | May 12, 2021

May 12, 2021
Introduction
The algorithm is to find maximum path sum in any given binary tree. The path can start from any node in the binary tree and end any node in the tree. So the brute force solution will be time complexity O(N^3), using O(N^2) to find all paths first, and then use O(N) time to calculate the sum for each path. The optimal solution can be found using post order traversal once with time complexity is O(N), whereas N is total number of nodes in the tree.

It is important to undersand the post order traversal and how the traversal can help to traverse each node once and get all calculations needed for the maximum path sum in the binary tree. The tip here is that there are four values to calculate for each node in the tree, which is listed in the following section. I came cross this tip when I reviewed my study notes back in 2015 through my coding blog, and I definitely was surprised to learn the summary is simple and straightforward.

Post order traversal | bottom up | hashmap or in-place | Four cases
The idea is to apply post order traversal, visit nodes in binary tree bottom up, and also using optimal time complexity O(N), space complexity O(1), visit each node once.

There are still multiple ways to approach the solution based on the analysis of recursive function to calculate the root to leaf node maximum path. One idea is to use memoization to save all node's maximum path to leaf node's sum in a hashmap, or work on a solution in place so that there is no need to use extra space. In place solution also can be interpreted in different ways for easy to understand.

One of ideas is to think about the following way:
For each node like following, there should be four ways existing for max path:
1. Node only
2. L-sub + Node
3. R-sub + Node
4. L-sub + Node + R-sub

Keep trace the four path and pick up the max one in the end.

Another idea is to think about the following way:
For each node, recursively calculate the maximum path sum from root node to leaf node. So there are three values and keep the maximum value.
1. Node only
2. L-sub + Node
3. R-sub + Node
Next it is to calculate the paths cross root node, and keep maximum path sum.

Courage to try optimal time complexity and in-place first
It is better to build habit to try optimal time complexity and in-place solution for this probem first, and then spend time on other solutions like extra space using hashmap, or time complexity with O(N^2) solution. Try all solutions in practice and compare the difference.

The following code passes online judge, the solution is optimal time complexity, O(N), N is total number of nodes in the tree, and also space complexity is O(1).

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution {
    public int MaxPathSum(TreeNode root) {
        if(root == null)
            return 0; 
        
        var maxCrossRoot = Int32.MinValue; 
        //Try to aim optimal time complexity O(N), bottom up, post order traversal, 
        // visit each node once, and then recursively build up the maximum path sum, cross root path's maximum value
        // Also, space complexity is O(1) besides using internal stack of recursive function
        applyPostOrderTraversal(root, ref maxCrossRoot);
        
        return maxCrossRoot; 
    }
    
    /// May 12, 2021 
    /// bottom up, visit every node once, keep time complexity O(N), N is total number of nodes in the tree
    /// Recursive function is designed to calculate the maximum value of the following three:
    /// 1. Root value
    /// 2. Root value + left subtree's value
    /// 3. Root value + right subtree's value
    /// The maximum path sum is called from root node to leaf node path maximum sum. 
    private int applyPostOrderTraversal(TreeNode root, ref int maxCrossRoot)
    {
        if(root == null)
            return 0; 
        
        var left = applyPostOrderTraversal(root.left, ref maxCrossRoot); 
        var right = applyPostOrderTraversal(root.right, ref maxCrossRoot); 
        
        var value = root.val;
        var current = value; 
        if(left > 0)
            current += left;
        if(right > 0)
            current += right; 
        
        maxCrossRoot = Math.Max(maxCrossRoot, current);
        
        var values = new int[]{value, value + left, value + right};
        
        return values.Max();        
    }
}