CODEWITHSUNDEEP
c++recursion
George Go
George Go

Reputation: 77

Boolean Recursion Function for Binary Tree

So I have been trying to create a recursion function to identify if the each root's data is equivalent to the size of subtrees. For example) the tree below is true as all the subtree size is equivalent to the root value: grantparent (5) = 5 nodes parent (3)= 3 nodes

I think I got the logic but having trouble translating into code. I have to make sure once one parent' data value does not have same amounts of node, it carries all the way through the recursion and bring that false value.*** 

#include "pch.h"
#include <iostream>
#include <vector>
#include <queue>

using namespace std;


struct node{
    int data;
    node *left, *right;

};


node* newNode(int data)
{
    node *temp = new node;
    temp->data = data;
    temp->left = NULL;
    temp->right = NULL;
    return temp;
}

int sizeoftree(node* root) {
    if (root == nullptr)
        return 0;
    return sizeoftree(root->left) + 1 + sizeoftree(root->right);
}


bool thesizetree(node* root) {
    bool left;
    bool right;

    if (root == nullptr) {
        return true;
    }
    else if (sizeoftree(root) == root->data && root->left != nullptr&& root->right != nullptr) {
        left = thesizetree(root->left);
        right = thesizetree(root->right);
        return true;
    }
    else
        return false;
}

int main() {

    node *root = newNode(5);
    root->left = newNode(3);
    root->right = newNode(1);
    root->left->left = newNode(1);
    root->left->right = newNode(1);



    if (thesizetree(root))
         cout << "it is size tree" << endl;
     else
         cout << "it is not size tree" << endl;

return 0;
}

Upvotes: 0

Views: 166

Answers (1)

john
john

Reputation: 87959

Shouldn't

    left = thesizetree(root->left);
    right = thesizetree(root->right);
    return true;

be

    left = thesizetree(root->left);
    right = thesizetree(root->right);
    return left && right;

or somewhat more efficient

    return thesizetree(root->left) && thesizetree(root->right);

It should be a red flag in your code that you assign to the left and right variables but then never do anything with them.

Looking at bit closer you also don't want the nullptr checks because null is handled correctly at the start of your function. So

else if (sizeoftree(root) == root->data && root->left != nullptr&& root->right != nullptr) {

should be

else if (sizeoftree(root) == root->data) {

Putting all of that together this seems correct

bool thesizetree(node* root) {
    return root == nullptr || 
        (sizeoftree(root) == root->data &&
         thesizetree(root->left) &&
         thesizetree(root->right));
}

Upvotes: 1

Related Questions