I am trying to implement the insert function for a pointer heap. Each node ("BinaryNode") stores an int and a string. My insert function is based on the explanation here. However, when I use this function to create a binary tree, it seems like I have a memory leak when it goes into the branch
else {
BinaryNode *curr;//potential problem
...}
For example, when I insert 1, 2, 3, 4, 5 (in that order), I want the tree to look like the tree here. Below is my insert function.
void MyTree::insert (int x ,string s) {
++size;
BinaryNode *pointer = new BinaryNode(s,x);
if (root == NULL) {
root = pointer;
tail = root;
return;
}
else if (tail == root) {
tail = pointer;
tail->parent = root;
root->lchild = tail;
}
else if (tail == tail->parent->lchild) {
tail->parent->rchild = pointer;
pointer->parent = tail->parent;
tail = pointer;
}
else {
BinaryNode *curr;//potential problem
for (curr = tail; curr->parent != NULL && curr == curr->parent->rchild; curr = curr->parent) {
continue;
if (curr == root)
break;
}
if (curr != root) {
curr = curr->parent->rchild;
}
while (curr->lchild != NULL) {
curr = curr->lchild;
}
cout << "curr: " << curr->getInt();
curr->lchild = pointer;
pointer->parent = curr;
tail = pointer;
}
return;
}
I realized the problem when I try to store a vector of BinaryNodes. When I try to push back the node containing 3 as the int, I get the following error:
*** Error in `./a.out': free(): invalid pointer: 0x00000000021cb010 ***
======= Backtrace: =========
...
To recap, calling the insert function doesn't give me any errors, but trying to store the node containing 3 in a vector gives the above error.
If my insert function looks fine, then I'll know to look at another function. Any insights are appreciated!
