Iterative approach to check for children sum property in a Binary Tree

0 0 6 minutes read

Given a binary tree, write a function that returns true if the tree satisfies below property:
For every node, data value must be equal to the sum of data values in left and right children. Consider data value as 0 for NULL children.
Examples:

Input : 
       10
      /  \
     8    2
    / \    \
   3   5    2
Output : Yes

Input :
         5
        /  \
      -2    7
      / \    \
     1   6    7
Output : No

We have already discussed the recursive approach. In this post an iterative approach is discussed.
Approach: The idea is to use a queue to do level order traversal of the Binary Tree and simultaneously check for every node:

If the current node has two children and if the current node is equal to the sum of its left and right children.
If the current node has just left child and if the current node is equal to its left child.
If the current node has just right child and if the current node is equal to its right child.

Below is the implementation of the above approach:

C++

// C++ program to check children sum property
#include <bits/stdc++.h>
using namespace std;
 
// A binary tree node
struct Node {
    int data;
    Node *left, *right;
};
 
// Utility function to allocate memory for a new node
Node* newNode(int data)
{
    Node* node = new (Node);
    node->data = data;
    node->left = node->right = NULL;
    return (node);
}
 
// Function to check if the tree holds
// children sum property
bool CheckChildrenSum(Node* root)
{
    queue<Node*> q;
 
    // Push the root node
    q.push(root);
 
    while (!q.empty()) {
        Node* temp = q.front();
        q.pop();
 
        // If the current node has both left and right children
        if (temp->left && temp->right) {
            // If the current node is not equal to
            // the sum of its left and right children
            // return false
            if (temp->data != temp->left->data + temp->right->data)
                return false;
 
            q.push(temp->left);
            q.push(temp->right);
        }
 
        // If the current node has right child
        else if (!temp->left && temp->right) {
            // If the current node is not equal to
            // its right child return false
            if (temp->data != temp->right->data)
                return false;
 
            q.push(temp->right);
        }
 
        // If the current node has left child
        else if (!temp->right && temp->left) {
            // If the current node is not equal to
            // its left child return false
            if (temp->data != temp->left->data)
                return false;
 
            q.push(temp->left);
        }
    }
 
    // If the given tree has children
    // sum property return true
    return true;
}
 
// Driver code
int main()
{
    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);
 
    if (CheckChildrenSum(root))
        printf("Yes");
    else
        printf("No");
 
    return 0;
}

Java

// Java program to check children sum property 
import java.util.*;
class GFG
{
 
// A binary tree node 
static class Node 
{ 
    int data; 
    Node left, right; 
} 
 
// Utility function to allocate memory for a new node 
static Node newNode(int data) 
{ 
    Node node = new Node(); 
    node.data = data; 
    node.left = node.right = null; 
    return (node); 
} 
 
// Function to check if the tree holds 
// children sum property 
static boolean CheckChildrenSum(Node root) 
{ 
    Queue<Node> q = new LinkedList<Node>(); 
 
    // add the root node 
    q.add(root); 
 
    while (q.size() > 0)
    { 
        Node temp = q.peek(); 
        q.remove(); 
 
        // If the current node has both left and right children 
        if (temp.left != null && temp.right != null)
        { 
            // If the current node is not equal to 
            // the sum of its left and right children 
            // return false 
            if (temp.data != temp.left.data + temp.right.data) 
                return false; 
 
            q.add(temp.left); 
            q.add(temp.right); 
        } 
 
        // If the current node has right child 
        else if (temp.left == null && temp.right != null)
        { 
            // If the current node is not equal to 
            // its right child return false 
            if (temp.data != temp.right.data) 
                return false; 
 
            q.add(temp.right); 
        } 
 
        // If the current node has left child 
        else if (temp.right == null && temp.left != null) 
        { 
            // If the current node is not equal to 
            // its left child return false 
            if (temp.data != temp.left.data) 
                return false; 
 
            q.add(temp.left); 
        } 
    } 
 
    // If the given tree has children 
    // sum property return true 
    return true; 
} 
 
// 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); 
 
    if (CheckChildrenSum(root)) 
        System.out.printf("Yes"); 
    else
        System.out.printf("No"); 
}
}
 
// This code is contributed by Arnab Kundu

Python3

# Python3 program to check 
# children sum property 
 
# A binary tree node 
class Node: 
     
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None
 
