## Flipkart Interview Question for Software Engineer / Developers

• 0

Country: United States
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
4
of 6 vote

1. Allocate a global bit vector of size h where h is height of the tree.
2. Traverse the tree in post-order fashion.
3. At each node do the following:
a) if leaf node: set the kth bit of the vector as 1 where k is the height of the current node.
b) else check if the k+l bit is set and add the value of the current node to sum.

Time complexity: O(n)
Space: O(logn)

The idea is to figure out the height of all leaf nodes and then choose all the nodes that are level 'l' from every leaf node.

Comment hidden because of low score. Click to expand.
0

yeah this worked. one corner case, if l == 0 should end up in adding all leaf nodes.

Comment hidden because of low score. Click to expand.
0

very nice solution, post order is used to encounter leaves first

Comment hidden because of low score. Click to expand.
0

seems wrong to me.
Consider complete binary tree of height 10. now delete right half of leaf nodes. So now of left leaves have depth 10, and on right, leaves have depth 9. assign l =2, and watch, how your algo does.

Comment hidden because of low score. Click to expand.
0

this algo fails as how do you ensure that any node is away for leaf only by l. for example
3
4 1
2 7
8
for this tree and l as 1 your algo gives ans as 12 but it should be 11.
as it is counting 1 also bcz (k+l) is set for it.

Comment hidden because of low score. Click to expand.
0

tree structure correction
3
/ \
4 1
/ \
2 7
/
8

Comment hidden because of low score. Click to expand.
1
of 1 vote

yes this solution will not work..!!
in this example

``````3
/ \
4  1
/ \
2 7
/
8``````

and if l = 1 then we need to sum 2, 4 and 3 and answer should be 9, not 11 or 12.

Comment hidden because of low score. Click to expand.
1
of 1 vote

algorithm is correct with one addition, that we unset the bit(k+l)th after summing the (k)th element.

Comment hidden because of low score. Click to expand.
0

If you unset the (k+l)th bit, then u might end up adding a node twice if it has two leaf nodes at level l.

Comment hidden because of low score. Click to expand.
1
of 1 vote

Thumbs up for @Anonymous on July 17, 2012
Great one! I am just following your steps.

``````#include <stdio.h>
#include <stdlib.h>

typedef struct node {
int data;
struct node *left;
struct node *right;
}node ;

node* newNode (int data) {
node *temp = (node *) malloc (sizeof(node));
temp->data = data;
temp->left = NULL;
temp->right = NULL;
return temp;
}
/* Calculates height as well as total
number of nodes present in the tree */
int height (node *root, int *count) {
int left, right ;
if (!root)
return 0 ;
*count = *count + 1  ;

/* Leaf node */
if ( root->left == NULL && root->right == NULL )
return 1 ;
left = height (root->left,count) ;
right = height (root->right,count) ;
return 1+((left>right) ? left : right ) ;
}

/* Post order traversal and puts the element in the array,
also puts the height of the tree nodes in another array */
int givePostOrderUtil (int* arr, node* root, int len, int* tLevel, int level) {
if (root) {
len = givePostOrderUtil (arr, root->left, len, tLevel, level+1) ;
len = givePostOrderUtil (arr, root->right, len, tLevel, level+1) ;
arr[len] = root->data ;
tLevel[len] = level ;
/* Special marks which indicates this as a leaf node */
if ( root->left == NULL && root->right == NULL )
tLevel[len] = -level ;
len ++ ;
}
return len ;
}

/* Post order traversal driver function */
int* givePostOrder (node *root, int size, int** tLevel) {
int *arr = (int *) malloc (sizeof(int)*size) ;
int *tlevel = (int *) malloc (sizeof(int)*size) ;
givePostOrderUtil (arr, root, 0, tlevel, 0) ;
*tLevel = tlevel ;
return arr ;
}

int giveSumParticularOrder (int* arr, int *tLevel, int tHeight, int count, int level) {
int *bitArr, i, sum = 0 ;

/* Array denotes for leaf nodes */
bitArr = (int *) malloc (sizeof(int) * tHeight) ;
for ( i = 0 ; i < tHeight ; i ++ )
bitArr[i] = 0 ;

for ( i = 0 ; i < count ; i ++ ) {
/* marks as leaf node */
if ( tLevel[i] < 0 ) {
bitArr[-tLevel[i]] = 1 ;
}
else {
/* check the marker boundary and if the bit set then it will be
a child at that extra depth. Collect the value and adds */
if ( (tLevel[i]+level) < tHeight && bitArr[tLevel[i]+level] ) {
sum += arr[i] ;
}
}
}
return sum ;
}

int main () {
int cNode = 0, i, *arr, *tLevel, tHeight ;
node *root = newNode(1) ;
root->left = newNode(2) ;
root->right = newNode(3) ;
root->left->left = newNode(4) ;
root->left->right = newNode(5) ;
root->right->left = newNode(6) ;
root->right->right = newNode(7) ;
root->left->right->left = newNode(8) ;
root->left->right->right = newNode(9) ;
root->right->right->right = newNode(10) ;

tHeight = height(root,&cNode) ;

arr = givePostOrder (root, cNode, &tLevel) ;
for ( i = 0 ; i < cNode ; i ++ )
printf ( "\n%d (%d)", arr[i], tLevel[i]) ;
printf ( "\nMaximum sum is : %d", giveSumParticularOrder (arr, tLevel, tHeight, cNode, 2) ) ;
return 0 ;
}``````

