Iterative approach to check for children sum property in a Binary Tree
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 nodestruct Node { int data; Node *left, *right;};// Utility function to allocate memory for a new nodeNode* 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 propertybool 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 codeint 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!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!
