Flipkart Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: In-Person
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.
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.
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.
algorithm is correct with one addition, that we unset the bit(k+l)th after summing the (k)th element.
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 ;
}
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
Start with root of the tree.
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 :)
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)
{
if (stack->top < k || st->array[stack->top-K]->already_added) return 0;
st->array[stack->top-K]->already_added = True
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;
}
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 ..
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
:)
// 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;
}
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);
}
1. Allocate a global bit vector of size h where h is height of the tree.
- Anonymous July 17, 20122. 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.