Comment hidden because of low score. Click to expand.
1
of 1 vote

I suggest a modification to Anonymous ans, instead maintaining a bit set/or reset we maintain a actual vector of keys while going down through preorder traversal.
If we encounter any leaf, we simply add the value at vector.size()-K to a hash. In the end we sum the values in the hash.
More precisely,

``````Let V be Vector
Let map<int,bool> be HashMap
if ( root != NULL )
1. if root != Leaf
push root->data to V
preOrder(root->left)
preOrder(root->right)
Pop from V
2. else if root == Leaf
push root->data to V
map [ V [ V.size() - K - 1 ] ] = true;
Pop from V``````

Now, sum all the values in the map to get desired answer :)

Comment hidden because of low score. Click to expand.
1
of 1 vote

1) perform post-order traversal of tree. maintain stack explicitly.
also maintain whether particular number is already added or not in stack
2) whenever you reach at leaf node get stack[top - k]->value and add it to ans.
code:

``````int sumup(Node * tree, int K, stack * st)
{
if (tree == NULL) return
if (tree->left == NULL && tree->right == NULL)
{
return st->array[stack->top-K]->value ;
}
int ans = 0;
st.push(tree);
ans += sumup(tree->left, K, st);
ans += sumup(tree->right,K, st);
st.pop(tree);
return ans;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

I don't understand the question.

Comment hidden because of low score. Click to expand.
0

@eugene : Suppose your binary tree leaves are at 5, 8, 7, 9, 2, 1 levels from the root level say level 0. Now you have given a number say 4, now you have to sum up all the values that are present in 4 levels up from those leaves.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Comment hidden because of low score. Click to expand.
0

A
/ \
B C
/ \ \
E F D
/ \
G H

here in dis tree there are only three leaves G , H , D the reqd. ans would be ( E + F + C ) if the level is 1 and if the level given is 2 it would be ( B + A ) ...hope its all clear now ..

Comment hidden because of low score. Click to expand.
-1
of 1 vote

no its not like this
for level 1 sum= B+C
for level 2 sum =E+F+D

since when level got started counted from leaves
:)

Comment hidden because of low score. Click to expand.
0

@shreyans Deadman says correctly.. questions asked " which are at a particular level from all of its existing leaves.".. so we have to calculate from leaves ,not from root

Comment hidden because of low score. Click to expand.
0
of 0 vote

// Calculates the sum of a particular level from leaves
int a[]={0,0,0,0,0,0},s;
int levelSum(struct btreenode *root,int h,int g){
if(root==NULL) return 0;
levelSum(root->leftchild,h+1,g);
levelSum(root->rightchild,h+1,g);
if(root->leftchild==NULL && root->rightchild==NULL)
a[h]=1;
else{
if(a[h+g]==1)
s+=root->data;
}

return s;
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

Save the binary tree in an array (like storing a heap-store NULL in the places which are vacant in the tree)
Calculate the sum by adding the entries from 2^(n-1) up-til either length of the array(in case it is the last level) or up-til 2^(n-1) entries.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Save the binary tree in an array (like storing a heap-store NULL in the places which are vacant in the tree)
Calculate the sum by adding the entries from 2^(n-1) up-til either length of the array(in case it is the last level) or up-til 2^(n-1) entries.

Comment hidden because of low score. Click to expand.
-1
of 1 vote

You can solve this by using BFS.

Comment hidden because of low score. Click to expand.
-2
of 2 vote

There's a much simple solution, i.e. calculate the height of the left-subtree and the right sub-tree, and pick the maximum. You can leverage the power of recursion to do that -- the code is self-explanatory, but basically you call bstHeight recursively on each on each node's left and right child, starting with the root. If the current node is null, return 0, otherwise add 1. In the end, after all recursive calls have been issued, you end up with as many 1s as there are levels in the particular sub-tree. They are added up to the total, and all you have to do is pick the max value.

``````struct Node
{
int i;
Node* left;
Node* right;

Node(int i, Node* left=NULL, Node* right=NULL)
: i(i), left(left), right(right)
{}
};

int bstHeight(const Node* const root)
{
if (!root)
return 0;

return std::max(1 + bstHeight(root->left), 1 + bstHeight(root->right));
}

int main()
{
Node* root = new Node(10);
// left sub-tree
root->left = new Node(5);
root->left->left = new Node(2);
root->left->left->right = new Node(3);
// right sub-tree
root->right = new Node(12);
root->right->right = new Node(12);
root->right->right->right = new Node(12);
root->right->right->right->right = new Node(12);
root->right->right->right->right->right = new Node(12);
root->right->right->right->right->right->right = new Node(12);
root->right->right->right->right->right->right->right = new Node(12);
root->right->right->right->right->right->right->right->right = new Node(12);
root->right->right->right->right->right->right->right->right->right = new Node(12);
root->right->right->right->right->right->right->right->right->right->right = new Node(12);

cout << "bstHeight(" << root->i << "): " << bstHeight(root) << endl << endl;

deleteTree(root);
}

void deleteTree(Node* root)
{
if (!root)
return;

Node* left = root->left;
Node* right = root->right;

cout << "delete " << root->i << "\n";
delete root;

deleteTree(left);
deleteTree(right);
}``````

Comment hidden because of low score. Click to expand.
0

Your algo will just find height of tree not what question is asking for. pls read question.

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.