CareerCup

u must be joking,or he must be joking.I don't see how is this correct if complete.

<pre lang="" line="1" title="CodeMonkey89970" class="run-this">int main()
{
int sum = traverseNode(rootNode, 0);
}
int traverseNode(Node x, sum)
{
if(x.left != null)
{
sum += traverseNode(x.left);
}
if(x.right != null)
{
sum += traverseNode(x.right);
}
if(x.left == null && x.right == null)
{
sum += x.value;
}
return sum;
}</pre><pre title="CodeMonkey89970" input="yes">
I gave it shot.</pre>

i think the above soul wont work, hes finding the sum of nodes with no leafs but thats not the question is r8??

int sum = 0;
void nosiblsum(node* n)
{
if(!n || (n->left==NULL && n->right==NULL)
return ;
if(n->left == NULL && n->right!= NULL)
{
sum += n->right->data;
nosiblsum(n->right);
}
else if(n->right == NULL && n->left != NULL)
{
sum += n->right->data;
nosiblsum(n->left);
}
else
{
nosiblsum(n->left);
nosiblsum(n->right);
}
}

Do a BFS here is the pseudo code.

1. Enque(Root), sum = 0
2. While Q is not empty repeat 3  to 11.
3.     r=Dqueue();
4.     if(!(r->lClild && r->rChild))
5.         if(r->lChild) 
6.              sum = sum + r->Child.data;
7.         else if (r->rChild) 
8.              sum = sum + r->rChild.data;
9.     if(r->lChild) Enqueue(r-rChild);
10.    if(r->rChild) Enqueue(r->lChild)   
11. Go to 2.
12. Return Sum

public static int nodesWithNoSiblings(TreeNode node) {
if (node == null) {
return 0;
}
int leftChildrenWithNoSiblings = nodesWithNoSiblings(node.getLeft());
int rightChildrenWithNoSiblings = nodesWithNoSiblings(node.getRight());
int currentCount = (node.getLeft()==null?1:0) + (node.getRight()==null?1:0);
return currentCount + leftChildrenWithNoSiblings + rightChildrenWithNoSiblings;
}

@Anonymous
Can you pl explain the lines 9 and 10 ? I do not understand that part.

Thanks
S

Resursive solution

int CheckSumOfNoSiblings(Node node) {
    if (node->left == null && node->right != null) 
        return CheckSumOfNoSiblings(node->right) + 1;
    if (node->right == null && node->left != null)
        return CheckSumOfNoSiblings(node->left) + 1;
    if (node->left != null && node->right != null)
        return CheckSumOfNoSiblings(node->left) + CheckSumOfNoSiblings(node->right);
    return 0;
}

int sumUpNodesWOSiblings(tnode* aRoot)
{
static int res;
if(aRoot)
{
sumUpNodesWOSiblings(aRoot->m_left);
if(aRoot->m_left && !aRoot->m_right)
res+=aRoot->m_left->m_data;
if(!aRoot->m_left && aRoot->m_right)
res+=aRoot->m_right->m_data;
sumUpNodesWOSiblings(aRoot->m_right);
}
return res;
};

int sumNotsibling(struct node *r)
{int sum=0;
if(!r)
return;
if(r->left && !r->right )
sum++;
if(r->left && !r->left)
sum++;
sum=sum+sumNotsiblings(r->left)+sumNotsiblings(r->right);
return sum;
}





}

public int sumOfSib(Node n,int sum){

if(n==null){
return 0;
}
int lsum = sumOfSib(n.left,sum);
int rsum = sumOfSib(n.right,sum);
if(n.left!=null && n.right ==null){

sum =sum + n.left.data;

}
if(n.right!=null && n.left ==null){
sum = sum +n.right.data;

}
return sum+lsum+rsum;
}



The above code in Java

Initially the sum in zero and then you add the root data to the sum to get the final answer

Hey all... What do you guys think about the following code?

static int sum = 0;

int findSum(node *tree)
{
    if(tree->left == null && tree->right ==null)
    {
        // Means that it is a leaf node...

        sum += sum->value;
        return;
    }

    if(tree->right != null)
        findSum(tree->right);

    if(tree->left != null)
        findSum(tree->left);

}

int noSibSum(node* root)
{
    if(root == NULL ||(root->left==NULL && root->right == NULL))
    return 0;
    if(root->left!=NULL && root->right == NULL)
      return root->left->data + noSibSum(root->left);
      else if(root->right!=NULL && root->left == NULL)
      return root->right->data+noSibSum(root->right);
      else{
          return noSibSum(root->left)+noSibSum(root->right);
      }
}