Amazon Interview Question
Software Engineer / DevelopersCountry: 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;
}
}
public static int getSumOfLeaves(Node root) {
if ( root == null ) {
return 0;
}
if ( root.getLeft() == null
&& root.getRight() == null ) {
return root.getValue();
}
return getSumOfLeaves(root.getLeft()) + getSumOfLeaves(root.getRight());
}
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;
}
- Vir Pratap Uttam May 04, 2015