## Bloomberg LP Interview Question

Software Engineer / Developers**Country:**United States

**Interview Type:**In-Person

Use spiral level order traversal technique.

Take two sum varialbe oddSum and evenSum and two stacks s1 and s2.

Take one boolean variable evenLevel.

java code is below:

```
public int maxAmountRob(BTNode<T> node) {
if (node == null) {
return;
}
Stack<BTNode<T>> stack1 = new Stack<>();
Stack<BTNode<T>> stack2 = new Stack<>();
stack2.push(node);
boolean levelFlag = false;
int oddSum=0;
int evenSum=0;
while (!(stack1.isEmpty() && stack2.isEmpty())) {
BTNode<T> currentNode;
if (levelFlag) {
while (!stack1.isEmpty()) {
currentNode= stack1.pop();
oddSum+=currentNode.getData();
if(currentNode.getLeft() != null){
stack2.push(currentNode.getLeft());
}
if(currentNode.getRight() != null){
stack2.push(currentNode.getRight());
}
}
levelFlag = false;
} else {
while (!stack2.isEmpty()) {
currentNode= stack2.pop();
evenSum+=currentNode.getData();
if(currentNode.getRight() != null){
stack1.push(currentNode.getRight());
}
if(currentNode.getLeft() != null){
stack1.push(currentNode.getLeft());
}
}
levelFlag = true;
}
}
return Math.max(oddSum,evenSum);
```

}

I used normal post-order traversal with a method parameter indicating the level.

```
public static int maxLevelSum(TreeNode root){
int[] sums = getSums(root, 0);
return Math.max(sums[0], sums[1]);
}
public static int[] getSums(TreeNode node, int level){
int[] res1 = new int[2];
int[] res2 = new int[2];
if (node.left != null)
res1 = getSums(node.left, level+1);
if (node.right != null)
res2 = getSums(node.right, level+1);
if (level %2 ==0){
return new int[]{res1[0]+res2[0], res1[1]+res2[1]+ node.val};
}
else{
return new int[]{res1[0]+res2[0] + node.val, res1[1]+res2[1]};
}
```

Python Solution:

def maxLevelSum(root,EvenOrOdd,sumation):

if root == None:

return max(sumation[0],sumation[1])

else:

if EvenOrOdd == True:

sumation[0] += root.val

else:

sumation[1]+= root.val

maxLevelSum(root.left,not EvenOrOdd,sumation)

maxLevelSum(root.right,not EvenOrOdd,sumation)

return max(sumation[0],sumation[1])

print(maxLevelSum(tr,True,[0,0]))

{{

def maxLevelSum(root,EvenOrOdd,sumation):

if root == None:

return max(sumation[0],sumation[1])

else:

if EvenOrOdd == True:

sumation[0] += root.val

else:

sumation[1]+= root.val

maxLevelSum(root.left,not EvenOrOdd,sumation)

maxLevelSum(root.right,not EvenOrOdd,sumation)

return max(sumation[0],sumation[1])

print(maxLevelSum(root,True,[0,0]))

}}

def maxLevelSum(root,EvenOrOdd,sumation):

if root == None:

return max(sumation[0],sumation[1])

else:

if EvenOrOdd == True:

sumation[0] += root.val

else:

sumation[1]+= root.val

maxLevelSum(root.left,not EvenOrOdd,sumation)

maxLevelSum(root.right,not EvenOrOdd,sumation)

return max(sumation[0],sumation[1])

I assume it's a level order traversal where you build two sums, one of even levels and one of odd. levels

I used a nullptr as a marker element to seperate levels in the queue, tiny trick is to ensure the termination

works.

- Chris December 14, 2016