Amazon Interview Question
Developer Program EngineersCountry: Spain
Interview Type: Written Test
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;
}
@cyrus: I don't know which logic you are following. But only leaf node will become 0 not internal nodes.
Go through my code again for better understanding.
I understood like this :-
If a binary tree is given, convert it into a binary tree where each node is the sum of its childrens.
---------------------------
Input
1
/ \
3 4
/ \
5 6
-------------------------------
Output
18
/ \
11 0
/ \
0 0
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());
}
}
- Nitin Gupta January 24, 2013