## Amazon Interview Question

Software Engineer / Developers- 0of 0 votes
Given a binary tree,Sum all the values of leaves .

**Country:**India

**Interview Type:**Phone Interview

```
int sumleaves (btree* t) {
if (!t->left && !t->right) {
return (t->val);
}
else {
return ( ((t->left)?sumleaves(t->left):0) + ((t->right)?sumleaves(t->right):0 );
}
}
```

If you give this code in an interview, you will have points cut off.

1) No null checks.

2) A ridiculous attempt to write concise code. This is a simple problem so if I showed this to a co-worker, he might be able to understand easily, but that if you did this everytime?

Meh. Do you subject every method you write with torturous null checks? If you look closely, most of your code will be written with certain assumptions in mind. If those assumptions are broke, pretty much your entire system is broken.

@dr.house: Huh? Of course you do. Robust error handling is a major portion of writing production code.

Besides, the interviewer will scrutinize you to these standards. Did you not understand the first sentence of what Anonymous is saying? Even if you don't do it yourself, the interviewer will likely do, and ding you for it.

We can use any of the traversal mechanism (in/pre/post order)and at node we can check if left && right nodes are null then Update the running counter

Instead of global variable, you can use a integer pointer as part of your function prototype. Use this integer to maintain your sum.

void sum (node *root, int *summation);

```
// Normal pre-order traversal and adding to the sum as we traverse
void sum_leaf_binary_tree(struct node* root, int& sum = 0) {
if(root) {
if(root->left == NULL && root->right == NULL) {
sum += root->data; // leaf node
return;
}
if(root->left)
sum_leaf_binary_tree(root->left, sum);
if(root->right)
sum_leaf_binary_tree(root->right, sum);
}
}
```

Idea is to do a depth first search, maintaining a running.

C++ like code. Note that sum is passed by reference. If you want to do C, then you can pass a pointer.

```
long LeafSum(Node *root) {
long sum = 0;
LeafSumInternal(root, sum);
return sum;
}
void LeafSumInternal(Node *n, long & sum) {
if (n == null) return;
// Found a leaf node! Add to sum.
if (!n->left && !n->right) {
sum += n->data;
return;
}
if (n->left) { LeafSumInternal(n->left, sum) };
if (n->right) {LeafSumInternal(n->right, sum)};
}
```

//print sum of leaves of binary tree

/*

1.Traverse the tree

2.Find the leaf node and return its value

*/

#include <stdio.h>

#include <stdlib.h>

struct node

{

/* data */

int data;

struct node* left;

struct node* right;

};

struct node* newnode(int key){

struct node* leaf = (struct node*)malloc(sizeof(struct node));

leaf->data = key;

leaf->left =NULL;

leaf->right =NULL;

}

int sumofleaves(struct node* n){

if(n!=NULL){

if(n->left==NULL && n->right==NULL)

return n->data;

else

return sumofleaves(n->left)+sumofleaves(n->right);

}

return 0;

}

int main(){

/* 5

/ \

3 9

/\ / \

2 4 7 10

*/

struct node *root=newnode(5);

root->left = newnode(3);

root->right = newnode(9);

root->left->left = newnode(2);

root->left->right = newnode(4);

root->right->left = newnode(7);

root->right->right = newnode(10);

printf("%d",sumofleaves(root));

// inorder(root);

// printf("\n");

// preorder(root);

// printf("\n");

// postorder(root);

printf("\n");

return 0;

}

public class BinaryTree {

class Node

{

Node(int i)

{

data=i;

}

int data;

Node nodeLeft;

Node nodeRight;

}

static BinaryTree tree = new BinaryTree();

static Node createTree()

{

Node l1_1 = tree.new Node(30);

Node l2_1 = tree.new Node(25);

Node l2_2 = tree.new Node(35);

Node l3_1 = tree.new Node(20);

Node l3_2 = tree.new Node(28);

Node l3_3 = tree.new Node(32);

Node l3_4 = tree.new Node(50);

Node l4_1 = tree.new Node(10);

Node l4_2 = tree.new Node(22);

Node l4_3 = tree.new Node(27);

Node l4_4 = tree.new Node(29);

Node l4_5 = tree.new Node(31);

Node l4_6 = tree.new Node(34);

Node l4_7 = tree.new Node(38);

Node l4_8 = tree.new Node(55);

l1_1.nodeLeft=l2_1;

l1_1.nodeRight=l2_2;

l2_1.nodeLeft=l3_1;

l2_1.nodeRight=l3_2;

l2_2.nodeLeft=l3_3;

l2_2.nodeRight=l3_4;

l3_1.nodeLeft=l4_1;

l3_1.nodeRight=l4_2;

l3_2.nodeLeft=l4_3;

l3_2.nodeRight=l4_4;

l3_3.nodeLeft=l4_5;

l3_3.nodeRight=l4_6;

l3_4.nodeLeft=l4_7;

l3_4.nodeRight=l4_8;

return l1_1;

}

public static void main(String p[])

{

Node root= null;

root = tree.createTree();

System.out.println(sumOfLeaves(root));

}

static int sumOfLeaves(Node node)

{

int total = 0;

if(node.nodeLeft != null)

total += sumOfLeaves(node.nodeLeft);

else

{

if(node.nodeRight == null)

return node.data;

else

return 0;

}

//total += node.data;

if(node.nodeRight != null)

total += sumOfLeaves(node.nodeRight);

else

{

if(node.nodeLeft == null)

return sumOfLeaves(node.nodeRight);

else

return 0;

}

return total;

}

}

sum(BinaryTree *root )

{

int sum = 0;

if(root != null)

{

if(root->leftchild != null && root->rightchild != null)

{

sum(root->leftchild);

}

else

{

sum = sum + *root;

}

if(root->rightchild != null && root->leftchild != null)

{

sum(root->rightchild);

}

else

{

sum = sum + *root;

}

}

return sum;

}

- CodeSpace October 07, 2012