Sunday 3 September 2017

Write a program to find whether a given complete binary tree satisfies the min heap property.

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

int * createCompleteBinaryTree(int n);
void printCompleteBinaryTree(int * tree, int n);
int isSumProperty(int * tree, int n);

int main()
{
    int n, * tree;
    scanf("%d",&n);
    tree = createCompleteBinaryTree(n);
    if(isSumProperty(tree,n))
        printf("yes\n");
    else
        printf("no\n");
    return 0;
}

int * createCompleteBinaryTree(int n)
{
    int i;
    int * tree = (int *) malloc(n*sizeof(int));
    for(i=0;i<n;i++)
    {
        scanf("%d",(tree+i));
    }
    return tree;
}


void printCompleteBinaryTree(int * tree, int n)
{
    int i;
    for(i=0;i<n;i++)
        printf(" %d",*(tree+i));
    printf("\n");
}

int isSumProperty(int * tree, int n)
{
 int i,j=1,sum=0,m=0;
 m=n/2;
 for(i=0;i<m;i++)
 {
     sum=*(tree+i);
     if(sum>*(tree+j))
     {
         if(j>=n)
         break;
         else
         return 0;
     }
     if(sum>*(tree+j+1))
     {
         if((j+1)>=n)
         break;
         else
         return 0;
     }
    
     else{
     if(j>=n)
     break;
     j=j+2;
 }}
 return 1;
}

No comments:

Post a Comment