Pages

Monday 27 August 2012

Finding max levelsum in binary tree

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 
            /    \ 
          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: