NPTEL(WEEK-6.1)

Programming Assignment 6.1: Value Balanced Tree

Due on 2016-03-05, 23:55 IST

A tree is called value balanced tree if for all nodes, sum of values (assume the values are integers) of nodes in left hand side is equal to sum of values in right hand side.

Given a complete binary tree find if it is a value balanced tree or not.

You have to complete isValueBalanced(int [], int) function. You can create other functions but should be called from given function.

Input Constraints:

The input tree would be always a complete binary tree.

Input:

Number of Nodes in first line and values of nodes in level order (as represented as array) in next.

Output:

Either “Tree is value balanced” or “Tree is not value balanced”

PROGRAM:

#include <cstdio>

#define MAX 100

using namespace std;

/**

 * Check given tree is value balanced or not

 * @param tree  : int array : Array representation of a complete binary tree

 * @param count : int   : Number of elements in tree

 * @return boolean : Given tree is value balanced or not

 */

bool isValueBalanced(int tree[], int count);

int main() {

int count;

int tree[MAX];

scanf("%d",&count);

for (int i = 0; i < count; ++i) {

       scanf("%d",&tree[i]);

}

if(isValueBalanced(tree, count)) {

      printf("Tree is value balanced");

} else {

      printf("Tree is not value balanced");

}

return 0;

}

CODING :

bool isValueBalanced(int tree[],int count){
int loop,a,b;

loop=((count-1)/2) - 1;

 while(loop != -1){
    a=(2*loop) + 2;
    b=2*loop+1;

   if(tree[a] != tree[b])
     { return false;}
   else{
      tree[loop]=tree[loop] + tree[a]+tree[a];
      loop--;
       }

 }
 return true;

}