Remove the nodes in the binary tree for that the sum of all values from root to leaf is less than K

The easiest way to imagine this problem is to think of this as a sub problem first:

Remove the nodes leafs in the binary tree for that the sum of all values from root to leaf is less than K

In this case, the problem is simple, visit all the leaves, and keep track of the sum of all the parents, such that by the time the leaf node is reached, we will know whether the leaf should be deleted or not.

The below algorithm follows the same pattern, with a little difference. Just that if the leaf is not deleted, the we pass along its value, such that while we return, we can use that to determine whether their parents should stay or not.

Read the algo, its simple to follow.

Terms:

completePath = any path from root to leaf
sumToRoot = sum of all the parent nodes till the root
sumToLeaf = max (sum of all the nodes to the leaf)
completePathSum = max (sum of nodes in completePath)

Algo:

// @return max sum to leaf
int visit(node n, int sumToRoot) {

 if(n == null)
  return 0;
 
 // visit left and right first
 int leftSumToLeaf = visit(n.left, sumToRoot + n.value);
 int rightSumToLeaf = visit(n.right, sumToRoot + n.value);

 int maxSumToLeaf = max(leftSumToLeaf, rightSumToLeaf);
 
 int completePathSum = sumToRoot + n.value + maxSumToLeaf;

 // if completePathSum < k remove and return 0 
 if( completePathSum < k ) {
  delete n;
  return 0;
 }

 // otherwise 
 return n.value + maxSumToLeaf;
}

Do write comments if you feel something is not right.