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)

code for isSum?