Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com

Problem

Submissions

Hints & solutions

Discuss

Children Sum Property

Easy

0/40

35 upvotes

Problem statement

Return true if all non-leaf nodes in a given binary tree have a value that is equal to the sum of their child nodes, otherwise return false..

For Example:

Output: true 
Explanation: Node 2 and 3 are children of Node 1 and (3+1)=4.

Detailed explanation ( Input/output format, Notes, Images )

Input format:

The first line of each test case contains an integer ‘N’ i.e. the number of nodes in a tree.
The second line contains an array of integers of length (2*N +1), denoting the level order traversal of binary trees separated by a single space. Refer the image for input format.

Output Format:

The output contains a string “true” or “false”.

Note:-

You don’t need to print anything. Just implement the given function.

Sample Input 1:

4
5 3 2 3 -1 -1 -1 -1 -1

Sample Output 1:

true

Explanation Of Sample Input 1:

Node 1: The sum of its child nodes is 3 + 2 = 5, which is equal to its value.
Node 2: The sum of its child nodes is 3, which is equal to its value.
Node 3: It is a leaf node with no child nodes, so the condition is satisfied.
Node 4: It is a leaf node with no child nodes, so the condition is satisfied.

Sample Input 2:

6
7 3 4 3 -1 2 3 -1 -1 -1 -1 -1 -1

Sample Output 2:

false

Explanation Of Sample Input 2:

Node 1: The sum of its child nodes is 3 + 4 = 7, which is equal to its value.
Node 2: The sum of its child nodes is 3, which is equal to its value.
Node 3: The sum of its child nodes is 2 + 3 = 5, which is not equal to its value 4, so the condition is not satisfied. Hence the answer is false.

Constraints:

1 <= N <= 10^3
1 <= data <= 10^5
Time Limit: 1 sec

Hint 1

Hint 2

Recursively subtract child node values from the parent node and check if the resulting value is zero.

Approaches (2)

Approach 1

Approach 2

Recursive

Approach:

The approach checks the sum property recursively for each node in the binary tree. It starts by checking if the current node is null or a leaf node. If so, it returns true as it automatically satisfies the sum property. For non-leaf nodes, it subtracts the values of the left and right child nodes from the current node's value. If the resulting value is not equal to 0, it returns false as it violates the sum property. The process is then applied recursively to the left and right subtrees. If both subtrees satisfy the sum property, it returns true; otherwise, it returns false.

Algorithm:

function isParentSum( root )

if root is null or (root has no left child and no right child):
- return true
if root has a left child:
- root->data -= root->left->data
if root has a right child:
- root->data -= root->right->data
if root->data is not equal to 0:
- return false
return isParentSum( root->left ) AND isParentSum( root->right )

Time Complexity

O(N), where ‘N’ is the number of nodes in the binary tree.

The time complexity of the code is O(N), where ‘N’ is the number of nodes in the binary tree because this approach traverses each node of the tree exactly once in the worst case.

Space Complexity

O(N), where ‘N’ is the number of nodes in the binary tree.

The space complexity is O(h), where ‘h’ is the height of the binary tree. This space is used to store the recursive function calls on the function call stack. In the worst case scenario, where the tree is skewed and has a height of ‘N’ (where ‘N’ is the number of nodes in the tree), the space complexity would be O(N) as the recursion can go up to the height of the tree.

(100% EXP penalty)

Children Sum Property

Interview problems

Java Easy recursive using left and right Sum

public class Solution {
    public static boolean isParentSum(Node root) {
        // Write your code here.
        if(root==null)return true;
        return is(root)>=0;
    }


    public static int is(Node root){
        if(root==null){
            return 0;
        }


        int leftSum=is(root.left);
        int rightSum=is(root.right);
        
        if(leftSum==0 && rightSum==0){
            return root.data;
        }
        if(leftSum+rightSum==root.data){
            return root.data;
        }
        return Integer.MIN_VALUE;
    }
}

java

51 views

0 replies

0 upvotes

Harsh Raj

Interview problems

c++ recursive code

