Check Children Sum Property in a Binary Tree
The "Children Sum Property" is a property of binary trees, which states that the value of a node in a binary tree must be equal to the sum of the values of its two children.
The "Check Children Sum Property" refers to the process of checking whether a given binary tree satisfies this property. To check this property, you need to traverse the binary tree in a recursive manner, starting from the root node. For each node, you need to check whether the sum of the values of its two children is equal to the value of the node itself. If this property holds true for all the nodes in the tree, then the tree is said to satisfy the "Children Sum Property".

In other words, the "Check Children Sum Property" is a way to ensure that the values of nodes in a binary tree are consistent with the sum of the values of their children, which is an important property in many applications of binary trees, such as in constructing binary search trees and performing various tree-based algorithms.
Program List
/*
C Program
+ Check Children Sum Property in a Binary Tree
*/
#include<stdio.h>
#include<stdlib.h>
//structure of Binary Tree node
struct Node {
int data;
struct Node *left, *right;
};
//Create a binary tree nodes and node fields (data,pointer)
//And returning the reference of newly nodes
struct Node *insert(int data) {
//create dynamic memory to new binary tree node
struct Node *new_node = (struct Node *) malloc(sizeof(struct Node));
if (new_node != NULL) {
//set data and pointer values
new_node->data = data;
new_node->left = NULL; //Initially node left-pointer is NULL
new_node->right = NULL; //Initially node right-pointer is NULL
} else {
printf("Memory Overflow\n");
exit(0); //Terminate program execution
}
//return reference
return new_node;
}
int children_sum(struct Node *root) {
if (root == NULL || (root->left == NULL && root->right == NULL)) return 1;
int leftData = 0, rightData = 0;
if (root->left != NULL) {
//get data of left child
leftData = root->left->data;
}
if (root->right != NULL) {
//get data of right child
rightData = root->right->data;
}
if (root->data != leftData + rightData) {
//when parent node data is not equal to child sum
return 0;
} else {
//recursively call
if (children_sum(root->left) && children_sum(root->right)) {
return 1;
}
return 0;
}
}
int main() {
struct Node *root = NULL;
/* Make A Binary Tree
-----------------------
7
/ \
4 3
/ \ / \
3 1 1 2
/
1
*/
//Insertion of binary tree nodes
root = insert(7);
root->left = insert(4);
root->right = insert(3);
root->right->right = insert(2);
root->right->left = insert(1);
root->left->left = insert(3);
root->left->right = insert(1);
root->left->right->left = insert(1);
if (children_sum(root)) {
printf("Yes\n");
} else {
printf("No\n");
}
//case 2
root->left->right->data = 2;
if (children_sum(root)) {
printf("Yes\n");
} else {
printf("No\n");
}
return 0;
}
Output
Yes
No
/*
C++ Program
Check Children Sum Property in a Binary Tree
*/
#include<iostream>
using namespace std;
class Node {
public:
int data;
Node *left, *right;
Node(int value) {
this->data = value;
this->left = NULL;
this->right = NULL;
}
};
class BinaryTree {
public:
Node *root;
BinaryTree() {
this->root = NULL;
}
bool children_sum(Node *head) {
if (head == NULL || (head->left == NULL && head->right == NULL)) {
return true;
}
int leftData = 0, rightData = 0;
if (head->left != NULL) {
leftData = head->left->data;
}
if (head->right != NULL) {
rightData = head->right->data;
}
if (head->data != leftData + rightData) {
return false;
} else {
if (this->children_sum(head->left) && this->children_sum(head->right)) {
return true;
}
return false;
}
}
};
int main() {
BinaryTree obj;
/* Make A Binary Tree
-----------------------
7
/ \
4 3
/ \ / \
3 1 1 2
/
1
*/
obj.root = new Node(7);
obj.root->left = new Node(4);
obj.root->right = new Node(3);
obj.root->right->right = new Node(2);
obj.root->right->left = new Node(1);
obj.root->left->left = new Node(3);
obj.root->left->right = new Node(1);
obj.root->left->right->left = new Node(1);
if (obj.children_sum(obj.root)) {
cout << "Yes\n";
} else {
cout << "No\n";
}
obj.root->left->right->data = 2;
if (obj.children_sum(obj.root)) {
cout << "Yes\n";
} else {
cout << "No\n";
}
}
Output
Yes
No
/*
Java Program
Check Children Sum Property in a Binary Tree
*/
//Class of Binary Tree node
class Node {
public int data;
public Node left, right;
//make a tree node
public Node(int value) {
//Assign field values
data = value;
left = null;
right = null;
}
}
public class BinaryTree {
public Node root;
public BinaryTree() {
//set initial tree root to null
root = null;
}
public boolean children_sum(Node head) {
if (head == null || (head.left == null && head.right == null)) {
return true;
}
int leftData = 0, rightData = 0;
if (head.left != null) {
//get data of left child
leftData = head.left.data;
}
if (head.right != null) {
//get data of right child
rightData = head.right.data;
}
if (head.data != leftData + rightData) {
//When parent node data is not equal to child sum
return false;
} else {
//recursively call
if (children_sum(head.left) && children_sum(head.right)) {
return true;
}
return false;
}
}
public static void main(String[] args) {
//Make object of Binary Tree
BinaryTree obj = new BinaryTree();
/*Make A Binary Tree
-----------------------
7
/ \
4 3
/ \ / \
3 1 1 2
/
1
*/
//Binary tree nodes
obj.root = new Node(7);
obj.root.left = new Node(4);
obj.root.right = new Node(3);
obj.root.right.right = new Node(2);
obj.root.right.left = new Node(1);
obj.root.left.left = new Node(3);
obj.root.left.right = new Node(1);
obj.root.left.right.left = new Node(1);
if (obj.children_sum(obj.root)) {
System.out.print("Yes\n");
} else {
System.out.print("No\n");
}
//case 2
obj.root.left.right.data = 2;
if (obj.children_sum(obj.root)) {
System.out.print("Yes\n");
} else {
System.out.print("No\n");
}
}
}
Output
Yes
No
/*
C# Program
Check Children Sum Property in a Binary Tree
*/
using System;
//Class of Binary Tree node
public class Node {
public int data;
public Node left, right;
//make a tree node
public Node(int value) {
//Assign field values
data = value;
left = null;
right = null;
}
}
public class BinaryTree {
public Node root;
public BinaryTree() {
//set initial tree root to null
root = null;
}
public Boolean children_sum(Node head) {
if (head == null || (head.left == null && head.right == null)) {
return true;
}
int leftData = 0, rightData = 0;
if (head.left != null) {
//get data of left child
leftData = head.left.data;
}
if (head.right != null) {
//get data of right child
rightData = head.right.data;
}
if (head.data != leftData + rightData) {
//When parent node data is not equal to child sum
return false;
} else {
//recursively call
if (children_sum(head.left) && children_sum(head.right)) {
return true;
}
return false;
}
}
public static void Main(String[] args) {
//Make object of Binary Tree
BinaryTree obj = new BinaryTree();
/*Make A Binary Tree
-----------------------
7
/ \
4 3
/ \ / \
3 1 1 2
/
1
*/
//Binary tree nodes
obj.root = new Node(7);
obj.root.left = new Node(4);
obj.root.right = new Node(3);
obj.root.right.right = new Node(2);
obj.root.right.left = new Node(1);
obj.root.left.left = new Node(3);
obj.root.left.right = new Node(1);
obj.root.left.right.left = new Node(1);
if (obj.children_sum(obj.root)) {
Console.Write("Yes\n");
} else {
Console.Write("No\n");
}
//case 2
obj.root.left.right.data = 2;
if (obj.children_sum(obj.root)) {
Console.Write("Yes\n");
} else {
Console.Write("No\n");
}
}
}
Output
Yes
No
# Python Program
# Check Children Sum Property in a Binary Tree
class Node :
def __init__(self, value) :
self.data = value
self.left = None
self.right = None
class BinaryTree :
def __init__(self) :
self.root = None
def children_sum(self, head) :
if (head == None or(head.left == None and head.right == None)) :
return True
leftData = 0
rightData = 0
if (head.left != None) :
leftData = head.left.data
if (head.right != None) :
rightData = head.right.data
if (head.data != leftData + rightData) :
return False
else :
if (self.children_sum(head.left) and self.children_sum(head.right)) :
return True
return False
def main() :
obj = BinaryTree()
# Make A Binary Tree
# 7
# / \
# 4 3
# / \ / \
# 3 1 1 2
# /
# 1
#
obj.root = Node(7)
obj.root.left = Node(4)
obj.root.right = Node(3)
obj.root.right.right = Node(2)
obj.root.right.left = Node(1)
obj.root.left.left = Node(3)
obj.root.left.right = Node(1)
obj.root.left.right.left = Node(1)
if (obj.children_sum(obj.root)) :
print("Yes")
else :
print("No")
obj.root.left.right.data = 2
if (obj.children_sum(obj.root)) :
print("Yes")
else :
print("No")
if __name__ == "__main__":
main()
Output
Yes
No
# Ruby Program
# Check Children Sum Property in a Binary Tree
class Node
attr_reader :data, :left, :right
attr_accessor :data, :left, :right
def initialize(value)
@data = value
@left = nil
@right = nil
end
end
class BinaryTree
attr_reader :root
attr_accessor :root
def initialize()
@root = nil
end
def children_sum(head)
if (head == nil or(head.left == nil and head.right == nil))
return true
end
leftData = 0
rightData = 0
if (head.left != nil)
leftData = head.left.data
end
if (head.right != nil)
rightData = head.right.data
end
if (head.data != leftData + rightData)
return false
else
if (self.children_sum(head.left) and self.children_sum(head.right))
return true
end
return false
end
end
end
def main()
obj = BinaryTree.new()
# Make A Binary Tree
# 7
# / \
# 4 3
# / \ / \
# 3 1 1 2
# /
# 1
#
obj.root = Node.new(7)
obj.root.left = Node.new(4)
obj.root.right = Node.new(3)
obj.root.right.right = Node.new(2)
obj.root.right.left = Node.new(1)
obj.root.left.left = Node.new(3)
obj.root.left.right = Node.new(1)
obj.root.left.right.left = Node.new(1)
if (obj.children_sum(obj.root))
print("Yes\n")
else
print("No\n")
end
obj.root.left.right.data = 2
if (obj.children_sum(obj.root))
print("Yes\n")
else
print("No\n")
end
end
main()
Output
Yes
No
/*
Node JS Program
Check Children Sum Property in a Binary Tree
*/
class Node {
constructor(value) {
this.data = value;
this.left = null;
this.right = null;
}
}
class BinaryTree {
constructor() {
this.root = null;
}
children_sum(head) {
if (head == null || (head.left == null && head.right == null)) {
return true;
}
var leftData = 0;
var rightData = 0;
if (head.left != null) {
leftData = head.left.data;
}
if (head.right != null) {
rightData = head.right.data;
}
if (head.data != leftData + rightData) {
return false;
} else {
if (this.children_sum(head.left) && this.children_sum(head.right)) {
return true;
}
return false;
}
}
}
function main() {
var obj = new BinaryTree();
/* Make A Binary Tree
-----------------------
7
/ \
4 3
/ \ / \
3 1 1 2
/
1
*/
obj.root = new Node(7);
obj.root.left = new Node(4);
obj.root.right = new Node(3);
obj.root.right.right = new Node(2);
obj.root.right.left = new Node(1);
obj.root.left.left = new Node(3);
obj.root.left.right = new Node(1);
obj.root.left.right.left = new Node(1);
if (obj.children_sum(obj.root)) {
process.stdout.write("Yes\n");
} else {
process.stdout.write("No\n");
}
obj.root.left.right.data = 2;
if (obj.children_sum(obj.root)) {
process.stdout.write("Yes\n");
} else {
process.stdout.write("No\n");
}
}
main();
Output
Yes
No
<?php
/*
Php Program
Check Children Sum Property in a Binary Tree
*/
class Node {
public $data;
public $left;
public $right;
function __construct($value) {
$this->data = $value;
$this->left = null;
$this->right = null;
}
}
class BinaryTree {
public $root;
function __construct() {
$this->root = null;
}
public function children_sum($head) {
if ($head == null || ($head->left == null && $head->right == null)) {
return true;
}
$leftData = 0;
$rightData = 0;
if ($head->left != null) {
$leftData = $head->left->data;
}
if ($head->right != null) {
$rightData = $head->right->data;
}
if ($head->data != $leftData + $rightData) {
return false;
} else {
if ($this->children_sum($head->left) && $this->children_sum($head->right)) {
return true;
}
return false;
}
}
}
function main() {
$obj = new BinaryTree();
/* Make A Binary Tree
-----------------------
7
/ \
4 3
/ \ / \
3 1 1 2
/
1
*/
$obj->root = new Node(7);
$obj->root->left = new Node(4);
$obj->root->right = new Node(3);
$obj->root->right->right = new Node(2);
$obj->root->right->left = new Node(1);
$obj->root->left->left = new Node(3);
$obj->root->left->right = new Node(1);
$obj->root->left->right->left = new Node(1);
if ($obj->children_sum($obj->root)) {
echo("Yes\n");
} else {
echo("No\n");
}
$obj->root->left->right->data = 2;
if ($obj->children_sum($obj->root)) {
echo("Yes\n");
} else {
echo("No\n");
}
}
main();
Output
Yes
No
/*
Swift 4 Program
Check Children Sum Property in a Binary Tree
*/
class Node {
var data: Int;
var left: Node? ;
var right: Node? ;
init(_ value: Int) {
self.data = value;
self.left = nil;
self.right = nil;
}
}
class BinaryTree {
var root: Node? ;
init() {
self.root = nil;
}
func children_sum(_ head: Node? ) -> Bool {
if (head == nil || (head!.left == nil && head!.right == nil)) {
return true;
}
var leftData: Int = 0;
var rightData = 0;
if (head!.left != nil) {
leftData = head!.left!.data;
}
if (head!.right != nil) {
rightData = head!.right!.data;
}
if (head!.data != leftData + rightData) {
return false;
} else {
if (self.children_sum(head!.left) && self.children_sum(head!.right)) {
return true;
}
return false;
}
}
}
func main() {
let obj: BinaryTree = BinaryTree();
/* Make A Binary Tree
-----------------------
7
/ \
4 3
/ \ / \
3 1 1 2
/
1
*/
obj.root = Node(7);
obj.root!.left = Node(4);
obj.root!.right = Node(3);
obj.root!.right!.right = Node(2);
obj.root!.right!.left = Node(1);
obj.root!.left!.left = Node(3);
obj.root!.left!.right = Node(1);
obj.root!.left!.right!.left = Node(1);
if (obj.children_sum(obj.root)) {
print("Yes");
} else {
print("No");
}
obj.root!.left!.right!.data = 2;
if (obj.children_sum(obj.root)) {
print("Yes");
} else {
print("No");
}
}
main();
Output
Yes
No
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment