CareerCup

we can keep a counter to track the nodes in the same level.

public class TreeNode
{
	int key;
	int value;
	TreeNode left;
	TreeNode right;
}
public static int mostNegativeLevel(TreeNode root)
{
	if(root == null)
		return -1;

	Queue q = new Queue<TreeNode>();
	int count = 0;		

	int level = 0;	
	int maxNegativeLevel = 0;

	int negativeCount = 0;
	int maxNegativeCount = 0;
	
	q.enqueue(root);	
	count++;

	while(!q.empty())
	{
		TreeNode node = stack.dequeue();
		negativeCount+= (node.number < 0)? 1:0;
		count --;

		if(node.left != null) 
			q.push(node.left);
		if(node.right !- null)
			q.push(node.right);

		if(count == 0)
		{
			if(negativeCount > maxNegativeCount)
			{
				maxNegativeCount = negativeCount;
				maxNegativeLevel = level;
			}		
			
			count = q.size();
			level++;
			negativeCount = 0;
		}
	}
	
	return maxnegativeLevel;
}

Its a modification of Level Order traversal / BFS of binary tree.

For each level, find the count of -ve numbers. Compare it with a max_count, which indicates what level has the max -ve numbers and swap if needed.

As for the BFS search with level number, it can be done in many ways:
1. Using a dummy node
2. Keeping a count of nodes in current level and next leve
3. Using separate queues for current and next level.

Here is working version in python

//tree node structure
class Node:
  left = None
  right = None
  value = -1

  def __init__(self, value =-1):
    self.value = value

def find_negatives(tree):
  count = []
  count_negatives(tree, count, 0)
  max = 0;
  depth = 0;
  for i in range(0, len(count)):
    print "depth " + str(i) + " count: " + str(count[i])
    if (count[i] > max):
      max = count[i]
      depth = i

  print "result depth : " + str(depth) + " count : " + str(max)
  return max

def count_negatives(tree, count, depth):
  if tree is None:
    return

  if tree.value < 0:
    print "found : " + str(tree.value) + " depth : " + str(depth)
    if (len(count) -1 < depth):
      count.append(1)
    else:
      count[depth] = count[depth] +1

  count_negatives(tree.left, count, depth+1)
  count_negatives(tree.right, count, depth+1)
  return

This is another one using BFS.

def bfs_count(root):
  result = {}
  current_depth =0
  current_node_count = 0
  current_negative_count = 0
  next_node_count = 0
  queue = deque()

  queue.append(root)
  current_node_count =1
  max_count = 0
  max_depth = 0

  while (len(queue)):
    node = queue.popleft()
    current_node_count-=1

    if (node.value < 0):
      current_negative_count+=1
    
    if (node.left != None):
      queue.append(node.left)
      next_node_count += 1
  
    if (node.right != None):
      queue.append(node.right)
      next_node_count +=1

    if (current_node_count == 0):
      if (current_negative_count > max_count):
        max_count = current_negative_count;
        max_depth = current_depth
      current_depth+=1
      current_node_count = next_node_count
      next_node_count = 0
      current_negative_count = 0;

  result[max_depth] = max_count
  return result

This is my proposal in C++. I assumed we have a BST:

#include <iostream>
using namespace std;

struct node
{
int data;
node* p_left;
node* p_right;
};

node* addNode(node* root, int value)
{
if(root == NULL)
{
node* n = new node;
n->data = value;
n->p_left = NULL;
n->p_right = NULL;
return n;
}
if(value <= root->data)
root->p_left = addNode(root->p_left, value);
else
root->p_right = addNode(root->p_right, value);
return root;
}

int getDepth(node* root)
{
if(root == NULL)
return 0;
return 1 + max(getDepth(root->p_left), getDepth(root->p_right));
}

void maxNegativeInLevel(node* root, int * arr, int level)
{
if(root == NULL)
return;
if(root->data < 0)
arr[level]++;
maxNegativeInLevel(root->p_left, arr, level + 1);
maxNegativeInLevel(root->p_right, arr, level + 1);
}

int main()
{
node* tree = NULL;
tree = addNode(tree, -8);
tree = addNode(tree, -15);
tree = addNode(tree, -3);
tree = addNode(tree, -21);
tree = addNode(tree, -14);
tree = addNode(tree, -3);
tree = addNode(tree, 4);
tree = addNode(tree, -6);

int depth = getDepth(tree);
int * quantities = new int[depth];
maxNegativeInLevel(tree, quantities, 0);

int max_level = 0;

for(int i = 0; i < depth; i++)
if(quantities[i] > quantities[max_level])
max_level = i;

cout << "Level " << max_level << " with " << quantities[max_level] << " node(s)" << endl;
}

Just make modified version of BFS. Instead of using single list create two: List<Node> currentLevel and List<Node> nextLevel:
- currentLevel - stores elements for the level which is being precessed.
- nextLevel - stores the children of the current level
In this way you can control the level which you are processing without mixing it with its children.
For the current level count the number of negative numbers. And choose the one which has max number of neg numbers.
Code:

public static void findLevelWithMaxNeg(Node root) {
        List<Node> currentLevel = new ArrayList<Node>();
        List<Node> nextLevel = new ArrayList<Node>();
        currentLevel.add(root);
        int levelWithMaxNeg = -1;
        int maxNeg = 0;
        int currentNeg = 0;
        int levelNo = 0;
        int i = 0;
        while (i < currentLevel.size()) {
            i++;
            Node node = currentLevel.get(i);
            if (node.value < 0) {
                currentNeg++;
            }
            if (node.left != null) {
                nextLevel.add(node.left);
            }
            if (node.right != null) {
                nextLevel.add(node.right);
            }
            if (i == currentLevel.size()) {
                if (currentNeg > maxNeg) {
                    maxNeg = currentNeg;
                    levelWithMaxNeg = levelNo;
                }
                levelNo++;
                currentNeg = 0;
                currentLevel.clear();
                currentLevel.addAll(nextLevel);
                nextLevel.clear();
                i = 0;
            }
        }
        System.out.println("Level with the most num of negetive number: " + levelWithMaxNeg);
    }