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 childrenÂ
Â
def 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 childrenÂ
def 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 approachÂ
using 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!
