Amazon Interview Question Software Engineer / Developers
Country: India
Interview Type: Written Test
Where is odd values summing going on ??? We have to add the values at odd levels of left and subtract it from odd levels of value of right !
He makes the value of each node equal to it's value minus the value of it's children. Because each node negates its children, and summing doesn't matter what order we do it in, this works out. Example:
A root of value 10 with children values 5 and 3 will have total value 10 - (5+3) = 2.
If the 3 node has another child of value 2, then we subtract that before proceeding, getting
10 - (5 + (3 - 2)) =
10 - (5 + 3) + 2 = 4
The last child will effectively get negated twice, making it positive again. Though really it just collapses into the 3, reducing it to 1.
public static int calcDifference(TreeNode root)
{
int[] result = findOddSumAndEvenSum(root, true, new int[]{0,0});
return result[0] - result[1];
}
public static int[] findOddSumAndEvenSum(TreeNode root, boolean isOdd, int[] oddEvenSum)
{
if(root == null)
return new int[]{0, 0};
if(isOdd)
oddEvenSum[0] = oddEvenSum[0] + root.getValue();
else
oddEvenSum[1] = oddEvenSum[1] + root.getValue();
findOddSumAndEvenSum(root.getLeftNode(), !isOdd, oddEvenSum);
findOddSumAndEvenSum(root.getRightNode(), !isOdd, oddEvenSum);
return oddEvenSum;
}
A small correction
if(root.getLeftNode()!=null){
findOddSumAndEvenSum(root.getLeftNode(), !isOdd, oddEvenSum);
}
if(root.getRightNode()!=null){
findOddSumAndEvenSum(root.getRightNode(), !isOdd, oddEvenSum);
}
otherwise you will end up returning {0,0} as soon as you encounter the leftchild as null
#include<iostream.h>
#include<queue.h>
using namespace std;
struct node {
int data;
node * left;
node * right;
};
struct node * newNode( int x )
{
struct node * temp = (struct node*)malloc (sizeof(struct node));
temp->data =x;
temp->left = NULL;
temp->right = NULL;
}
int printDifference( struct node * root)
{
if(root == NULL)
return 0 ;
int odd = -1;
queue<node*> q;
q.push (root);
int currentlevel = 1;
int nextlevel = 0;
int oddsum=0;
int evensum =0;
while( !q.empty())
{
node * current = q.front();
q.pop();
currentlevel--;
if(current)
{
//printf("%d ", current->data);
if(odd)
{
oddsum = oddsum + current->data;
}
else
evensum = evensum+current->data;
if(current->left)
{
q.push(current->left);
nextlevel++;
}
if(current->right)
{
q.push(current->right);
nextlevel++;
}
}
if(currentlevel == 0)
{
//printf("\n");
currentlevel = nextlevel;
nextlevel = 0;
//printf("%d\n", odd);
odd = ~odd;
//printf("%d\n", odd);
}
}
// printf("%d\n", oddsum);
//printf("%d\n", evensum);
return (oddsum-evensum);
}
int main ()
{
node *root = newNode(2);
root->left = newNode(4);
root->right = newNode(12);
root->left->left = newNode(8);
root->left->right = newNode(6);
root->right->left = newNode(10);
root->right->right = newNode(14);
printf ("%d ", printDifference(root));
getchar();
return 0;
}
int OddLevelSum=0, EvenLevelSum=0;
int calcDiff(node *Root, int level){
if(level%2){/*Odd Level*/
OddLevelSum=OddLevelSum+Root->info;
}else{/*Even Level*/
EvenLevelSum=EvenLevelSum+Root->info;
}
calcDiff(Root->left, level+1);
calcDiff(Root->right, level+1);
return modDiff(OddLevelSum, EvenLevelSum);
}
A little correction in the existing code
int OddLevelSum=0, EvenLevelSum=0;
int main() {
calcDiff(Root, 1);
printf("Result : %d", (OddLevelSum - EvenLevelSum));
return 0;
}
void calcDiff(node *Root, int level){
if(level%2){/*Odd Level*/
OddLevelSum=OddLevelSum+Root->info;
}else{/*Even Level*/
EvenLevelSum=EvenLevelSum+Root->info;
}
calcDiff(Root->left, level+1);
calcDiff(Root->right, level+1);
return;
}
I removed the return at the end of calcDiff() function because return will be called many times upon the popping of system stack at the end of " calcDiff(Root->right, level+1);" line.
I hope am on the right track. Please correct me if am wrong some where.
Cheers
class TreeNode {
int data;
TreeNode left;
TreeNode right;
public TreeNode(int data)
{
this.data = data;
left = right =null;
}
}
/**
* Actual Calculation is implemented in calcDiff(root) where the root node is
* passed.
*
*/
class Calc {
public static void main(String [] args)
{
TreeNode root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);
root.right.left = new TreeNode(6);
root.right.right = new TreeNode(7);
System.out.println(diff(root));
}
public static int diff(TreeNode n) {
return sumtree(n, 1);
}
public static int sumtree(TreeNode n, int level) {
if (n == null) return 0;
if (level % 2 == 0) {
return sumtree(n.left, level + 1) + sumtree(n.right, level +1 ) - n.data;
} else {
return sumtree(n.left, level + 1) + sumtree(n.right, level + 1) + n.data;
}
}
}
I use two queue to do this work. And it works well, because I take level traversal, so the time using is O(n).
#include<iostream>
#include<queue>
using namespace std;
typedef struct node{
int data;
struct node *left, *right;
}BTNode, *Tree;
#define NIL 0
int a[] = {1, 2, 4, 0, 0, 5, 0, 0, 3, 6, 0, 0, 7, 0, 0};
static int i = 0;
void pre_order_create(Tree &T) {
int num = a[i++];
if(num == NIL) {
T = NULL;
} else {
T = (BTNode*)malloc(sizeof(BTNode));
T->data = num;
pre_order_create(T->left);
pre_order_create(T->right);
}
}
calculate_diff(Tree T, int *odd_sum, int *even_sum) {
queue<BTNode*> *m_queue1 = new queue<BTNode*>();
queue<BTNode*> *m_queue2 = new queue<BTNode*>();
queue<BTNode*> *temp_queue;
BTNode *temp;
int level = 1;
int *sum;
m_queue1->push(T);
while(!m_queue1->empty()) {
if(level % 2 == 1) {
sum = odd_sum;
} else {
sum = even_sum;
}
while(m_queue1->size() > 0) {
temp = m_queue1->front();
(*sum) += temp->data;
if(temp->left) {
m_queue2->push(temp->left);
}
if(temp->right) {
m_queue2->push(temp->right);
}
m_queue1->pop();
}
level++;
temp_queue = m_queue1;
m_queue1 = m_queue2;
m_queue2 = temp_queue;
}
}
void main() {
Tree T = NULL;
pre_order_create(T);
int odd_sum = 0;
int even_sum = 0;
calculate_diff(T, &odd_sum, &even_sum);
cout << "odd_sum=" << odd_sum << ",even_sum=" << even_sum << endl;
getchar();
}
private static void calcDifference(final Node root) {
ArrayList<Node> list, tList;
list = new ArrayList<>();
list.add(root);
int evenListSum = 0, oddListSum = root.value, height = 1;
while (true) {
int size = list.size();
if (size == 0) {
return;
}
int i = 0;
tList = new ArrayList<>();
while (i < size) {
Node n = list.remove(0);
if (n.left != null) {
tList.add(n);
if (height % 2 != 0) {
evenListSum = evenListSum + n.left.value;
} else {
oddListSum = oddListSum + n.left.value;
}
}
if (n.right != null) {
tList.add(n);
if (size % 2 != 0) {
evenListSum = evenListSum + n.right.value;
} else {
oddListSum = oddListSum + n.right.value;
}
}
}
list = tList;
height++;
i++;
}
}
void SumDiff(Tree *root, int num, int *Sum1, int *Sum2)
{
if(root != NULL)
{
if(num % 2 == 0)
{
*Sum2+= root->data;
SumDiff(root->left, num +1, Sum1, Sum2);
SumDiff(root->right, num +1, Sum1, Sum2);
}
else
{
*Sum1+= root->data;
SumDiff(root->left, num +1, Sum1, Sum2);
SumDiff(root->right, num +1, Sum1, Sum2);
}
}
}
private static void findEvenOddSum(Node node) {
// Add the root node
List<Node> list = new ArrayList<Node>();
list.add(node);
// Pass the arguments,
//list : Nodes to process at current level, isOdd : level is odd or even 3. difference : difference between odd and even
findSum(list, true, 0);
}
private static void findSum(List<Node> list, boolean isOdd , int difference) {
final int elementSize = list.size();
//If no more elements to process
if(elementSize == 0){
System.out.println("Difference between odd and even is : " + difference);
return;
}
int sumAtLevel = 0;
//Find the nodes for processing
for(int i=0; i< elementSize; i++){
//Take from the list and remove. We can use queue instead
Node n = list.get(0);
list.remove(0);
//Add to sum at current level
sumAtLevel += n.data;
// Find the left node for further processing
if(n.left != null)
list.add(n.left);
//Find the right node for further processing
if(n.right != null)
list.add(n.right);
}
// Operate on difference based on the level
if(isOdd)
difference += sumAtLevel;
else
difference -= sumAtLevel;
// Switch the level and pass the other items
findSum(list, !isOdd, difference);
}
Just recursion
- peng January 13, 2013int calcDiff(node * root)
{
if(root==NULL)
return 0;
int tmp= root->val - calcDiff(root->left)-calcDiff(root->right);
return tmp;
};