Binary Tree Structure Balanced , EXC_BAD_ACCESS when using recursion

Question

I am working on question to check if Binary structure tree is balanced or not and when I run the code, I get EXC_BAD_ACCESS and I'm not sure how fix problem and what is causing it to break.

The code is suppose to hit NULL and return (true,-1) at some point and go deep into left subtree. Then return and go to right subtree. We can check whether the subtrees of left and right are balanced by different if it is <= 1. and get its height by max(left,right) +1 for each node. if <= 1 means not balance returns (false , height) and it bubbles up to recursion.

Thanks

#include <iostream>
using namespace std;

struct TreeNode {
    TreeNode * left;
    TreeNode * right;
};


class balanceStatusAndHeight{
public:
    bool isBalanced;
    int height;
    balanceStatusAndHeight(bool isBalanced, int height);
};


balanceStatusAndHeight::balanceStatusAndHeight(bool isBalanced, int height) {
    this->isBalanced = isBalanced;    
    this->height = height;
}




balanceStatusAndHeight checkBalance(TreeNode * root) {    

    if (root == NULL ) {
        return balanceStatusAndHeight(true, -1);
    }

    balanceStatusAndHeight leftResult = checkBalance(root->left);
    if ( !leftResult.isBalanced  ) {
        return leftResult;
    }

    balanceStatusAndHeight rightResult = checkBalance(root->right);
    if ( !rightResult.isBalanced) {
        return rightResult;
    }


    bool subTreesAreBalanced = abs(leftResult.height - rightResult.height) <= 1;
    int height = max(leftResult.height, rightResult.height) + 1;

    return balanceStatusAndHeight(subTreesAreBalanced, height);

};




int main(int argc, const char * argv[]) {

    TreeNode *a = new TreeNode;
    a->left = new TreeNode;
    a->left->left = new TreeNode;

    balanceStatusAndHeight c = checkBalance(a);


    cout << c.isBalanced << endl;



    return 0;
}

I see some tests for NULL, but absolutely no setting variables to NULL. Don't assume a dynamically allocated object is nicely initialized unless you do it yourself. Add a constructor to TreeNode to NULL right and left. — user4581301
Normally I'd suggest the following: Make absolutely certain that the recursion stops before you run out of stack. Since you have a really small tree here, that shouldn't happen, so my suggestion is you step through the program with your development environment's debugger and see where things go off the rails. But in this case, I think you've tripped over comment 1: The tree doesn't know where to stop and wanders off into invalid memory. — user4581301
@user4581301 Care to posit that as an answer :D I'd only add that if you really must use c++ for what you're doing you should familiarise yourself with valgrind valgrind.org — Keynan
AH yes that worked Thank You.. Why doesn't it c++ just do it for me and just put NULL or initialized nicely? @user4581301 — Kenneth Li
C++ is founded on the principle that you don't pay for anything you don't use. Automatic NULLing of variables is a cost that you don't need to pay if you are going to set the variable to a good value before you use it. End result is less work performed and faster programs. The downside is it's easier to blow yourself up through carelessness or ignorance. But one could say the same thing about a Bugatti. Stupidly fast. Stupidly easy to kill yourself with it, too. — user4581301

user4581301 user4581301 · Accepted Answer · 2020-01-30T02:54:49

In checkBalance

if (root == NULL )

expects tree branches to be NULL terminated. Unfortunately nothing in the code ensures that the trees are NULL terminated, so this test fails when it hits an uninitialized left or right pointer and then the program tries to access the invalid TreeNode at the uninitialized pointer.

With a modern compiler

struct TreeNode {
    TreeNode * left = NULL; // but prefer nullptr to NULL as it has better type safety
    TreeNode * right = NULL;
};

solves that problem. Since NULL is being used instead of nullptr the compiler may be old or deliberately set to an older C++ Standard revision and a constructor will be needed instead.

struct TreeNode {
    TreeNode * left;
    TreeNode * right;

    TreeNode():left(NULL), right(NULL)
    {

    }
};

A smarter constructor or crafty use of aggregate initialization can make your life easier.

Does the program work after this change? No idea. Didn't test for that. It exits without a crash, though.

Binary Tree Structure Balanced , EXC_BAD_ACCESS when using recursion

1 Answers