Program to Check Whether a Binary Tree is Sum Tree or Not

• Write a C program to check if a binary tree is sum tree.

Given a binary tree, we have to check whether binary tree is a Sum Tree or not. A sum tree is a binary tree where each node is equal to the sum of left sum tree and right sub tree. The value of each leaf node will become to 0, as they don't have any sub tree. Here, we will recursively traverse each node of linked list and check whether the value of node is equal to the sum of nodes in left and right sub tree. Below is the detailed algorithm to check for sum tree.

---

Algorithm to check for Sum Tree
Let "node" be the pointer to the root node of a sub tree.

• If node is equal to NULL, return true. Empty tree is always a sum tree.
• If node is a leaf node, return true. A leaf node is a sum tree.
• Find the sum of all nodes in left and right sub tree. Let it be leftSubTreeSum and rightSubTreeSum.
• Check if node's value is equal to sum of leftSubTreeSum and rightSubTreeSum. If not equal then sub tree rooted at node is not a sum tree.
• Also check recursively whether left and right sub tree are sum tree or not.

Time Complexity : O(n²), Worst Case occurs for skewed tree.

---

C program check whether binary tree is Sum Tree

#include <stdio.h>
#include <limits.h>

#define TRUE 1
#define FALSE 0

struct node {
    int data;
    struct node *left;
    struct node *right;
};

struct node* getNewNode(int data) {
  /* dynamically allocate memory for a new node */ 
  struct node* newNode = (struct node*)malloc(sizeof(struct node));
 
  /* populate data in new Node */
  newNode->data = data;
  newNode->left = NULL;
  newNode->right = NULL;
  
  return newNode;
}

/*
This function returns below tree
            82
           / \
         35   6
        / \    \
       15  5    6
      / \
     7  8
*/
struct node* generateBTree(){
    // Root Node
    struct node* root =  getNewNode(82);
 
    root->left = getNewNode(35);
    root->right = getNewNode(6);
 
    root->left->left = getNewNode(15);
    root->left->right = getNewNode(5);
    root->right->right = getNewNode(6);
 
    root->left->left->left = getNewNode(7);
    root->left->left->right = getNewNode(8);
    
    return root;

}

/* Return sum of all the nodes of a binary tree */
int getTreeNodesSum(struct node *root) {
   if(root == NULL)
     return 0;
   /* Recursively calculate the sum of all nodes of 
   left and right sub tree and root node */
   return getTreeNodesSum(root->left) + root->data + getTreeNodesSum(root->right);
}
 
/* Check whether given binary tree satisfies Sum tree 
property or not. Returns 1 if true otherwise 0
*/
int isSumTree(struct node* node) {
    int leftSum, rightSum;
 
    /* Empty tree */
    if(node == NULL)
     return TRUE;
 /* Leaf Node */
 if(node->left == NULL && node->right == NULL)
        return TRUE;
 
   /* Find sum of left and right subtree */
   rightSum = getTreeNodesSum(node->right);
   leftSum = getTreeNodesSum(node->left);
 
   /* Check if root node staisfies Sum tree property and 
   also check if both subtree are also sum tree */
    if((node->data == leftSum + rightSum)&& isSumTree(node->left) &&
         isSumTree(node->right))
        return TRUE;
 
   return FALSE;
}

int main() {
    struct node *root = generateBTree();    
    
    if(isSumTree(root))
        printf("Given tree is Sum Tree\n");
    else
        printf("Not a Sum Tree\n");

    /* Modifying value of one node to breaj sun tree property */
    root->data = 100;
    
    if(isSumTree(root))
        printf("Given tree is Sum Tree\n");
    else
        printf("Not a Sum Tree\n");
    getchar();
    return 0; 
}

Output

Given tree is Sum Tree
Not a Sum Tree