Given a binary tree, write an efficient function that returns the maximum level sum. If tree is empty return 0. Assume that all values in binary tree are positive integers. What are the space and time complexities of your solution?
Input:
3
Code:
#include<stdio.h>
#include<conio.h>
#include<malloc.h>
#define QUEUESIZE 20
struct treenode
{
int data;
struct treenode *left;
struct treenode *right;
} *root=NULL;
int *queue[QUEUESIZE];
int rear=-1,front=-1;
//queue finctions
void enque(struct treenode *root)
{
if(rear<QUEUESIZE)
{
queue[++rear]=root;
}
else printf("queue overflow");
}
int deque()
{
int i;
if(front!=rear)
i=queue[++front];
else printf("underfolw");
return i;
}
int isqempty()
{
if(front==rear)
return 1;
return 0;
}
//for building tree statically
struct treenode * buildtree()
{
struct treenode *temp1,*temp2,*temp3,*temp4,*temp5,*temp6;
root=(struct treenode *)malloc(sizeof(struct treenode));
temp1=(struct treenode *)malloc(sizeof(struct treenode));
temp2=(struct treenode *)malloc(sizeof(struct treenode));
temp3=(struct treenode *)malloc(sizeof(struct treenode));
temp4=(struct treenode *)malloc(sizeof(struct treenode));
temp5=(struct treenode *)malloc(sizeof(struct treenode));
temp6=(struct treenode *)malloc(sizeof(struct treenode));
root->data=4;
root->left=temp1;
temp1->data=5;
root->right=temp2;
temp2->data=6;
temp1->left=temp3;
temp3->data=7;
temp3->left=temp3->right=NULL;
temp1->right=temp4;
temp4->data=8;
temp4->left=NULL;
temp4->right=NULL;
temp2->left=temp5;
temp5->data=6;
temp2->right=temp6;
temp6->data=10;
temp5->left=temp5->right=temp6->left=temp6->right=NULL;
printf("\n tree buildedsuccessfull");
return root;
}
//levelsum
void printlevel(struct treenode *root)
{
int sum=0,maxsum=root->data;
struct treenode *temp;
enque(root);
enque(NULL);
temp=deque();
while(!isqempty())
{
sum=0;
while(temp!=NULL)
{
sum=sum+temp->data;
if(temp->left!=NULL)
enque(temp->left);
if(temp->right!=NULL)
enque(temp->right);
// printf("%d ",temp->data);
temp=deque();
}
if(maxsum<sum)
maxsum=sum;
if(temp==NULL)
{
enque(NULL);
temp=deque();
}
}
printf("\n maximum sum is %d",maxsum);
}
//main
void main()
{
struct treenode *root;
int i=1;
while(i)
{
printf("\n enter 1 to build elements");
printf("\n enter 2 print elements in level wise");
scanf("%d",&i);
switch(i)
{
case 1:
root=buildtree();
break;
case 2:
printlevel(root);
break;
}
}
}
Input:
3
/ \
4 7
/ \ / \
5 1 1 2
Return value: 11 Code:
#include<stdio.h>
#include<conio.h>
#include<malloc.h>
#define QUEUESIZE 20
struct treenode
{
int data;
struct treenode *left;
struct treenode *right;
} *root=NULL;
int *queue[QUEUESIZE];
int rear=-1,front=-1;
//queue finctions
void enque(struct treenode *root)
{
if(rear<QUEUESIZE)
{
queue[++rear]=root;
}
else printf("queue overflow");
}
int deque()
{
int i;
if(front!=rear)
i=queue[++front];
else printf("underfolw");
return i;
}
int isqempty()
{
if(front==rear)
return 1;
return 0;
}
//for building tree statically
struct treenode * buildtree()
{
struct treenode *temp1,*temp2,*temp3,*temp4,*temp5,*temp6;
root=(struct treenode *)malloc(sizeof(struct treenode));
temp1=(struct treenode *)malloc(sizeof(struct treenode));
temp2=(struct treenode *)malloc(sizeof(struct treenode));
temp3=(struct treenode *)malloc(sizeof(struct treenode));
temp4=(struct treenode *)malloc(sizeof(struct treenode));
temp5=(struct treenode *)malloc(sizeof(struct treenode));
temp6=(struct treenode *)malloc(sizeof(struct treenode));
root->data=4;
root->left=temp1;
temp1->data=5;
root->right=temp2;
temp2->data=6;
temp1->left=temp3;
temp3->data=7;
temp3->left=temp3->right=NULL;
temp1->right=temp4;
temp4->data=8;
temp4->left=NULL;
temp4->right=NULL;
temp2->left=temp5;
temp5->data=6;
temp2->right=temp6;
temp6->data=10;
temp5->left=temp5->right=temp6->left=temp6->right=NULL;
printf("\n tree buildedsuccessfull");
return root;
}
//levelsum
void printlevel(struct treenode *root)
{
int sum=0,maxsum=root->data;
struct treenode *temp;
enque(root);
enque(NULL);
temp=deque();
while(!isqempty())
{
sum=0;
while(temp!=NULL)
{
sum=sum+temp->data;
if(temp->left!=NULL)
enque(temp->left);
if(temp->right!=NULL)
enque(temp->right);
// printf("%d ",temp->data);
temp=deque();
}
if(maxsum<sum)
maxsum=sum;
if(temp==NULL)
{
enque(NULL);
temp=deque();
}
}
printf("\n maximum sum is %d",maxsum);
}
//main
void main()
{
struct treenode *root;
int i=1;
while(i)
{
printf("\n enter 1 to build elements");
printf("\n enter 2 print elements in level wise");
scanf("%d",&i);
switch(i)
{
case 1:
root=buildtree();
break;
case 2:
printlevel(root);
break;
}
}
}
No comments:
Post a Comment