Amazon Interview Question
SDE1sTeam: TCS
Country: India
Interview Type: Written Test
I like your flip idea, let me modify my code for a variant of flip (but using a bool variable):
//external/global variables
BOOL evenlevel=true
evensum, oddsum (numeric type matching node values)
//wrapper for other function
sum(root)
{
evensum=oddsum=0 // reset sums
rec_sum(root) // call main recursive function
return evensum, oddsum // or return difference
}
rec_sum( node )
{
if( node == nil) return
if(evenlevel) evensum += node.val
else oddsum += node.val
evenlevel=!evenlevel //children are diff type
rec_sum(Node.left)
rec_sum(Node.right)
evenlevel=!evenlevel //back to original type
}
// calling from main
int total = getChildTotal(root, 1, root.value)
int getChildTotal(Node* node, int level, int total) {
if (node == NULL) {
return total;
} else {
childTotal = (node->left == NULL?) 0 : node->left.value + (node->right == NULL)? 0 : node->right.value;
if (level%2 == 0) {
// current node is at even height. so children are at odd height
childTotal = -childTotal;
}
total = total + childTotal;
total = getChildTotal(node->left, level+1, total);
total = getChildTotal(node->right, level+1, total);
return total;
}
}
GLOBAL VARS:
h=0, even, odd
//wrapper for other function
sum( node)
{
even=odd=0 // reset sums
h=0 // not really needed ( rec_sum will unwind it to 0 )
rec_sum(node)
return even, odd
}
rec_sum( node )
{
if( node == nil) return;
if(h%2==0)
even+= node.val
else
odd+= node.val
++h // increment height value for my children
sum(Node.left)
sum(Node.right)
--h // unwind height
}
//external/global variables
h=0, even, odd
//wrapper for other function
sum( node)
{
even=odd=0 // reset sums
h=0 // not really needed
rec_sum(node)
return even, odd
}
rec_sum( node )
{
if( node == nil) return
if(h%2==0) even+= node.val
else odd += node.val
++h // increment height value for my children
sum(Node.left)
sum(Node.right)
--h // unwind height
}
Here you go in C#:
int SumEvenOdd(Tree root)
{
return SumEvenOdd(root, true);
}
int SumEvenOdd(Tree root, bool isPositive)
{
if (root == null)
{
return 0;
}
int a = 1;
if (isPositive)
{
a = -1;
}
return root.Value * a + SumEvenOdd(root.Left, !isPositive) + SumEvenOdd(root.Right, !isPositive);
}
Sample Function In Java
public int heightDiff(Node root) {
int evenSum = 0;
int oddSum = 0;
int height = 0;
int count = 0;
Queue<Node> queue = new LinkedList<Node>();
if (root == null)
return 0;
queue.add(root);
while (!queue.isEmpty()) {
height++;
count = queue.size();
while (count > 0) {
root = queue.poll();
int x = Integer.parseInt(root.get().toString());
if (height % 2 == 0) {
evenSum += x;
} else {
oddSum += x;
}
if(root.left!=null) queue.add(root.left);
if(root.right!=null) queue.add(root.right);
count--;
}
}
return oddSum - evenSum;
}
public int sumofNodes(TreeNode node, boolean oddLevel)
{
if (node == null)
return 0;
int sum=sumofNodes(node.leftchild, !oddLevel)
+ sumofNodes(node.rightchild, !oddLevel);
if (oddLevel)
return node.data + sum;
else
return sum;
}
public void oddEvenDifference(TreeNode node)
{
System.out.println(Math.abs(sumofNodes(node, true) - sumofNodes(node, false)));
}
int EvenSum=0,OddSum=0;
void SumEveOddLevels(struct tree *root,int level)
{
if(root)
{
if(level%2)
OddSum+=root->data;
else
EvenSum+=root->data;
SumEveOddLevels(root->left,level+1);
SumEveOddLevels(root->right,level+1);
}
}
#include <stdio.h>
#include <stdlib.h>
struct node {
int val;
struct node* left;
struct node* right;
};
void rec_calcDiff(struct node* root, int height, long int* evenSum, long int* oddSum) {
if(root == NULL)
return;
rec_calcDiff(root->left, height+1, evenSum, oddSum);
rec_calcDiff(root->right, height+1, evenSum, oddSum);
if(height%2 == 0)
*evenSum += root->val;
else
*oddSum += root->val;
return;
}
long int calcDiff(struct node* root) {
int height=1;
long int evenSum=0, oddSum=0;
rec_calcDiff(root, height, &evenSum, &oddSum);
return (oddSum - evenSum);
}
struct node* createNode(int val) {
struct node* newNode = (struct node*) malloc(sizeof(struct node));
newNode->val = val;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
main()
{
struct node* root = createNode(7);
root->left = createNode(8);
root->right = createNode(4);
root->left->left = createNode(33);
root->left->right = createNode(77);
root->right->right = createNode(3);
printf("%ld\n", calcDiff(root));
return 0;
}
why is itjt's answers downvoted? it works!
template<>
int tree<int>:: oddevensum()
{
deque<node<int>* > myq1;
deque<node<int>* > myq2;
node<int>* temp;
int sum=0;
myq1.push_back(root);
while(!(myq1.empty()) || !(myq2.empty()))
{
//odd levels
while( !(myq1.empty()) )
{
temp=myq1.front();
sum+= temp->val;
if(temp->left) myq2.push_back( temp->left );
if(temp->right) myq2.push_back( temp->right );
myq1.pop_front();
}
while( !(myq2.empty()) )
{
temp=myq2.front();
sum-= temp->val;
if(temp->left) myq1.push_back( temp->left );
if(temp->right) myq1.push_back( temp->right );
myq2.pop_front();
}
}
return sum;
}
diffOddEvenHeights(){
int evenSum = 0;
int oddSum = 0;
diffOddEvenHeightsHelper(rootNode, evenSum, oddSum, 0);
return oddSum - evenSum;
}
diffOddEvenHeightsHelper(Node* root, int& even, int& odd, int level){
if (root){
diffOddEvenHeightsHelper(root->left, even, odd, level+1);
if (level & 1)
odd += root->data;
else
even += root->data;
diffOddEvenHeightsHelper(root->right, even, odd, level + 1);
}
}
Typical level order or breath first traversal to figure out the even and the odd sums. You only need a single queue and boolean flag toggling between even and odd. You can sum up the odd and even values using BFS and then print the difference.
int total = getChildTotal(root, 1, root.value)
int getChildTotal(Node* node, int level, int total) {
if (node == NULL) {
return total;
} else {
childTotal = (node->left == NULL?) 0 : node->left.value + (node->right == NULL)? 0 : node->right.value;
if (level%2 == 0) {
// current node is at even height. so children are at odd height
childTotal = -childTotal;
}
total = total + childTotal;
total = getChildTotal(node->left, level+1, total);
total = getChildTotal(node->right, level+1, total);
return total;
}
}
Pseudocode:
int calcDifference(start, odd, result) {
if(odd)
result += start.value;
else
result -= start.value
result = calcDifference(start.left, !odd, result);
result = calcDifference(start.right, !odd, result)
return result;
}
calcDifference(root, true, 0);
The key is to traverse all of the nodes, flipping an odd/even flag as you go down a level.
You could traverse the tree breadth first. Maintain two queues: an odd queue and an even queue. Enqueue the children of odd queue elements in the even queue and vice versa. You could use a signed diff variable and add to or subtract from it depending on whether it's an odd or even element.
- joyboyhardik September 28, 2013