Amazon Interview Question SDE1s
Country: India
Interview Type: In-Person
PrintLevelsSum(struct node *root,int *arr,int *level,int k,int i){
if(!root)
return;
if(level==pow(k,i)){
arr[i]=root->data;
i=i+1;
}
*level=*level+1;
PrintLevelsSum(root->left,arr,level,k,i);
PrintLevelsSum(root->right,arr,level,k,i);
}
main(){
struct node *root;
int arr[No of Levels];
int level=1,k,i=0;
scanf("%d",k);
PrintLevelsSum(root,arr,level,k,i);
}
arr : is an integer array contains the values of level sum..arr[0] contains the sum of all nodes in level k^0,
arr[1] contains the sum of all nodes in level k^1, so on
function call is PrintLevelsSum(root,arr,level,k,i);
My solution is little big, i implemented my code by c++ , i created BST , that is also a binary tree , my file BST.hpp contains all functions required to implement this program, and from main.cpp I called all the header function , and input file contains data for creating BST .
1st line of input indicates no of nodes for bst and rest are values for BST.
1.BST.hpp
/*
BST.hpp
Developed By: Suman Roy
Email : email.suman.roy@gmail.com
*/
#ifndef BST_H
#define BST_H
#include<iostream>
#include<stdlib.h>
#include<math.h>
using namespace std;
typedef struct node{
int i_value;
struct node * l_child;
struct node * r_child;
}node;
typedef struct level{
int i_start;
int i_end;
int i_sum;
}level;
class Queue_t{
private:
node **i_queue;
int rear;
int front;
public:
node* Get_Value();
int Insert_Value( node* );
Queue_t ( int );
Queue_t( void );
};
Queue_t::Queue_t ( void ){};
Queue_t::Queue_t( int i_size){
i_queue=new (std::nothrow) node* [ i_size ];
front=rear=-1;
}
int Queue_t::Insert_Value( node *temp){
std::cout<<"inserted ="<<temp->i_value<<std::endl;
i_queue[++front]=temp;
// std::cout<< i_queue[front]->i_value;
return front;
}
node* Queue_t::Get_Value(){
if ( front == rear ){
front=rear=-1;
return NULL;
}
else return ( i_queue[ ++rear ] );
}
class Bst : public Queue_t{
private:
node *root;
level *level_store;
public:
Bst();
bool Find ( int& );
node * Getnode( int& );
bool Insert ( int& );
void Print(node * );
void Print_Level(int& , int& );
};
Bst::Bst(){
root=NULL;
Queue_t();
}
void Bst::Print_Level ( int &level_limit, int &bst_size){
level_store=new ( std::nothrow ) level[ bst_size ] ;
Queue_t l_queue( bst_size );
node *temp=root;
int i_temp;
int level=l_queue.Insert_Value( temp );
level_store[ level ].i_start=0;
level_store[ level ].i_end=0;
int check=true;
while ( check ){
level_store[level].i_sum=0;
int flag=0;
check=false;
std::cout<<"queue start & end"<<level_store[level].i_start<<":"<<level_store[level].i_end<<std::endl;
int ii=level;
for ( int i=level_store[ii].i_start ; i<=level_store[ii].i_end ; i++ ){
temp=l_queue.Get_Value();
level_store[ii].i_sum+=temp->i_value;
if ( temp->l_child != NULL ) {
check=true;
i_temp=l_queue.Insert_Value( temp->l_child );
if ( flag == 0) {
level_store [ ++ level ].i_start=i_temp;
flag =1;
}
}
if ( temp->r_child != NULL ){
check=true;
i_temp=l_queue.Insert_Value ( temp->r_child );
if (flag==0 ){
level_store[ ++ level ].i_start=i_temp;
flag=1;
}
}
// std::cout<<"sum at level "<<ii<<"="<<level_store[ii].i_sum<<std::endl;
}
std::cout<<"sum at level "<<ii<<"="<<level_store[ii].i_sum<<std::endl;
std::cout<<"..................."<<std::endl;
level_store [ level ].i_end=i_temp;
}
//print sum
std::cout<<"PRINTING FINAL RESULT\n";
int i_pow=0;
int i_print_level=0;
do {
std::cout<<"Sum for level = "<<i_print_level<<" : "<<level_store[ i_print_level ].i_sum<<std::endl;
i_print_level=pow( level_limit , i_pow ++);
}while ( i_print_level <=level );
// std::cout<<"Sum for level "<<level_limit<<" ="<<level_store[level_limit].i_sum<<std::endl;
}
void Bst::Print( node * temp){
std::cout<<temp->i_value<<temp->l_child<<temp->r_child<<std::endl;
}
bool Bst::Find( int &i_val ){
node *temp=root;
while( temp!=NULL ){
if( temp->i_value == i_val )
return true;
else {
if ( temp->i_value > i_val ) temp=temp->l_child;
else temp=temp->r_child;
}
}
return false;
}
node * Bst::Getnode(int &i_val){
node *temp=new node;
if ( temp == NULL ) {
std::cout<<"Out of memory \n ";
return NULL;
}
temp->i_value=i_val;
temp->l_child==NULL;
temp->r_child=NULL;
Print(temp);
return temp;
}
bool Bst::Insert( int &i_val ){
if( root == NULL ){
root=Getnode(i_val);
return true;
}
node * temp=root;
node * temp2;
while ( temp != NULL ){
if ( temp->i_value == i_val ){
std::cout<<"Data alradey exist \n";
return false;
}
else {
temp2=temp;
if( temp->i_value > i_val )
temp=temp->l_child;
else temp=temp->r_child;
}
}
if( temp2->i_value > i_val )
temp2->l_child=Getnode ( i_val );
else
temp2->r_child=Getnode( i_val );
return true;
}
#endif
2. main.cpp
/*
main.cpp
You are given a binary tree and a number k.
Print the sum of levels k^0, k^1, k^2, k^3..... untill all levels are exhausted.
Each K^ith level sum should be printed separately.
I saved sum for all level and printing the sum by given level no
developed by : Suman
Date:13 7 2013
time : 4.23 am
*/
#include<iostream>
#include<stdlib.h>
#include<fstream>
#include"BST.hpp"
using namespace std;
int main(int argc , char **argv){
if( argc <1 ) {
std::cout<<"Provide Arguments\n";
exit(EXIT_FAILURE);
}
fstream file;
file.open( argv [1] , ios::in);
if( !file.is_open() ){
std:cout<<"Can't open file\n";
exit(EXIT_FAILURE);
}
int i_num , i_val;
file>>i_num;
Bst bst;
for ( int i=0 ;i<i_num ; i++ ){
file>>i_val;
bst.Insert( i_val);
}
int i_level;
std::cout<<"print the value of k\n";
std::cin>>i_level;
//int i_level=2;
bst.Print_Level( i_level , i_num); //i_level=k
}
3.input
7
5
3
4
1
10
12
30
4. output
suman@suman-laptop:/media/D/coding/algo/Graph/BST/level_sum$ ./a.out input
500
300
400
100
1000
1200
3000
print the value of k
3
inserted =5
queue start & end0:0
inserted =3
inserted =10
sum at level 0=5
...................
queue start & end1:2
inserted =1
inserted =4
inserted =12
sum at level 1=13
...................
queue start & end3:5
inserted =30
sum at level 2=17
...................
queue start & end6:6
sum at level 3=30
...................
PRINTING FINAL RESULT
Sum for level = 0 : 5
Sum for level = 1 : 13
Sum for level = 3 : 30
suman@suman-laptop:/media/D/coding/algo/Gr
Keep track of K^i-1 tree level in Queue and calculate the sum as their sum of the child nodes of the nodes present in queue and update the queue with new level.
void k_power_i_sum(struct node* tree,int k)
{
int i=0,j=1;
std::queue<struct node*> Q;
Q.push(tree);
std::cout<<"\nSum at k^"<<i<<" is "<<tree->val;
i++;
j++;
int num_nodes=1;
while(!Q.empty())
{
if(pow(k,i)==j)
{
int n=0;
int sum=0;
while(num_nodes>0)
{
struct node* v=Q.front();
num_nodes--;
Q.pop();
if(v->left!=NULL)
{Q.push(v->left);n++;sum+=v->left->val;}
if(v->right!=NULL)
{Q.push(v->right);n++;sum+=v->right->val;}
}
num_nodes=n;
std::cout<<"\nSum at k^"<<i<<" is "<<sum;
i++;
}
else if(pow(k,i)==j+1)
{
j++;
}
else
{
int n=0;
while(num_nodes>0)
{
struct node* v=Q.front();
num_nodes--;
Q.pop();
if(v->left!=NULL)
{Q.push(v->left);n++;}
if(v->right!=NULL)
{Q.push(v->right);n++;}
}
j++;
num_nodes=n;
}
}
std::cout<<"\nDone ... ";
}
You would implement a breadth first search using a queue to sum the values on each level, print them, then move to the next level.
void printLevelOrder(BinaryTree *root) {
if (!root) return;
queue<BinaryTree*> nodesQueue;
int nodesInCurrentLevel = 1;
int nodesInNextLevel = 0;
int levelSum = 0;
nodesQueue.push(root);
while (!nodesQueue.empty()) {
BinaryTree *currNode = nodesQueue.front();
nodesQueue.pop();
nodesInCurrentLevel--;
if (currNode) {
levelSum += currNode.value;
nodesQueue.push(currNode->left);
nodesQueue.push(currNode->right);
nodesInNextLevel += 2;
}
if (nodesInCurrentLevel == 0) {
cout << levelSum;
cout << endl;
nodesInCurrentLevel = nodesInNextLevel;
nodesInNextLevel = 0;
levelSum = 0;
}
}
}
Here is the code you can test it. Just do a normal inorder traversal and for every level just dequeue all the elements there and then add all the elements of that level to get the sum:
- vgeek July 12, 2013#include <stdio.h> #include <conio.h> #include <malloc.h> typedef struct tree tree_t; struct tree { int data; tree_t *left; tree_t *right; }; tree_t *newNode(int data) { tree_t *n=(tree_t *)malloc(sizeof(tree_t)); n->data=data; n->left=n->right=NULL; return n; } typedef struct q q_t; struct q { int front; int rear; tree_t **array; }; q_t *createQueue(int size) { q_t *n=(q_t *)malloc(sizeof(q_t)); n->front=n->rear=0; n->array=(tree_t **)malloc(size*sizeof(tree_t *)); return n; } void enqueue(q_t *s,tree_t *t) { s->array[(s->rear)++]=t; } tree_t *dequeue(q_t *s) { s->front++; return s->array[s->front-1]; } int isQueueEmpty(q_t *s) { return (s->front==s->rear); } int power(int a,int b) { int temp; if(b==0) return 1; temp=power(a,b/2); if(b%2==0) return temp*temp; else { if(b>0) return a*temp*temp; else return (temp*temp)/a; } } int printAllSum(tree_t *root,int k) { q_t *s=createQueue(30); tree_t *temp=root; int i=0,j=1,sum=0; enqueue(s,temp); while(temp) { if(power(k,i)==j) { while(!isQueueEmpty(s)) { temp=dequeue(s); sum=sum+temp->data; } printf(" %d level sum is %d",j,sum); printf("\n"); } if(temp->left) enqueue(s,temp->left); if(temp->right) enqueue(s,temp->right); j=j+1; i=i+1; sum=0; } return 0; } int main() { tree_t *t=newNode(1); t->left=newNode(2); t->right=newNode(3); printAllSum(t,2); }