CareerCup

int sumUp(struct node* root)
{
     if(root == NULL) return 0;
     int curr = root->data;
     int left = sumUp(root->left);
     int right = sumUp(root->right);
     root->data = left + right;
     return (curr + root->data);
}

Make the question little more interesting, You can increase the node value at any instance but can't decrease. and always node->value=sumof(left subtree , right subtree).

Wow.. I don't believe this can be SDE Amazon question.

All here is the Segment Tree Formation.. U gotto be Kidding

this will convert all tree nodes to 0 as sumUp will first calculate sum on leaf nodes. and Smash!!!!

So if amazon is asking this question you must check this condition too.
sum function should not be called for leaf nodes. Coz leaf node don't have any children.

int sumUp(struct node* root)
{
     if(root == NULL) return 0;
	 if(root->left == NULL && root->right == NULL) return root;
     root->data = sumUp(root->left) + sumUp(root->right);
     return root->data;
}

TreeSum(root)
	if(root == null)
		return null;
	Node x = TreeSum(root.left);
	Node y = TreeSum(root.right); 
	Node n = new Node();
	n.value = root.value + x!=null?x.value:0 + y!=null?y.value:0;
	n.left = x;
	n.right = y;
	return n;

package tree;

import java.util.LinkedList;


public class BtreeChildSumInParent {
private BtreeNode root;
private LinkedList<BtreeNode> Q = new LinkedList<BtreeNode>();

public void insert(int data) {
if (root == null) {
root = new BtreeNode();
root.setData(data);
root.setSum(0);

} else {
Q.add(root);
while (!Q.isEmpty()) {
BtreeNode temp = Q.remove();
if (temp.getLeft() == null) {
BtreeNode newnode = new BtreeNode();
newnode.setData(data);
temp.setLeft(newnode);
root.setSum(root.getSum() + data);
break;
} else {
Q.add(temp.getLeft());

}
if (temp.getRight() == null) {
BtreeNode newnode = new BtreeNode();
newnode.setData(data);
temp.setRight(newnode);
root.setSum(root.getSum() + data);
break;
} else {
Q.add(temp.getRight());

}
}
Q.clear();
}

}

public class BtreeNode {
private int data;
private int sum;
private BtreeNode right;
private BtreeNode left;

public BtreeNode() {
this.right = null;
this.left = null;
this.sum = 0;
this.data = 0;
}

public int getData() {
return data;
}

public void setData(int data) {
this.data = data;
}

public int getSum() {
return sum;
}

public void setSum(int sum) {
this.sum = sum;
}

public BtreeNode getRight() {
return right;
}

public void setRight(BtreeNode right) {
this.right = right;
}

public BtreeNode getLeft() {
return left;
}

public void setLeft(BtreeNode left) {
this.left = left;
}

}

public void inorder(BtreeNode r) {
if (r == null) {
return;
}
inorder(r.getLeft());
if (r.getLeft() != null && r.getRight() != null) {
r.setSum(r.getLeft().getData() + r.getRight().getData());
System.out.print(" [" + r.getData() + " Sum " + r.getSum()
+ "] ");
} else
System.out.print(r.getData());
inorder(r.getRight());
}

public BtreeNode getRoot() {
return root;
}

public void setRoot(BtreeNode root) {
this.root = root;
}

public LinkedList<BtreeNode> getQ() {
return Q;
}

public void setQ(LinkedList<BtreeNode> q) {
Q = q;
}

public static void main(String[] args) {
BtreeChildSumInParent btree = new BtreeChildSumInParent();
btree.insert(50);
btree.insert(1);
btree.insert(2);
btree.insert(3);
btree.insert(4);
btree.insert(5);
btree.insert(6);
btree.inorder(btree.getRoot());

}

}

that is very easy just have an int NumberOfChildren for each node in the class and increment or decrement if inserting or deleting from tree accordingly for the parent node. I just tried it had to add 2 lines to my code.