Boolean Recursion Function for Binary Tree

Question

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;
}

See @john's answer. However, for this input, your code does give the right answer. Why don't you show an input for which this fails when it shouldn't? — cigien
– cigien, Commented May 9, 2020 at 21:03

john · Accepted Answer · 2020-05-09 21:09:30Z

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));
}

Collectives™ on Stack Overflow

Boolean Recursion Function for Binary Tree

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related