# Function to check if the tree holds 
# children sum property 
def CheckChildrenSum(root): 
 
    q = [] 
     
    # Push the root node 
    q.append(root) 
 
    while len(q) != 0:
        temp = q.pop() 
 
        # If the current node has both 
        # left and right children 
        if temp.left and temp.right: 
             
            # If the current node is not equal 
            # to the sum of its left and right
            # children, return false 
            if (temp.data != temp.left.data +
                             temp.right.data): 
                return False
 
            q.append(temp.left) 
            q.append(temp.right) 
         
        # If the current node has right child 
        elif not temp.left and temp.right: 
             
            # If the current node is not equal 
            # to its right child return false 
            if temp.data != temp.right.data: 
                return False
 
            q.append(temp.right) 
         
        # If the current node has left child 
        elif not temp.right and temp.left: 
             
            # If the current node is not equal 
            # to its left child return false 
            if temp.data != temp.left.data: 
                return False
 
            q.append(temp.left) 
 
    # If the given tree has children 
    # sum property return true 
    return True
 
# Driver code 
if __name__ == "__main__": 
 
    root = Node(10) 
    root.left = Node(8) 
    root.right = Node(2) 
    root.left.left = Node(3) 
    root.left.right = Node(5) 
    root.right.right = Node(2) 
 
    if CheckChildrenSum(root): 
        print("Yes") 
    else:
        print("No")
 
# This code is contributed 
# by Rituraj Jain

C#

// C# program to check children sum property 
using System;
using System.Collections.Generic; 
 
class GFG 
{ 
 
// A binary tree node 
public class Node 
{ 
    public int data; 
    public Node left, right; 
} 
 
// Utility function to allocate
// memory for a new node 
static Node newNode(int data) 
{ 
    Node node = new Node(); 
    node.data = data; 
    node.left = node.right = null; 
    return (node); 
} 
 
// Function to check if the tree holds 
// children sum property 
static Boolean CheckChildrenSum(Node root) 
{ 
    Queue<Node> q = new Queue<Node>(); 
 
    // add the root node 
    q.Enqueue(root); 
 
    while (q.Count > 0) 
    { 
        Node temp = q.Peek(); 
        q.Dequeue(); 
 
        // If the current node has both 
        // left and right children 
        if (temp.left != null && 
            temp.right != null) 
        { 
            // If the current node is not equal to 
            // the sum of its left and right children 
            // return false 
            if (temp.data != temp.left.data + 
                             temp.right.data) 
                return false; 
 
            q.Enqueue(temp.left); 
            q.Enqueue(temp.right); 
        } 
 
        // If the current node has right child 
        else if (temp.left == null && 
                 temp.right != null) 
        { 
            // If the current node is not equal to 
            // its right child return false 
            if (temp.data != temp.right.data) 
                return false; 
 
            q.Enqueue(temp.right); 
        } 
 
        // If the current node has left child 
        else if (temp.right == null &&
                 temp.left != null) 
        { 
            // If the current node is not equal to 
            // its left child return false 
            if (temp.data != temp.left.data) 
                return false; 
 
            q.Enqueue(temp.left); 
        } 
    } 
 
    // If the given tree has children 
    // sum property return true 
    return true; 
} 
 
// 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); 
 
    if (CheckChildrenSum(root)) 
        Console.WriteLine("Yes"); 
    else
        Console.WriteLine("No"); 
} 
} 
 
// This code is contributed by Rajput-Ji

Javascript

<script>
 
    // JavaScript program to check children sum property 
     
    // A binary tree node 
    class Node
    {
        constructor(data) {
           this.left = null;
           this.right = null;
           this.data = data;
        }
    }
     
    // Utility function to allocate memory for a new node 
    function newNode(data) 
    { 
        let node = new Node(data); 
        return (node); 
    } 
 
    // Function to check if the tree holds 
    // children sum property 
    function CheckChildrenSum(root) 
    { 
        let q = []; 
 
        // add the root node 
        q.push(root); 
 
        while (q.length > 0)
        { 
            let temp = q[0]; 
            q.shift(); 
 
            // If the current node has both left and right children 
            if (temp.left != null && temp.right != null)
            { 
                // If the current node is not equal to 
                // the sum of its left and right children 
                // return false 
                if (temp.data != temp.left.data + temp.right.data) 
                    return false; 
 
                q.push(temp.left); 
                q.push(temp.right); 
            } 
 
            // If the current node has right child 
            else if (temp.left == null && temp.right != null)
            { 
                // If the current node is not equal to 
                // its right child return false 
                if (temp.data != temp.right.data) 
                    return false; 
 
                q.push(temp.right); 
            } 
 
            // If the current node has left child 
            else if (temp.right == null && temp.left != null) 
            { 
                // If the current node is not equal to 
                // its left child return false 
                if (temp.data != temp.left.data) 
                    return false; 
 
                q.push(temp.left); 
            } 
        } 
 
        // If the given tree has children 
        // sum property return true 
        return true; 
    } 
     
    let 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); 
   
    if (CheckChildrenSum(root)) 
        document.write("Yes"); 
    else
        document.write("No"); 
     
</script>

Output:

Yes

Time Complexity: O(N), where N is the total number of nodes in the binary tree.
Auxiliary Space: O(N)

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 zambiatek!