bool isParentSum(Node *root){

int sum= 0 ;

if(root == nullptr || root->left == NULL && root->right == NULL)

return true ;

else{

if(root->left != nullptr){

sum += root->left->data ;

}

if(root->right != nullptr){

sum += root->right->data ;

}

return ((root->data == sum)

&& isParentSum(root->left)

&& isParentSum(root->right));

}

488 views

0 replies

0 upvotes

Shubham kumar

Interview problems

C++ || Simple few lines solution

bool isParentSum(Node *root){

if(!root) return true;

if(root && !root->left && !root->right) return true;

int leftSum = 0, rightSum = 0;

if(root->left)

leftSum = root->left->data;

if(root->right)

rightSum = root->right->data;

if(root->data != leftSum + rightSum || !isParentSum(root->left) || !isParentSum(root->right))

return false;

return true;

}

426 views

0 replies

1 upvote

Nilesh Sunil Kudale

Interview problems

Easy Solution in C++ By NK

pair<bool,int> isSum(Node* root){

if(root==NULL){

pair<bool,int>p=make_pair(true,0);

return p;

}

if(root->left==NULL && root->right==NULL){

pair<bool,int>p=make_pair(true,root->data);

return p;

}

pair<bool,int> leftAns=isSum(root->left);

pair<bool,int> rightAns=isSum(root->right);

bool left=leftAns.first;

bool right=rightAns.first;

bool cond=root->data==leftAns.second+rightAns.second;

pair<bool,int>ans;

if(left && right && cond){

ans.first=true;

ans.second=root->data;

}

else{

ans.first=false;

}

return ans;

}

bool isParentSum(Node *root){

// Write your code here.

return isSum(root).first;

}

156 views

0 replies

1 upvote

Priyansh Kumar

Interview problems

C++ Code || Recursive Approach

bool isLeafNode(Node* node) {

return (node != NULL) && (node->left == NULL) && (node->right == NULL);

}

bool isParentSum(Node* root) {

if (root == NULL) {

return true;

}

if (isLeafNode(root)) {

return true;

}

int leftSum = 0, rightSum = 0;

if (root->left != NULL) {

leftSum = root->left->data;

}

if (root->right != NULL) {

rightSum = root->right->data;

}

if ((root->data != leftSum + rightSum) ||

(!isParentSum(root->left)) ||

(!isParentSum(root->right))) {

return false;

}

return true;

}

169 views

0 replies

0 upvotes

Vishesh Upadhyay

Interview problems

easy solution in java using preorder

public class Solution {

static boolean flag=true;

public static boolean isParentSum(Node root) {

if (root==null)return false;

preorder(root);

return flag;

}

public static void preorder(Node root) {

if (root==null) {

return ;

}

if (root.left != null || root.right!=null) {

int sum =0;

if(root.left !=null) {

sum+=root.left.data;

}

if(root.right !=null) {

sum+=root.right.data;

}

if (sum != root.data) {

flag = false;

}

preorder(root.left);

preorder(root.right);

}

235 views

0 replies

1 upvote

Piyush Sahu

Interview problems

Recursive C++ solution

void check(Node* root,bool & b){

if(root==NULL||(!root->left&&!root->right)){

return;

}

int l = 0;

int r = 0;

if(root->left) l = root->left->data;

if (root->right) r = root->right->data;

if(root->data==l+r){

check(root->left,b);

check(root->right,b);

}

else{

b=false;

}

bool isParentSum(Node *root){

// Write your code here.

bool b = true;;

check(root,b);

return b;

}

395 views

0 replies

1 upvote

Harish Ishwar Naik

Interview problems

The most Simple solution

bool isParentSum(Node *root)

{

int child = 0;

if(root==NULL)

return true;

if(root->left)

child += root->left->data;

if(root->right)

child += root->right->data;

if(child!=root->data && child!=0)

return false;

return isParentSum(root->left) && isParentSum(root->right);

}

923 views

2 replies

1 upvote

Rahul Kumar Abhishek

Interview problems

Children Sum Property - java

public class Solution {

public static boolean isParentSum(Node root) {

// Write your code here.

if(root == null){

return false;

}

Queue<Node> q = new LinkedList<>();

q.add(root);

while(!q.isEmpty()){

int size = q.size();

for(int i = 0; i<size;i++){

Node node = q.remove();

int localSum = 0;

if(node.left != null){

q.add(node.left);

localSum+=node.left.data;

}

if(node.right != null){

q.add(node.right);

localSum+=node.right.data;

}

//if leaf node then continue the loop

if(node.left == null && node.right == null){

continue;

}

if(localSum != node.data){

return false;

}

return true;

}

318 views

0 replies

2 upvotes

Ajay Nishad

Interview problems

Easy JAVA solution


class Pair{
    boolean first;
    int second;
    public Pair(boolean first, int second){
        this.first = first;
        this.second = second;
    }
}


public class Solution {

    public static Pair helper(Node root){

        if(root==null){
            Pair p = new Pair(true,0);
            return p;
        }

        if(root.left==null && root.right==null){
            Pair p = new Pair(true,root.data);
            return p;
        }

        Pair leftSide = helper(root.left);
        Pair rightSide = helper(root.right);

        Pair p = new Pair(true, 0);
        if(leftSide.first && rightSide.first && root.data == leftSide.second+rightSide.second){
            p.second = root.data;
            p.first = true;
            return p;
        }

        return new Pair(false,root.data);
    }

    public static boolean isParentSum(Node root) {

        Pair ans = helper(root);

        return ans.first;
    }
}

192 views

0 replies

0 upvotes

Console