124. Binary Tree Maximum Path Sum

Here is the link.

C# mock interview practice on Nov 24, 2019 with insights

Nov 25, 2019
It is one of my mock interview algorithms. I solved the algorithm but I also experienced the nervousness since I could not remember if I solved the algorithm before. It is a hard level algorithm, and I like to write down how to approach the algorithm in the contest or mock interview or onsite.

I solved all tree algorithms on Leetcode six months ago. But my generic approach is to solve all easy level algorithms on Leetcode.com first, and then move to medium level. So it is important for me to explain how to approach this hard level algorithm since I solved similar easy level tree algorithm called longest univalue path, my discussion post is here. I am still in the accumulation stage to solve as many algorithms as possible. Be greedy, solve easy one, solve one with less time first, solve ones to help me build confidence, increase curiosity, and expand my comfortable zone.

Case study

I like to go over the example and explain to myself how to approach the problem. Let me show some diagram with my thought process in my mock interview.

I like to go over the example, and explain how I ask question what to do based on example 2.

After the work out on example 2, I learned that I need to work on an extra task to calculate the path cross the root node. The whole process from example 1 and example 2 took me around 10 to 15 minutes.

If you cannot follow the process, then I can advice you to review the post I have about longest univalue path. Here is the link.

I spent two months to interview people on interiviewing.io using a few binary tree algorithms almost every weekday, I learn and work every day on tree algorithms. Those interviewees are best teachers in the world and they brought all their education and industry experience to demonstrate how good thinkers are, I learn to build up my curiousity and be a real problem solver, open to all ideas as an interviewer and determin to make the idea work, remove bias and avoid memorization of a solution, ask good questions to follow the idea and understand the question.

References:

public class Solution {
    public int MaxPathSum(TreeNode root) {
        if (root == null)
                return 0;
            var maxPathSum = Int32.MinValue;
            postorderTraversal(root, ref maxPathSum);

            return maxPathSum; 
        }

        /// <summary>
        /// return max value of path from root node to one of node downward to leaf node
        /// </summary>
        /// <param name="root"></param>
        /// <returns></returns>
        private static int postorderTraversal(TreeNode root, ref int maxPathSum)
        {
            if (root == null)
            {
                return 0;
            }

            var maxLeft = postorderTraversal(root.left, ref maxPathSum);
            var maxRight = postorderTraversal(root.right, ref maxPathSum);

            var sumLeft  = Math.Max(0,maxLeft);
            var sumRight = Math.Max(0, maxRight);

            var currentMax = root.val + Math.Max(sumLeft, sumRight);
            var currentPath = root.val + sumLeft + sumRight; 
            maxPathSum = Math.Max(maxPathSum, currentPath);
            return currentMax;
        }
}