Search code examples
c++recursionbinary-search-treenodes

c++ issue with function to check if tree is full


So I have a function to check if a tree is a full(if every node only has either 0 or 2 children). Every other function works and the problem is with this one (second one just calls helper). First user inputs string and it gets sorted in order(works). char at position: len/2 is turned into root and calls recursively to make rest of tree(works tried displaying). When running the code no matter what string input I provide, I get Tree is not full. Any help is appreciated. additional note: if commented lines are uncommented, the problem reverses and I constantly get Tree is full for every input. Can provide code for other functions if needed.

inputs I have tried: rats -> arst (root node r) shouldn't be full victorn -> cinortv (root node o) should be full

bool isFullTreehelper(TreeNode* R00t) 
{

    //if empty tree then true
    if (R00t == NULL)
        return true;

    //leaf node
    if (R00t->left == NULL && R00t->right == NULL)
        return true;

    //if (R00t->left != NULL && R00t->right != NULL)
        //return true;


    if ((R00t->left != NULL) && (R00t->right != NULL))
    return (isFullTreehelper(R00t->left) && isFullTreehelper(R00t->right));

    return false;

}


//update: addditonal code (currently checking to see if this creates a balanced tree)

TreeNode* sortedArrayToBST_helper(ItemType items[], int start, int end)
{
    // continue while this branch has values to process
    if (start > end)
        return NULL;
        // Get the middle element and make it root
    int mid = start + (end - start) / 2;
    TreeNode* head = new TreeNode(items[mid]);
    // Recursively construct the left subtree
    // and make it left child of root
    head->left = sortedArrayToBST_helper(items, start, mid - 1);
    // Recursively construct the right subtree
    // and make it right child of root
    head->right = sortedArrayToBST_helper(items, mid + 1, end);
    return head;
}

void TreeType::sortedArrayToBST(ItemType items[], int l)
{
    root = sortedArrayToBST_helper(items, 0, l);

    //debug lines
    //cout << root->info << endl;
    //cout << root->left->info << endl;
    //cout << root->right->info << endl;
    //cout << root->left->left->info << endl;
    //cout << root->left->right->info << endl;
    //cout << root->right->left->info << endl;
    //cout << root->right->right->info << endl;

}






Solution

  • "@VictorNath What value do you pass as l to the function sortedArrayToBST? It seems, in the helper function end is the last element (and not the one after the last). If so, you should pass items size minus one in the second argument to sortedArrayToBST." - Mikhail

    in summary solution was to subtract 1 from the length when calling sortedArrayBST