Amazon Interview Question Software Engineer in Tests
Country: India
Interview Type: Phone Interview
void changenodeVal(node1 p)
{
int leftval=0,rightval=0;
if(p!=null)
{
if(p.left!=null)
{
leftval=p.left.val;
}
if(p.right!=null)
{
rightval=p.right.val;
}
changenodeVal(p.left);
changenodeVal(p.right);
if(p.left!=null&&p.right!=null)
p.val=leftval+rightval+p.left.val+p.right.val;
else
p.val=leftval+rightval;
}
}
hi akshay.shetye, i think the code will be like this because when you store it parent node it will update parent own value also.which could not recieved by grandparent. and i think it will update all node of tree with '0' value.
plz correct me if am wrong..
int sum(struct node* root)
{
if(root==null)return 0;
if(root->left==null) root->left->data=0; //correct me here if i am wrong
if(root->right==null) root->right->data=0;
root->data=root->left->data + root->right->data +sum(root->left)+sum(root->right);
return 0;
// i think every node of binary tree has been modified.
}
if(root->left==null) root->left->data=0; //correct me here if i am wrong
if(root->right==null) root->right->data=0;
This i wrong.. If root->left is NULL, how can you assign data to NULL node..
Following will work...
int sum(struct node* root)
{
if(root==null)return 0;
if(root->left!=null)
root->data = sum(root->left->data) + root->right->data
else
root->data = 0;
if(root->right!=null)
root->data += sum(root->right->data) + root->right->data
else if(root->left == NULL)
root->data = 0;
else
root->data += 0;
return 0;
}
//how is it??pls check
int sum(struct node* root)
{
if(root==null)return 0;
int i=root->data;
root->data=root->left->data + root->right->data +sum(root->left)+sum(root->right);
return root->data+i;
}
@bg i knew that but i did not know wht to do. because i had to give that condition.
by the way you should pass argument ass node pointer in your function ,not value
sum(roo->link->data) //this is wrong,pass here link of node :)
Abhra
Your code will have unexpected behavior. C/C++ does not guarantee any ordering of summation, which means the summation can be executed in any order and you can get different answers each time.
This has been posted before. The keypoint is to label every node with an index from left to right.
void SumFromLeftToRight(TreeNode* root, hash_map<int, int>& sums)
{
if(root == NULL)
return;
stack<TreeNode*> s;
stack<int> sIndex;
TreeNode* current = root;
int currentIndex = 0;
while(current != NULL || !s.empty())
{
if(current != NULL)
{
if(sums.find(currentIndex) == sums.end())
sums[currentIndex] = 0;
sums[currentIndex] += current->value;
s.push(current);
sIndex.push(currentIndex);
--currentIndex;
current = current->left;
}
else
{
current = s.top();
currentIndex = sIndex.top();
s.pop();
sIndex.pop();
if(current->right != NULL)
{
++currentIndex;
}
current = current->right;
}
}
}
<pre lang="" line="1" title="CodeMonkey31442" class="run-this">class Sum {
public int childSum(Node root) {
if(root == null) {
return 0;
}
int returnVal = root.getData();
int lsum = sum(root.getLeft());
int rsum = sum(root.getRight());
root.setData(lsum + rsum);
return returnVal;
}
}
</pre><pre title="CodeMonkey31442" input="yes">
</pre>
Note: I think , you have written sum in the place of childSum
Ignoring that,
Idon't think your code would serve the purpose. If you execute your code say for -2 in the example, you would store 4 in place of -2 and return -2, which is wrong. You should return 4+-2 because for root(10 here) we would need the sum of left child which is 2. I think changing the last line from
"return returnVal" to "return returnVal+root.getData()" would work
Why not write an iterative postorder. In visit instead of printing take the sum of left and right trees. any comments?
Hi, i attended the interview process last week, the same qns were asked... Where was your interview? Banglore or chennai?
int sumify(Node *root)
{
if (root == NULL)
{
root->sum = root->data;
}
else
{
root->sum = sumify(root->left) + sumify(root->right) + root->data;
}
return root->sum;
}
static void findSum(int n){
if (a1[(2*n)] == 0 || a1[(2*n)+1] == 0 ){
return ;
}
else
{
findSum(2*n);
findSum(2*n+1);
b1[n] = a1[2*n] + a1[2*n+1];
int temp = a1[n];
a1[n] = a1[2*n] + b1 [2*n] + a1 [2*n + 1] + b1 [2*n + 1];
b1[n] = temp ;
}
}
given a1 array with index starting from 1, call findSum(1) . Here terminating condition i have assumed the child of leaf node has value 0 . It will return everything corect except for leaf nodes whose value would be 0 in all the cases
void changenodeVal(node1 p)
{
int leftval=0,rightval=0;
if(p!=null)
{
if(p.left!=null)
{
leftval=p.left.val;
}
if(p.right!=null)
{
rightval=p.right.val;
}
changenodeVal(p.left);
changenodeVal(p.right);
if(p.left!=null&&p.right!=null)
p.val=leftval+rightval+p.left.val+p.right.val;
else
p.val=leftval+rightval;
}
}
- akshay.shetye November 20, 2011int sumify(Node node){ if(node == null) return 0; else{ int tmp = node.data; node.data = sumify(node.left)+sumify(node+right); return node.data+tmp; //corrected this } }