Amazon Interview Question SDE1s
Country: India
Interview Type: Written Test
This is a "true" recursive version.
Assuming sum returns the required value for a given node, then recursively what we need is (assuming root is even level)
(-sum(right)) + (-sum(left)) + (-root) which is exactly what you have.
what if we want to find (sum of values at even height)-(sum of values at ODD height) without using helper function.
The core idea is that, negative of a negative number is positive. And this can be used to find out if a level of a tree is odd or even. its similar to having a boolean and negating it at every level so that the the value flips as it goes deeper into the tree.
so,
Level -> (even, odd, even, odd, even,...) => (-1, -(-1), -(-(-1)), -(-(-(-1))), -(-(-(-(-1)))), ...) => (-1, 1, -1, 1, -1, ...)
For example,
(0) 1
/ \
(1) 2 3
/ \ / \
(2) 4 5 6 7
Level <--> Expression
2 <--> -(4+0+0), -(5+0+0)), -(6+0+0), -(7+0+0)
1 <--> -(2+ (-4) + (-5)), -(3 + (-6) + (-7))
0 <--> -(1 + (-(2+ (-4) + (-5))) + (-(3 + (-6) + (-7))))
At root => -1 + (2+3) - (4+5+6+7). Hence, the solution
Do a postorder also maintain a level, if level is odd then add the root->val otherwise subtract it.
int sum(node *root, int level){
if(root == NULL) return 0;
int left = sum(root->left, level+1);
int right = sum(root->right, level+1);
if(level%2 == 0)
return left + right - root->val;
else
return left + right + root->val;
}
Working code available at: ideone.com/X2QIIR
// above solution was using DFS, but since we have a constraint on method parameters.
// I wrote this solution using BFS
void sum(node *root)
{
queue<node *> q;
q.push(root); // push the first node in the queue
// these counts will help in discriminating between the levels
int currentNodes = 1, childNodes = 0;
while(!q.empty()){
// get the front node from the queue
node *t = q.front();
q.pop(); // pop it out
currentNodes -= 1; // decrease the currentNodes count
t->val = 0;
if(t->left) {
// if left child is not NULL, we add this value to the current node's val
t->val += t->left->val;
q.push(t->left); // push it in the queue
childNodes += 1; // increase the childNodes by one
}
if(t->right) {
t->val += t->right->val; // same here, add the value to the t->val
q.push(t->right);
childNodes += 1;
}
// this means that we finished the current level,
// now it's time to go down to the next level.
// so we switch the counts now and make childNodes count again 0
if(currentNodes == 0){
currentNodes = childNodes;
childNodes = 0;
}
}
}
int heightsum(node *root)
{
if(!root)
return 0;
static int sum, level;
level++;
heightsum(root->left);
heightsum(root->right);
level--;
if(level % 2)
return sum -= root->data;
else
return sum += root->data;
}
This wont work. The level will come out to be 0 for each level. This is because you're initializing a new int each recursive call. Then incrementing it to one, then decrementing it to 0.
Working code:
public static int getDiffOfEvenOddLevel(Node root, boolean isLevelEven)
{
if (root == null)
return 0;
if (isLevelEven)
return root.data + getDiffOfEvenOddLevel(root.left, false) + getDiffOfEvenOddLevel(root.right, false);
else
return -root.data + getDiffOfEvenOddLevel(root.left, true) + getDiffOfEvenOddLevel(root.right, true);
}
public class BinaryTreeExample {
public static void main(String[] args)
{
new BinaryTreeExample().run();
}
static class Node
{
Node left;
Node right;
int value;
public Node(int value)
{
this.value = value;
}
}
public void run()
{
Node rootnode = new Node(25);
System.out.println("Building tree with rootvalue " + rootnode.value);
System.out.println("=================================");
insert(rootnode, 11);
insert(rootnode, 35);
insert(rootnode, 8);
insert(rootnode, 12);
insert(rootnode, 30);
insert(rootnode, 40);
System.out.println("Traversing tree in order");
System.out.println("========================");
printInOrder(rootnode);
System.out.println(sum(rootnode));
}
private int sum(Node rootnode) {
if(rootnode == null)
return 0;
else
return (rootnode.value + -sum(rootnode.left) + -sum(rootnode.right));
}
public void insert(Node node, int value)
{
if (value < node.value)
{
if (node.left != null)
{
insert(node.left, value);
}
else
{
System.out.println(" Inserted " + value + " to left of node "+ node.value);
node.left = new Node(value);
}
}
else if (value > node.value)
{
if (node.right != null)
{
insert(node.right, value);
} else {
System.out.println(" Inserted " + value + " to right of node "
+ node.value);
node.right = new Node(value);
}
}
}
public void printInOrder(Node node)
{
if (node != null) {
printInOrder(node.left);
System.out.println(" Traversed " + node.value);
printInOrder(node.right);
}
}
}
Assuming root is at height '0' which is at even height.
int evenSum=0;
int oddSum = 0;
public int getOddEvenDiff(BTreeNode root) {
if (root == null)
return (evenSum-oddSum);
if (getDepth(root) % 2 == 0) {
evenSum += root.elem;
} else {
oddSum += root.elem;
}
getOddEvenDiff(root.left);
getOddEvenDiff(root.right);
return (evenSum-oddSum);
}
public int getDepth(BTreeNode node) {
int depth = 0;
while (node != null) {
depth++;
node = node.parent;
}
return depth+1;
}
private void DifferenceSumatOoddandSumatEven(ref int sum, BinaryTreeNode<T> node, int level)
{
if (node == null) return;
if ((level & 1)==0)//if level is even
sum+=node.item;
else
sum += -1 *node.item;
DifferenceSumatOoddandSumatEven(ref sum, node.Left, level + 1);
DifferenceSumatOoddandSumatEven(ref sum, node.Right, level + 1);
}
int sumOddMinusEven(struct node* root) {
if (root == NULL) return 0;
int level = 1;
queue< pair<int, struct node*> > q;
q.push( make_pair(level, root) );
int oddSum = root->data;
int evenSum = 0;
while(!q.empty()) {
pair<int, struct node*> my_element = q.front();
struct node* current = my_element.second;
int childLevel = my_element.first + 1;
q.pop();
bool isEven = (childLevel % 2 == 0) ;
if (current->left != NULL) {
q.push( make_pair( childLevel, current->left ) );
if (isEven) {
evenSum += current->left->data;
} else {
oddSum += current->left->data;
}
}
if (current->right != NULL) {
q.push( make_pair( childLevel, current->right ) );
if (isEven) {
evenSum += current->right->data;
} else {
oddSum += current->right->data;
}
}
}
cout << "Odd Sum "<< oddSum<<endl;
cout << "Even Sum "<<evenSum<<endl;
return ( oddSum - evenSum );
}
Use BFS, use some counters and a flag to track odd or even levels. If count == 0, a new level starts and the flag needs to be reset. The program will stop when the linked list is empty.
struct node{
int value;
struct node *l;
struct node *r;
struct node *next;
} node;
int getValue(node * root){
int count = 1; //Root
int values = 0;
int count1= 0;
int flag = 0;
node *head = (node *)calloc(sizeof(node), 1);
head->next = root;
p1 = head->next; //p tracks the tail of the list
while(head->next != NULL){
if(flag == 1)
values +=head->next->value;
count --; // Take out the next node
if(count == 0){
count = count1;
if(flag == 0) flag = 1;
else flag = 0;
}
if(head->next->l != NULL){
p->next = (node*)calloc(sizeof(node), 1);
p = p->next;
count1 ++;
}
if(head->next->r != NULL){
p->next = (node*)calloc(sizeof(node), 1);
p = p->next;
count1 ++;
}
node *p1 = head->next;
head->next = head->next->next;
free(p1);
}
}
Here is a BFS solution, using two Queues to store nodes and the level of nodes. then it can be easily solved.
public class FindSumOfHeight {
public static class Node{
public int value;
public Node left;
public Node right;
public Node(int value){
this.value = value;
this.left = null;
this.right = null;
}
}
public static boolean isLeaf(Node node) {
return (node.left == null && node.right == null);
}
public static int sum(Node root) {
if(root == null) {
return 0;
}
if(isLeaf(root))
return root.value;
int sumOfOdd = 0;
int sumOfEven = 0;
Queue<Node> nodeQ = new ArrayDeque<Node>();
nodeQ.offer(root);
Queue<Integer> levelQ = new ArrayDeque<Integer>();
levelQ.offer(0);
while(!nodeQ.isEmpty()) {
Node node = nodeQ.poll();
int currentHeight = levelQ.poll();
if(currentHeight%2 == 0)
sumOfEven += node.value;
else
sumOfOdd += node.value;
if(node.left != null){
nodeQ.offer(node.left);
levelQ.offer(currentHeight+1);
}
if(node.right != null){
nodeQ.offer(node.right);
levelQ.offer(currentHeight+1);
}
}
return sumOfOdd - sumOfEven;
}
public static void main(String[] args){
Node root = new Node(1);
Node one = new Node(2);
Node two = new Node(3);
Node three = new Node(4);
Node four = new Node(5);
Node five = new Node(6);
Node six = new Node(7);
Node seven = new Node(8);
Node eight = new Node(9);
root.left = one;
root.right = two;
one.left = three;
one.right = four;
two.left = five;
two.right = six;
three.left = seven;
six.right = eight;
System.out.println(sum(root));
}
}
Using Bfs
void oddeven(Bnode root)
{
Bnode cur=root;
Queue<Bnode> q= new LinkedList();
q.add(cur);
int curlevel=1,nxtlevel=0,odd=0,even=0,flag=0;
while(!q.isEmpty())
{
cur=q.poll();
curlevel--;
if(flag==0)
even+=cur.data;
else
odd+=cur.data;
if(cur.left!=null)
{
q.add(cur.left);
nxtlevel++;
}
if(cur.right!=null)
{
q.add(cur.right);
nxtlevel++;
}
if(curlevel==0)
{
curlevel=nxtlevel;
nxtlevel=0;
flag=flag==0?1:0;
}
}
System.out.println("odd-even "+(odd-even));
}
import java.util.LinkedList;
import java.util.Queue;
/*Given a binary tree. Write a function that takes only root node as arguement and
returns (sum of values at odd height)-(sum of values at even height).*/
public class Odd_Even_Sum {
public static void main(String[] args) {
TreeNode root = new TreeNode(1);
root.leftchild = new TreeNode(2);
root.rightchild = new TreeNode(3);
root.leftchild.leftchild = new TreeNode(4);
root.leftchild.rightchild = new TreeNode(5);
root.rightchild.leftchild = new TreeNode(6);
root.rightchild.rightchild = new TreeNode(7);
root.rightchild.leftchild.leftchild = new TreeNode(8);
root.rightchild.leftchild.rightchild = new TreeNode(10);
root.rightchild.rightchild.rightchild = new TreeNode(9);
System.out.println(utilFuction(root));
}
public static int utilFuction(TreeNode root)
{
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.add(root);
TreeNode current ;
boolean flag = true;
int sum =0;
Queue<TreeNode> temp_queue = new LinkedList<TreeNode>();
while(!queue.isEmpty())
{
current = queue.poll();
if(flag)
sum =sum + current.data;
else
sum = sum - current.data;
if(current.leftchild!=null)
temp_queue.add(current.leftchild);
if(current.rightchild!=null)
temp_queue.add(current.rightchild);
if(queue.isEmpty())
{
queue = temp_queue;
temp_queue = new LinkedList<TreeNode>();
flag = !flag;
}
}
return sum;
}
}
Solution with a some simplification:
Call the function with the root of the tree
The root is at height 0.
- nik March 09, 2013double sum(Node root){ if(root == null){ return 0; } return -(root.value + sum(root.left) + sum(root.right)); }