Given a binary tree, the task is to check for every node, its value is equal to the sum of values of its immediate left and right child. For NULL values, consider the value to be 0.
Example:
Input:
Output: The given tree satisfies the children sum property
Check for Children Sum Property in a Binary Tree using recursion:
To solve the problem follow the below idea:
Traverse the given binary tree. For each node check (recursively) if the node and both its children satisfy the Children Sum Property, if so then return true else return false
Below is the implementation of this approach:
C++
/* Program to check children sum property */#include <bits/stdc++.h>using namespace std;/* A binary tree node has data, leftchild and right child */struct node { int data; struct node* left; struct node* right;};/* returns 1 if children sum property holdsfor the given node and both of its children*/int isSumProperty(struct node* node){ /* left_data is left child data and right_data is for right child data*/ int sum = 0; /* If node is NULL or it's a leaf node then return true */ if (node == NULL || (node->left == NULL && node->right == NULL)) return 1; else { /* If left child is not present then 0 is used as data of left child */ if (node->left != NULL) sum += node->left->data; /* If right child is not present then 0 is used as data of right child */ if (node->right != NULL) sum += node->right->data; /* if the node and both of its children satisfy the property return 1 else 0*/ return ((node->data == sum) && isSumProperty(node->left) && isSumProperty(node->right)); }}/*Helper function that allocates a new nodewith the given data and NULL left and rightpointers.*/struct node* newNode(int data){ struct node* node = (struct node*)malloc(sizeof(struct node)); node->data = data; node->left = NULL; node->right = NULL; return (node);}// Driver Codeint main(){ struct node* root = newNode(10); root->left = newNode(8); root->right = newNode(2); root->left->left = newNode(3); root->left->right = newNode(5); root->right->right = newNode(2); // Function call if (isSumProperty(root)) cout << "The given tree satisfies " << "the children sum property "; else cout << "The given tree does not satisfy " << "the children sum property "; getchar(); return 0;}// This code is contributed by Akanksha Rai |
C
/* Program to check children sum property */#include <stdio.h>#include <stdlib.h>/* A binary tree node has data, left child and right child */struct node { int data; struct node* left; struct node* right;};/* returns 1 if children sum property holds for the given node and both of its children*/int isSumProperty(struct node* node){ /* left_data is left child data and right_data is for right child data*/ int left_data = 0, right_data = 0; /* If node is NULL or it's a leaf node then return true */ if (node == NULL || (node->left == NULL && node->right == NULL)) return 1; else { /* If left child is not present then 0 is used as data of left child */ if (node->left != NULL) left_data = node->left->data; /* If right child is not present then 0 is used as data of right child */ if (node->right != NULL) right_data = node->right->data; /* if the node and both of its children satisfy the property return 1 else 0*/ if ((node->data == left_data + right_data) && isSumProperty(node->left) && isSumProperty(node->right)) return 1; else return 0; }}/* Helper function that allocates a new node with the given data and NULL left and right pointers.*/struct node* newNode(int data){ struct node* node = (struct node*)malloc(sizeof(struct node)); node->data = data; node->left = NULL; node->right = NULL; return (node);}/* Driver code */int main(){ struct node* root = newNode(10); root->left = newNode(8); root->right = newNode(2); root->left->left = newNode(3); root->left->right = newNode(5); root->right->right = newNode(2); // Function call if (isSumProperty(root)) printf("The given tree satisfies the children sum " "property "); else printf("The given tree does not satisfy the " "children sum property "); getchar(); return 0;} |
Java
// Java program to check children sum property/* A binary tree node has data, pointer to left child and a pointer to right child */class Node { int data; Node left, right; public Node(int d) { data = d; left = right = null; }}class BinaryTree { Node root; /* returns 1 if children sum property holds for the given node and both of its children*/ int isSumProperty(Node node) { /* left_data is left child data and right_data is for right child data*/ int left_data = 0, right_data = 0; /* If node is NULL or it's a leaf node then return true */ if (node == null || (node.left == null && node.right == null)) return 1; else { /* If left child is not present then 0 is used as data of left child */ if (node.left != null) left_data = node.left.data; /* If right child is not present then 0 is used as data of right child */ if (node.right != null) right_data = node.right.data; /* if the node and both of its children satisfy the property return 1 else 0*/ if ((node.data == left_data + right_data) && (isSumProperty(node.left) != 0) && isSumProperty(node.right) != 0) return 1; else return 0; } } /* Driver code */ public static void main(String[] args) { BinaryTree tree = new BinaryTree(); tree.root = new Node(10); tree.root.left = new Node(8); tree.root.right = new Node(2); tree.root.left.left = new Node(3); tree.root.left.right = new Node(5); tree.root.right.right = new Node(2); // Function call if (tree.isSumProperty(tree.root) != 0) System.out.println( "The given tree satisfies children" + " sum property"); else System.out.println( "The given tree does not satisfy children" + " sum property"); }} |
Python3
# Python3 program to check children# sum property# Helper class that allocates a new# node with the given data and None# left and right pointers.class newNode: def __init__(self, data): self.data = data self.left = None self.right = None# returns 1 if children sum property# holds for the given node and both# of its childrendef isSumProperty(node): # left_data is left child data and # right_data is for right child data left_data = 0 right_data = 0 # If node is None or it's a leaf # node then return true if(node == None or (node.left == None and node.right == None)): return 1 else: # If left child is not present then # 0 is used as data of left child if(node.left != None): left_data = node.left.data # If right child is not present then # 0 is used as data of right child if(node.right != None): right_data = node.right.data # if the node and both of its children # satisfy the property return 1 else 0 if((node.data == left_data + right_data) and isSumProperty(node.left) and isSumProperty(node.right)): return 1 else: return 0# Driver Codeif __name__ == '__main__': root = newNode(10) root.left = newNode(8) root.right = newNode(2) root.left.left = newNode(3) root.left.right = newNode(5) root.right.right = newNode(2) # Function call if(isSumProperty(root)): print("The given tree satisfies the", "children sum property ") else: print("The given tree does not satisfy", "the children sum property ")# This code is contributed by PranchalK |
C#
// C# program to check children sum propertyusing System;/* A binary tree node has data, pointerto left child and a pointer to right child */public class Node { public int data; public Node left, right; public Node(int d) { data = d; left = right = null; }}class GFG { public Node root; /* returns 1 if children sum property holds for the given node and both of its children*/ public virtual int isSumProperty(Node node) { /* left_data is left child data and right_data is for right child data*/ int left_data = 0, right_data = 0; /* If node is NULL or it's a leaf node then return true */ if (node == null || (node.left == null && node.right == null)) { return 1; } else { /* If left child is not present then 0 is used as data of left child */ if (node.left != null) { left_data = node.left.data; } /* If right child is not present then 0 is used as data of right child */ if (node.right != null) { right_data = node.right.data; } /* if the node and both of its children satisfy the property return 1 else 0*/ if ((node.data == left_data + right_data) && (isSumProperty(node.left) != 0) && isSumProperty(node.right) != 0) { return 1; } else { return 0; } } } // Driver Code public static void Main(string[] args) { GFG tree = new GFG(); tree.root = new Node(10); tree.root.left = new Node(8); tree.root.right = new Node(2); tree.root.left.left = new Node(3); tree.root.left.right = new Node(5); tree.root.right.right = new Node(2); // Function call if (tree.isSumProperty(tree.root) != 0) { Console.WriteLine("The given tree satisfies" + " children sum property"); } else { Console.WriteLine( "The given tree does not" + " satisfy children sum property"); } }}// This code is contributed by Shrikant13 |
Javascript
<script> // JavaScript program to check children sum property class Node { constructor(data) { this.left = null; this.right = null; this.data = data; } } let root; /* returns 1 if children sum property holds for the given node and both of its children*/ function isSumProperty(node) { /* left_data is left child data and right_data is for right child data*/ let left_data = 0, right_data = 0; /* If node is NULL or it's a leaf node then return true */ if (node == null || (node.left == null && node.right == null)) return 1; else { /* If left child is not present then 0 is used as data of left child */ if (node.left != null) left_data = node.left.data; /* If right child is not present then 0 is used as data of right child */ if (node.right != null) right_data = node.right.data; /* if the node and both of its children satisfy the property return 1 else 0*/ if ((node.data == left_data + right_data) && (isSumProperty(node.left)!=0) && isSumProperty(node.right)!=0) return 1; else return 0; } } root = new Node(10); root.left = new Node(8); root.right = new Node(2); root.left.left = new Node(3); root.left.right = new Node(5); root.right.right = new Node(2); if (isSumProperty(root) != 0) document.write("The given tree satisfies the children" + " sum property"); else document.write("The given tree does not satisfy children" + " sum property"); </script> |
Output
The given tree satisfies the children sum property
Time Complexity: O(N), we are doing a complete traversal of the tree.
Auxiliary Space: O(log N), Auxiliary stack space used by recursion calls
Check for Children Sum Property in a Binary Tree using deque:
Follow the level order traversal approach and while pushing each node->left and node->right, if they exist add their sum and check if equal to current node->data.
Below is the implementation of this approach:
C++
/* Program to check children sum property */#include <bits/stdc++.h>using namespace std;/* A binary tree node has data, leftchild and right child */struct node { int data; struct node* left; struct node* right;};/* returns 1 if children sum property holdsfor the given node and both of its children*/ int isSumProperty(node *root) { queue<node*>q;//Stores the nodes at each subsequent level q.push(root); q.push(NULL); while(!q.empty()) { //Initialize the current as the first node of queue node* curr=q.front();q.pop(); if(curr==NULL) { //If there are more elements in the tree,then add NULL to continue if(!q.empty()) q.push(NULL);continue; } //Initialize sum with default value as 0 int sum=0; //Calculating sum =node->left->data+node->right->data if(curr->left) { q.push(curr->left); sum+=curr->left->data; } if(curr->right) { q.push(curr->right); sum+=curr->right->data; } //Sum==0 means its a Leaf Node so true/valid if(sum!=curr->data&&sum!=0) return 0; } return 1; }/*Helper function that allocates a new nodewith the given data and NULL left and rightpointers.*/struct node* newNode(int data){ struct node* node = (struct node*)malloc(sizeof(struct node)); node->data = data; node->left = NULL; node->right = NULL; return (node);}// Driver Codeint main(){ struct node* root = newNode(10); root->left = newNode(8); root->right = newNode(2); root->left->left = newNode(3); root->left->right = newNode(5); root->right->right = newNode(2); // Function call if (isSumProperty(root)) cout << "The given tree satisfies " << "the children sum property "; else cout << "The given tree does not satisfy " << "the children sum property "; getchar(); return 0;}// This code is contributed by Ishita Trivedi |
Java
import java.util.LinkedList;import java.util.Queue; /* A binary tree node has data, left child and right child */class Node { int data; Node left; Node right; Node(int value) { data = value; left = null; right = null; }}class Main { /* returns 1 if children sum property holds for the given node and both of its children*/ static int isSumProperty(Node root) { Queue<Node> q = new LinkedList<Node>(); q.offer(root); q.offer(null); while (!q.isEmpty()) { // Initialize the current as the first node of queue Node curr = q.poll(); if (curr == null) { // If there are more elements in the tree, // then add null to continue if (!q.isEmpty()) q.offer(null); continue; } // Initialize sum with default value as 0 int sum = 0; // Calculating sum =node->left->data+node->right->data if (curr.left != null) { q.offer(curr.left); sum += curr.left.data; } if (curr.right != null) { q.offer(curr.right); sum += curr.right.data; } // Sum==0 means its a Leaf Node so true/valid if (sum != curr.data && sum != 0) return 0; } return 1; } /* * Helper function that allocates a new node with the given data and NULL left * and right pointers. */ static Node newNode(int data) { Node node = new Node(data); node.data = data; node.left = null; node.right = null; return node; } // Driver Code public static void main(String[] args) { Node root = newNode(10); root.left = newNode(8); root.right = newNode(2); root.left.left = newNode(3); root.left.right = newNode(5); root.right.right = newNode(2); // Function call if (isSumProperty(root) == 1) System.out.println("The given tree satisfies the children sum property"); else System.out.println("The given tree does not satisfy the children sum property"); }} |
Python3
#Program to check children sum propertyfrom queue import Queue# Helper class that allocates a new# node with the given data and None# left and right pointers.class newNode: def __init__(self, data): self.data = data self.left = None self.right = None# returns 1 if children sum property# holds for the given node and both# of its childrendef isSumProperty(root): # Stores the nodes at each subsequent level q = Queue() q.put(root) q.put(None) while not q.empty(): # Initialize the current as the first node of queue curr = q.get() if curr == None: # If there are more elements in the tree, then add None to continue if not q.empty(): q.put(None) continue # Initialize sum with default value as 0 sum = 0 # Calculating sum = node.left.data + node.right.data if curr.left: q.put(curr.left) sum += curr.left.data if curr.right: q.put(curr.right) sum += curr.right.data # Sum == 0 means its a Leaf Node so true/valid if sum != curr.data and sum != 0: return 0 return 1# Driver Codeif __name__ == '__main__': root = newNode(10) root.left = newNode(8) root.right = newNode(2) root.left.left = newNode(3) root.left.right = newNode(5) root.right.right = newNode(2) # Function call if(isSumProperty(root)): print("The given tree satisfies the", "children sum property ") else: print("The given tree does not satisfy", "the children sum property ") |
C#
// C# program for the above approachusing System;using System.Collections.Generic;class Node { public int data; public Node left; public Node right; public Node(int value) { data = value; left = null; right = null; }}class GFG { /* returns 1 if children sum property holds for the given node and both of its children*/ static int isSumProperty(Node root) { Queue<Node> q = new Queue<Node>(); q.Enqueue(root); q.Enqueue(null); while (q.Count != 0) { // Initialize the current as the first node of queue Node curr = q.Dequeue(); if (curr == null) { // If there are more elements in the tree, // then add null to continue if (q.Count != 0) { q.Enqueue(null); } continue; } // Initialize sum with default value as 0 int sum = 0; // Calculating sum =node->left->data+node->right->data if (curr.left != null) { q.Enqueue(curr.left); sum += curr.left.data; } if (curr.right != null) { q.Enqueue(curr.right); sum += curr.right.data; } // Sum==0 means its a Leaf Node so true/valid if (sum != curr.data && sum != 0) { return 0; } } return 1; } /* * Helper function that allocates a new node with the given data and NULL left * and right pointers. */ static Node newNode(int data) { Node node = new Node(data); node.data = data; node.left = null; node.right = null; return node; } // Driver Code static void Main(string[] args) { Node root = newNode(10); root.left = newNode(8); root.right = newNode(2); root.left.left = newNode(3); root.left.right = newNode(5); root.right.right = newNode(2); // Function call if (isSumProperty(root) == 1) { Console.WriteLine("The given tree satisfies the children sum property"); } else { Console.WriteLine("The given tree does not satisfy the children sum property"); } }}// This code is contributed by rishabmalhdijo |
Javascript
// Program to check children sum propertyclass Node { constructor(data) { this.data = data; this.left = null; this.right = null; }}// Returns 1 if children sum property// holds for the given node and both// of its childrenfunction isSumProperty(root) { // Stores the nodes at each subsequent level let q = []; q.push(root); while (q.length > 0) { // Initialize the current as the first node of queue let curr = q.shift(); // Initialize sum with default value as 0 let sum = 0; // Calculating sum = node.left.data + node.right.data if (curr.left) { q.push(curr.left); sum += curr.left.data; } if (curr.right) { q.push(curr.right); sum += curr.right.data; } // Sum == 0 means its a Leaf Node so true/valid if (sum != curr.data && sum != 0) { return 0; } } return 1;}// Driver Codelet root = new Node(10);root.left = new Node(8);root.right = new Node(2);root.left.left = new Node(3);root.left.right = new Node(5);root.right.right = new Node(2);// Function callif (isSumProperty(root)) { console.log("The given tree satisfies the children sum property");} else { console.log("The given tree does not satisfy the children sum property");} |
Output
The given tree satisfies the children sum property
Time Complexity: O(N), for complete traversal of the tree.
Auxiliary Space: O(N), for storing the nodes in the deque.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
