Jun 112012
 

A Sum-Tree is a Binary tree, where each non-leaf node has a value equal to the sum of 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 tree functions are better written using 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.
—————————————————————

  One Response to “Check if a Binary Tree is a Sum Tree or not”

Comments (1)
  1. code for isSum?

 Leave a Reply

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

(required)

(required)