The Children Sum Property states that, for each node in a Binary Tree, the value of the node must be equal to the sum of the values of its left and right children. If the node has no children, then the property is still satisfied.
Table of Contents
Write a function to check whether a given Binary Tree satisfies the Children Sum Property.
Consider the following Binary Tree:
10
/ \
8 2
/ \ \
3 5 2
Expected Output:
The given Binary Tree satisfies the Children Sum Property.
Time and Space Complexity:
The time complexity of checking the Children Sum Property for a Binary Tree is O(n), where n is the number of nodes in the tree. This is because we need to visit every node once.
The space complexity is O(h), where h is the height of the tree, due to the space used by the recursive function call stack.
C++ Solution:
#include <iostream>
// Define a node structure for the Binary Tree
struct Node {
int data;
Node* left;
Node* right;
Node(int value) {
data = value;
left = nullptr;
right = nullptr;
}
};
// Function to check if a Binary Tree satisfies the Children Sum Property
bool isChildrenSumPropertySatisfied(Node* root) {
// Base case: an empty tree or a leaf node satisfies the property
if (root == nullptr || (root->left == nullptr && root->right == nullptr))
return true;
int leftValue = (root->left) ? root->left->data : 0;
int rightValue = (root->right) ? root->right->data : 0;
// Check if the property is satisfied for the current node
if (root->data == leftValue + rightValue &&
isChildrenSumPropertySatisfied(root->left) &&
isChildrenSumPropertySatisfied(root->right)) {
return true;
}
return false;
}
int main() {
// Creating the Binary Tree
Node* 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);
// Check if the Children Sum Property is satisfied
bool isSatisfied = isChildrenSumPropertySatisfied(root);
if (isSatisfied) {
std::cout << "The Binary Tree satisfies the Children Sum Property." << std::endl;
} else {
std::cout << "The Binary Tree does not satisfy the Children Sum Property." << std::endl;
}
return 0;
}
Code Explanation:
- We define a Node structure for the Binary Tree, holding data, a left child, and a right child.
- The isChildrenSumPropertySatisfied function recursively checks whether the Children Sum Property is satisfied for the given Binary Tree. For each node, it calculates the sum of values of its left and right children, and then checks if the property holds for both the children as well.
- In the main function, we create the Binary Tree and call isChildrenSumPropertySatisfied to check if the property is satisfied or not.
When you run the code, it checks whether the given Binary Tree satisfies the Children Sum Property and prints the result accordingly.
Output:
The Binary Tree satisfies the Children Sum Property.