Rotate image (square matrix) by 90 deg
Tue, 06 May 2025
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.
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.
Tue, 06 May 2025
Tue, 06 May 2025
Tue, 06 May 2025
Leave a comment