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.