July 15, 2020 - 10:00 PM mock interview - the interviewee is Microsoft SDE II with two year experience

SufficientPathTreeAlgo.java

import java.io.*;
import java.util.*;

class Solution {
  public static void main(String[] args) {
    ArrayList<String> strings = new ArrayList<String>();
    strings.add("Hello, World!");
    strings.add("Welcome to CoderPad.");
    strings.add("This pad is running Java " + Runtime.version().feature());

    for (String string : strings) {
      System.out.println(string);
    }
  }
  
  /**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
  /*
  460 - 
  
    null  dfsHelper(a 0 - 1)
  /    \
null  null
    
    */  
  public TreeNode sufficientSubset(TreeNode root, int limit) {
    if (root == null) return root;
    return dfsHelper(root, 0, limit);
  }     
      
  private TreeNode dfsHelper(TreeNode root, int prevTotal, limit) {
    // base case at leaf node
    if (root.left == null && root.right == null) {
      return (prevTotal + root.val < limit) ? null : root;
    }  
    // now recursion going left first then right
    if (root.left != null) {
      // creative - 
      root.left = dfsHelper(root.left, prevTotal + root.val, limit);
    }  
    if (root.right != null) {
      root.right = dfsHelper(root.right, prevTotal + root.val, limit); 
    }
    
    return root.left == null && root.right == null ? null : root;
  }  
}

/* 
Given the root of a binary tree, consider all root to leaf paths: paths from the root to any leaf.  (A leaf is a node with no children.)

A node is insufficient if every such root to leaf path intersecting this node has sum strictly less than limit.

Delete all insufficient nodes simultaneously, and return the root of the resulting binary tree.

test case 1:
     1
  /    \
  -99  -99
  
  limit is 1, return null

test case 2:

     10
    /  \
    5  10 
    
    limit = 21, return null
    
    
test case 3:

      1i
    /   \
i  2   -3  i
   /\    /
inul 1i 4    limit = -1 
    
    
    return: 
    
      1
    /   \
   2    -3
    \    /
    1   4    limit = -1  
         

The given tree will have between 1 and 5000 nodes.
-10^5 <= node.val <= 10^5
-10^9 <= limit <= 10^9
 
 public TreeNode sufficientSubset(TreeNode root, int limit) {
        
    } 
 */