Binary tree problem

[moddinati]

hello,

I wrote a recursive function to try and find the depth of a binary tree, but when I run the program I keep getting an invalid memory access error.

A couple notes about the tree. The tree is NOT a linked list (not my choice), it is basically a giant array with indices of the daughters rather than pointers. Also, every box will be gauranteed to have two daughters.

int findNumLayers(int currentLayer,int whichBox, KDtree<DIM> myTree) {
    int branch1=0,branch2=0;   
    cout << "CurrentLayer = " << currentLayer << endl;
    cout << "WhichBox = " << whichBox << endl;
    //Every Leaf should have two daughters
    if(myTree.boxes[whichBox].dau1 != 0 && myTree.boxes[whichBox].dau2 != 0) {
        //Increment tree depth
        currentLayer++;  
        //Find depth of each branch
        branch1 = findNumLayers(currentLayer,myTree.boxes[whichBox].dau1,myTree);
        branch2 = findNumLayers(currentLayer,myTree.boxes[whichBox].dau2,myTree);
    }
    //Return maximum branch depth
    else if (currentLayer < branch1 && branch1 > branch2) return branch1;
    else if (currentLayer < branch2 && branch1 < branch2) return branch2;
    else return currentLayer;
}

The output I get when running this is

Number of Boxes: 8191
CurrentLayer = 0
WhichBox = 0
CurrentLayer = 1
WhichBox = 1
CurrentLayer = 2
WhichBox = 4097
CurrentLayer = 3
WhichBox = 6145
CurrentLayer = 4
WhichBox = 7169
CurrentLayer = 5
WhichBox = 7681
CurrentLayer = 6
WhichBox = 7937
CurrentLayer = 7
WhichBox = 8065
CurrentLayer = 8
WhichBox = 8129
CurrentLayer = 9
WhichBox = 8161
CurrentLayer = 10
WhichBox = 8177
CurrentLayer = 11
WhichBox = 8185
CurrentLayer = 12
WhichBox = 8189
Invalid memory access of location 1adf2ebc eip=1ad0c89e

I was able to calculate that there should be 12 layers in this example, so I think the problem lies in the return statement, although I can't seem to find it myself.

All help is appreciated.

[hk_mp5kpdw]

What happens after the "if" portion of the code gets executed? Does the function return any value?

...may not be the issue, but it is "return" related.

[Salem]

Use a debugger, let it catch the invalid memory access, then start working your way back to the problem.

[moddinati]

The problem with trying to use the debugger, is this C++ code is run through JAVA's JNI. I tried the debugger, but it was unhelpful.

I changed the return statement to something simple, such as "return 5;". I'm still getting the same issue. I can put print statements after the if statement and they execute fine.

EDIT: Just as a side note, I'm using the Netbeans IDE for the main editing but compiling my C++ code from command line using g++

[moddinati]

Another Note, comment out the line

branch2 = findNumLayers(currentLayer,myTree.boxes[whichBox].dau2,myTree);

So it only goes down one branch of the tree, it seems to work fine.

I still need to to traverse the entire tree though.

[swoopy]

> else if (currentLayer < branch1 && branch1 > branch2) return branch1;
This shouldn't be an else if. If you print out the values of branch1 and branch2 at this point, branch1 will equal 0, and so will branch2.

[moddinati]

thanks swoopy, fixed that issue.

That still doesn't resolve my main issue.

I did notice though, that (when I only traverse half the branch so it actually works), that as I return to java i get the following message

malloc: ***  Deallocation of a pointer not malloced: 0x1ad64000; This could be a double free(), or free() called with the middle of an allocated block;

I get this message 12 times, the number of times my recursive function gets called. This makes no sense to me. Any ideas?

EDIT: So I just started commenting stuff out until it works. I don't think it has anything to do with the recursive function. I commented the entire function out except for a single return statement, and I still got one of the errors above. I then commented out my input parameter 'KDtree<DIM> myTree' and it runs fine. Thanks for the help guys, I think this may be more of a JNI issue than a C++ issue. I'll move to some JNI forums.

[swoopy]

>I then commented out my input parameter 'KDtree<DIM> myTree' and it runs fine.
It probably won't help, but you might try passing myTree as a reference:

int findNumLayers(int currentLayer,int whichBox, KDtree<DIM> &myTree) {

[moddinati]

That was exactly the problem. Thanks swoopy, everything works great now.