Amazon Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: Phone Interview
That %2 business is not required. Just return node.value - lv - rv no matter what. That'll give you odd - even, assuming the root is at odd level. Invert the value obtained in the end to get even - odd.
f(root) = root.value - f(root.left) - f(root.right)
= root.value - [root.left.value - f(root.left.left) -
f(root.left.right)] - [root.right.value - f(root.right.left) - f(root.right.right)]
= root.value - root.left.value - root.right.value + f(root.left.right) + f(root.left.left) + f(root.right.left) + f(root.right.right)
You see where it's going.
/// public static int findDiff(Tree root)
{
if (root == null)
return 0;
return root.item - (findDiff(root.left) + findDiff(root.right));
}
\\\
Difference of nodes' values at odd and even level is nothing but root's value-(sum of root immediate children nodes' values)
private static int findDiff(Node node) {
if (node == null)
return 0;
int leftValue = findDiff(node.left);
int rightValue = findDiff(node.right);
return node.value - (leftValue + rightValue);
}
Thanks.
public int calcDiff(Node root){
Node temp = root;
int odd =0;
int even =0;
while(temp!=null){
odd=odd+temp.val;
temp=temp.next.next;
}
temp =root.next;
while(temp!=null){
even =even+temp.val;
temp=temp.next.next;
}
return odd-even;
}
it might be a answer to the question:
public class Main {
public int calculateDiff(TreeNode rootNode) {
return calculateNodeValue(rootNode, true);
}
public int calculateNodeValue(TreeNode theNode, boolean isOdd) {
if (theNode == null)
return 0;
int childsValue = 0;
if (theNode.childs != null)
for (TreeNode childNode : theNode.childs) {
childsValue += calculateNodeValue(childNode, !isOdd);
}
return theNode.value - childsValue;
}
class TreeNode {
public int value;
public List<TreeNode> childs;
}
}
Question Should be -
Write a function to calculate the difference between ( the sum of all node-values at even levels) and (sum of node-values at odd levels) of a Tree .
So much for Attention to details.
Here is the recursive implementation
int treeNodeSum ( TreeNode* root, int level, bool isEvenSum )
{
if(!root) return 0;
int leftChildSum = treeNodeSum(root->left, level+1, isEvenSum);
int rightChildSum = treeNodeSum(root->right, level+1, isEvenSum);
if( ( isEvenSum && level%2 == 0 )|| (!isEvenSum && level%2 == 1)) {
return root->data + leftChildSum + rightChildSum;
}
return 0;
}
//invoke using call once for even once for odd with root and lvl 0
int diff == treeNodeSum(root, 0, true) - treeNodeSum(root, 0, false);
template <class T>
int BinaryTree<T>::DiffBWOddAndEvenLevelSums()
{
int evemsum = 0;
int oddsum = 0;
_DiffBWOddAndEvenLevelSums(m_Root, evemsum, oddsum);
return (evemsum - oddsum);
}
template <class T>
void BinaryTree<T>::_DiffBWOddAndEvenLevelSums(BinaryTreeNode<T>* node, int& sum1, int& sum2)
{
if (node)
{
sum1 += node->m_Data;
_DiffBWOddAndEvenLevelSums(node->m_Left, sum2, sum1);
_DiffBWOddAndEvenLevelSums(node->m_Right, sum2, sum1);
}
}
private static int findDiff(BTNode node,int level) {
- MVVSK December 09, 2012if(node == null)
return 0;
int lv = findDiff(node.left, level+1);
int rv = findDiff(node.right, level+1);
if(level % 2 == 0){
return node.value + lv + rv;
}
else{
return node.value*-1 + lv +rv;
}
}