1038. Binary Search Tree to Greater Sum Tree

I wrote a post to share on Leetcode.com discuss. Here is the link. I also like to copy and paste here in case one day the algorithm is set to the private and the discussion post is no longer available.

It is a medium level tree algorithm. I worked on the algorithm in weekly contest, I was nervous. Two mistakes dragged down my performance. It should take me 10 minutes, but I actually spent over 50 minutes, last two minutes I finally made it work in the contest.

Two most common mistakes

Let me introduce the first mistake I had, and I had to take time to figure out. I like to traversal the tree using Right, Root, Left so that all numbers will be decending order.

From the above diagram, a, b, c, d and e are used to mark the order of all elements in the tree. I was confused that d and e two nodes, which one should go first. I was not sure. It took me extra five minutes at least

Let me introduce my second mistake, calculate the sum of visited nodes in the tree.

private static void traversalRightRootLeft(TreeNode root)
        {
            if(root.right != null)
            {
                traversalRightRootLeft(root.right);
            }

            // visit root
            
            var firstCheck = previous != null  ;            
            
            if(firstCheck)
                root.val += previous.val;
                
            previous = root; 
            

            if(root.left != null)
            {
                traversalRightRootLeft(root.left);
               root.left.val += root.val; // this is a second bug
            }
        }

The second bug is to write code in the left child; The simple reasoning can pinpoint the code is wrong. Every node will be visited once, how come the node which is left child will be counted twice in calculation of node's value?

I like to explain this common mistake in recursive function so that it is much easy to understand the reasoning.

Advice on weekly contest

Based on the above facts, I should focus on reasoning, not just try to pass all test cases in problem solving; It is hard for me to work on something new in the contest, I was nervous but I learned two lessons from the above two mistakes in the contest.

I like to write down and share with others. We all know that practice makes perfect. What I like to do is to talk about mistake, and try to work on my reasoning skills in the contest. That will help me to improve my performance. Between 50 minutes to solve and 10 minutes to solve are huge difference in 90 minues contest.

References:

1. weekly contest 135 website is here.
2. My weekly performance 135 diagram with time spent on the second algorithm 54 minutes.
   
3. Top 10 players and their time spent on the algorithm.

The minimum time is 1 minutes, maximum time is 9 minutes for those top 10 ranking players.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    static TreeNode previous = null;
    public TreeNode BstToGst(TreeNode root) {
        if (root == null)
                return null;
            previous = null;
            traversalRightRootLeft(root);
            return root;
        }

        
        private static void traversalRightRootLeft(TreeNode root)
        {
            if(root.right != null)
            {
                traversalRightRootLeft(root.right);
            }

            // visit root
            
            var firstCheck = previous != null  ;            
            
            if(firstCheck)
                root.val += previous.val;
                
            previous = root; 
            

            if(root.left != null)
            {
                traversalRightRootLeft(root.left);
               // root.left.val += root.val;
            }
        }
}