Check if a Binary Tree is a Sum Tree or not

A Sum-Tree is a Binary tree in which the value of each non-leaf node is equal to the sum of the values of all its children.

For example, the below tree is a Sum-Tree.

Write a function that checks whether a given tree is a Sum-Tree or not.

Solution:

Most of the Binary Tree functions are better written recursively. We just have to divide the entire solution into 

  1. Solution for the Root Node
  2. Solution for Left-SubTree
  3. Solution for Right Sub-Tree

Out of these, we have to solve the problem only for the root node and delegate the solution of Left and Right SubTrees to Recursion. 

Here is the code which will check if a Binary tree is a sum-tree or not.

/** Returns 1 if the tree is sum tree, else returns 0.
 *  Node struct of the tree is defined as below:
 *
 *  struct Node
 *  {
 *      int data;
 *      Node* lptr; // Left Sub-Tree
 *      Node* rptr; // Right Sub-Tree
 *  };
 */
int isSumTree(Node* r)
{
    // An Empty tree is a sum tree.
    // If the node is a leaf node, then it satisfies Sum-Tree
    if(r==NULL || r->lptr ==NULL && r->rptr == NULL)
        return 1;
    // If Left subtree is Empty, then check the right subtree only
    if(r->lptr ==NULL)
        return ( (r->rptr->data == r->data) && isSum(r->rptr) );
    // If Right subtree is Empty, then check the Left subtree only
    if(r->rptr ==NULL)
        return ( (r->lptr->data == r->data) && isSum(r->lptr) );
    if(r->data == r->lptr->data + r->rptr->data)
    {
        // This Node satisfies the sum-tree property.
        // So check the left & right subtrees
        return isSum(r->lptr) && isSum(r->rptr);
    }
    else
    {
        // This node does not satisfy the sum-tree property,
        // so don't need to check the child nodes.
        return 0;
    }
}
Please let me know your feedback.  

0 Comments

Leave a comment