Binary Tree: Given a binary tree, check if the tree is a children sum property

Problem Statement:

Given a binary tree, check if the tree is a children sum property .

Meaning, each root is a sum of its immediate two children

Solution Explanation:

We will solve the problem using recursion.

Check if the root node is equal to the sum of nodes of its children.

And continue till you reach till the end.

Time Complexity: O(n)
Space Complexity: O(h)

Code Solution

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct Node 
{
    int data;
    struct Node *left;
    struct Node *right;
};


struct Node* newNode(int data)
{
    struct Node* newNode = new Node;
    newNode->data = data;
    newNode->left = newNode->right = NULL;

    return (newNode);
}

void display_inorder(Node* root)
{
    if (root == NULL)
        return;

    display_inorder(root->left);
    cout << root->data << " ";
    display_inorder(root->right);
}


void insert_inorder(Node* root, vector<int>& nodes) 
{
    if (root == nullptr) 
    {
        return;
    }
  
    insert_inorder(root->left, nodes);  
    nodes.push_back(root->data);          
    insert_inorder(root->right, nodes); 
}

int solution(Node* root) 
{

	// if the root is null or if left and right children are null, return true
    if (root == nullptr || (root->left == nullptr && root->right == nullptr))
        return 1;
        
    int sum = 0;
    
    // if root has left child, add it
    if (root->left != nullptr)
        sum += root->left->data;

    // if root has left right, add it
    if (root->right != nullptr)
        sum += root->right->data;

    return ((root->data == sum)
            && solution(root->left)
            && solution(root->right));
    
}

int main(void)
{
    /*
     *           30
     *         /    \
     *        10     20
     *       / \    /  \
     *      5   5  10   10
     */

    struct Node* root = newNode(30);
    root->left = newNode(10);
    root->right = newNode(20);
    root->left->left = newNode(5);
    root->left->right = newNode(5);
    root->right->left = newNode(10);
    root->right->right = newNode(10);

    cout<< solution(root);
    
    return 0;
}

Output

1