Leetcode discuss: 1080. Insufficient Nodes in Root to Leaf Paths

Here is the link.

C# It took me 85 minutes to make it work in mock interview

July 10, 2020
Introduction
1080. Insufficient Nodes in Root to Leaf Paths

What is secret to solve a tree algorithm in Leetcode mock interview. I can say a few things to make it work fast, correctly as well.

Work on a small case study, and also make it simple; ask myself to double check if things can be simplified.

It took me 85 minutes to write code, tested code a few times, and made it work.

Case study
Work on a three nodes tree, root node with value 1, left child with value -99, right child with value -99, limit is 1;
Test case 2:
Root node with value 10, left child with value 5, right child with value 10, limit is 21, return null;
Test case 3:
Root node = 1
root node.left = 2
root node.right = -3
root node.left.left = -5,
root node.right.left = 4
limit is -1

Extra work
I did not analyze carefully, so I started to think about using leaf node hashmap. There is no need for leaf node hashmap.

I noticed that root == null does not work for test case 2, and return is null, the function postOrderTraversal did set root node of orginal tree to null. But test case failed in function
SufficientSubset. Need to take more time to look into this issue.

Hashmap
There is no need to save every node p's sum from root node to p node. Only root node to leaf node's path sum should be used to compare to limit.

C# value type and reference type

I need to look into C# language design related to reference type. I debugged the code using visual studio, I need to figure out how to pass root node reference and make it work.

I made temporary fix to add extra checking in the function SufficientSubset :
if(root.left == null && root.right == null)
return null;

/**
 * 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 {
    // root 1, left -99, right -99, limit 1
    public TreeNode SufficientSubset(TreeNode root, int limit) {
        
         if(root.left == null && root.right == null && root.val < limit)
            return null;
        
        // preorder traversal the tree and save root to node paths sum into a hashmap
        // int[] first one is sum, second one - 1 - leaf node - 0 - not leaf node
        var map = new Dictionary<TreeNode, int[]>();      
        
        TreeNode parent = null; 
        preorderTraversal(root, map, 0);
        
        // postorder traversal, and then calculate the root to leaf path
        // remove nodes if need
        // leaf node to current node sum
        //  TreeNode parent = null;
        postOrderTraversal(root, map, parent, limit, true);
        
        if(root.left == null && root.right == null)
            return null;
        
        return root; 
    }
    
    /// root 1, left -99, right -99, limit 1
    private void preorderTraversal(TreeNode root, Dictionary<TreeNode, int[]> map, int sumRootToP)
    {
        if(root == null)
            return; 
        
        var sum = sumRootToP + root.val; // -99
       
        var isLeaf =  root.left == null && root.right == null; // false
        
        var value = isLeaf? 1 : 0; 
        map.Add(root, new int[]{sumRootToP + root.val, value}); // {-98, 1}
        
        preorderTraversal(root.left,  map, sum); 
        preorderTraversal(root.right, map, sum);
    }
    
    // root 1, left -99, right -99, limit 1
    private void postOrderTraversal(
 TreeNode root, 
 Dictionary<TreeNode, int[]> rootToPMap,    
 TreeNode parent, 
 int limit, 
 bool isLeft)
    {
        if(root == null)
            return;
        
        // Left and right
        postOrderTraversal(root.left,  rootToPMap, root, limit, true);
        postOrderTraversal(root.right, rootToPMap, root,limit, false);        
        
        // if root node is leaf node
        if(rootToPMap[root][1] == 1)
        {
            var sum = rootToPMap[root][0]; // -98
            if(sum < limit)
            {
                //leafMap.Add(root, false); // keep the leaf
                if(parent != null && isLeft)
                {
                    parent.left = null;
                }
                else if(parent != null )
                {
                    parent.right = null;
                }
                else if(parent == null)
                {
                    root = null;
                }
            }
        }
        else // not leaf node
        {
            if(root.left == null && root.right ==  null)
            {                                
                if(parent != null)
                {
                    if(isLeft)
                        parent.left = null;
                    else
                        parent.right = null; 
                }
                
                root = null; 
            }
        }
    }       
}