Binary tree problem

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.

Code:

---

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

Code:

---

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.

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.

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

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++

Another Note, comment out the line

Code:

---

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.

> 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.

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

Code:

---

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.

>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:

Code:

---

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

---

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