#codingexercise

We discussed the method to remove all nodes which don't lie in any path with sum  >= k

Node removeNodes(ref Node root, int k, ref int sum)
{
if (root == null) return null;
int lsum = sum + root.data;
int rsum = lsum;
root.left = removeNodes(ref root.left, k, ref lsum);
root.right = removeNodes(ref root.right, k, ref rsum);
sum = max(lsum, rsum);
if (sum < k)
{
delete(root);
root = null;
}
return root;
}
But this assumes that the sum is strictly increasing down the tree. A better solution might be to delete the leaves in a bottom up manner.

Node removeLeaves(ref Node root, ref int sum)
{
if (root = null) return null;
root.left = removeLeaves(ref root.left, sum - root.data);
root.right = removeLeaves(ref root.right, sum - root.data);
if (root.left == null && root.right == null && root.data < sum)
{
delete(root);
return null;
}
return root;
}

Check if two binary trees are equal
bool Compare( node first, node second)
{
if (first == null && second == null) return true;
if (first == null || second == null) return false;
if (first.data != second.data) return false;
return Compare(first.left, second.left) && Compare(first.right, second.right);
}

Given an array of integers, can it be partitioned into two groups such that the sum of the groups are equal ?

If the sum of all elements is odd, then there is no solution
If the sum of the elements is even, then we recur using sum/2
The recursion considers the last element as included or excluded.

bool isSumEqual(List<int> A, int n, int sum)
{
if (sum == 0) return true;
if (n == 0 && sum != 0) return false;
if (A[n-1] > sum)
   return isSumEqual(A, n-1, sum);
return isSumEqual(A, n-1, sum) || isSumEqual(A, n-1, sum-A[n-1]);
}

bool getPartition(List<int> A, int n)
{
int sum = A.sum();
if (sum%2 != 0) return false;
return isSumEqual(A,n, sum/2);
}

#codingexercise

Given two sets of strings A and B. Find the
 (A-B) U (B-A) ( U = union ). The answer should be in lexicographical order and A’s elements should appear before B’s.

List<T> nonoverlapping(list<T> A, list<T> B)

{

Var infirst = A.Except(B);

Var insecond = B.Except(A);

Return infirst.union(insecond);

}

List<int> Except<List<int> A, List<int> B)
{
var ret = new List<int> ();
for (int i = 0; i < A.Count; i++)
  if (B.Contains(A[i]) == false)
     ret.Add(A[i]);
return ret;
}