CareerCup

struct
{
int data;
tree* left;
tree* right;
}tree;
int findDiffSum(tree* node)
{
return node.data - (findDiffSum(node->left)+findDiffSum(node->right));
}

int main()
{
tree* root= giventree; //our focus here is not to construct the tree i suppose
printf("%d", findDiffSum(root));
}

as i interpreted the question i think just use the 2 quees and every time maintain the two counters for even level and for odd level when the nodes whole tree traversed just return the diifernec between the dsese two counters .
code ::
// there are two quees
int DiffODDEVEN(struct node *r)
{int odd=0;
int even=0;
struct node *temp;
if(!r)
return 0;
enquee1(r);
while(front1!=NULL || front2!=NULL)
{
while(front1!=NULL)
{
temp=dequee1();
even++;
if(temp->left)
enquee2(temp->left);
if(temp->right)
enquee2(temp->right);
}
while(front2!=NULL)
{
temp=dequee2();
odd++;
if(temp->left)
enquee1(temp->left);
if(temp->right)
enquee1(temp->right);

}
}
return(abs(odd-even));
}


}

pseudo code:

modifiedPreorder(node, level)
{
static int evenSum=0, oddSum=0;
if(node==null)
return 0;
else
{
if(level%2==0)
evenSum+=node->data;
else
oddSum+=node->data;
modifiedPreorder(node->left, level+1);
modifiedPreorder(node->right,level+1);
}
return evenSum-oddSum;
}

I think it can be done using only one queue, below is the algo, please have a look:

01. Q.Enqueue(root), evenSum=0, oddSum=0, count=1, 
    curCount=0, isEvenLevel=true, isOddLevel=false, curSum=0
02. while Q is not empty 
03.        while(count)
04.            curNode=Q.Dequeue()
05.	          if(curNode->left)
06.		       curCount++
07.		       Q.Enqueue(curNode->left)
08.	          if(curNode->right)
09.		       curCount++
10.		       Q.Enqueue(curNode->right)
11.            sum += curNode->data
12.       count=curCount
13.       curCount=0;
14.       if(isEvenLevel==true)
15.           evenSum+=sum
16.           isEvenLevel=false
17.	      isOddLevel=true
18.      else
20.          oddSum+=sum
21.          isEvenLevel=true
22. 	     isOddLevel=false 
24.      sum=0
23.  return evenSum-oddSum

here by using count and curCount i m maintaining the number the node at each level.

it cane done using O(N^2) BFS to using 2 stack in O(N0 , using 1 queue in O(N) :)

int getSum(Node root, int level) {
if(root == null) {
return 0;
}
if(level%2 == 0) {
return root.data + getSum(root.right, level+1) + getSum(root.left, level+1);
}
return getSum(root.right+1) + getSum(root.left+1) - root.data;
}

I don't think we need to maintain any level or anything.

int diffBetLevel(node* root)
{
    int lvalue=0, rvalue=0;
    if(root==0) return 0;
    lvalue=diffBetLevel(root->left);
    rvalue=diffBetLevel(root->right);
    return root->data-(lvalue+rvalue);
}

It worked for in dry run:
int evenOddDiff(Node* root)
{
if(root==0) return 0;
return root->intVal - ( evenOddDiff( root->left ) + evenOddDiff ( root->right ) );
}

I think the question says diff(sum of even nodes, sum of odd nodes) - so if the tree is like this

Level 0 - 5
Level 1 - 3, 9
Level 2 - 2,4, 8,12

Sum of even nodes - 31
Sum of odd nodes - 12
The answer should be 19

I don't think the above codes give this answer. You need to accumulate the sums and take the difference at last

This is my code

int findDiff(Node* node){
int sum1 = 0;
int sum2 = 0;
int level = 0;

findDiffRecursion(node, level, sum1, sum2);

return abs(sum1-sum2);
}

void findDiffRecursion(Node* node, int level, int& sum1, int& sum2){

if(node == NULL)
return;

if(level%2==0)
sum1+=node->data;

else
sum2+=node->data;

findDiffRecursion(node->left, level+1, sum1, sum2);
findDiffRecursion(node->right, level+1, sum1, sum2);

return;
}

i go with anonymous but i think
lvalue=diffBetLevel(root->left->data);
rvalue=diffBetLevel(root->right->data);

<pre lang="" line="1" title="CodeMonkey42367" class="run-this"> public class SumEvenAndOddLevels
{
public class EvenOddSumsHelper
{
int m_sumEven;

public int SumEven
{
get { return m_sumEven; }
set { m_sumEven = value; }
}
int m_sumOdd;

public int SumOdd
{
get { return m_sumOdd; }
set { m_sumOdd = value; }
}
}

public EvenOddSumsHelper GetSumEvenAndOdd(BTreeNode node, bool even)
{
EvenOddSumsHelper sums = new EvenOddSumsHelper();
EvenOddSumsHelper left;
EvenOddSumsHelper right;

if (node.LeftNode != null)
{
left = GetSumEvenAndOdd(node.LeftNode, !even);
sums.SumEven += left.SumEven;
sums.SumOdd += left.SumOdd;
}
if (node.RightNode != null)
{
right = GetSumEvenAndOdd(node.RightNode, !even);
sums.SumEven += right.SumEven;
sums.SumOdd += right.SumOdd;
}
if (even)
sums.SumEven += (int)node.Data;
else
sums.SumOdd += (int)node.Data;
return sums;
}
}</pre><pre title="CodeMonkey42367" input="yes">
</pre>

#include <stdio.h>
#include <stdlib.h>

/* A binary tree node has data, pointer to left child
and a pointer to right child */
struct node
{
int data;
struct node* left;
struct node* right;
};

/* Function to get the count of leaf nodes in a binary tree*/
void getLeafCount(struct node* node,int l,int &even,int &odd)
{
if(node!=NULL)
if(l%2==0)
even++;
else
odd++;
else
return;

getLeafCount(node->left,l+1,even,odd);
getLeafCount(node->right,l+1,even,odd);
}

/* Helper function that allocates a new node with the
given data and NULL left and right pointers. */
struct node* newNode(int data)
{
struct node* node = (struct node*)
malloc(sizeof(struct node));
node->data = data;
node->left = NULL;
node->right = NULL;

return(node);
}

/*Driver program to test above functions*/
int main()
{
/*create a tree*/
int l,m=-1,even=0,odd=0;
struct node *root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);
root->right->left = newNode(6);

/*get leaf count of the above created tree*/
getLeafCount(root,0,even,odd);
printf("even=%d odd=%d",even,odd);

getchar();
return 0;
}