SegFault in BSTs' remove Method

edge6768 (124)
Hey guys,

I recently started using a new data set with my BST class and SegFaults started popping up... It's happening somewhere within the recursive remove methods' handling of deleting a node with two children (currently commented out so it will run). Does anyone see where the error is?

Additionally, I really feel like I made the remove function more complicated/verbose than it really is and would appreciate any suggestions to simplify it.

remove:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
 
template<typename U>
bool bst<U>::remove(U toDel) {
	bstNode<U>* cur = getPtr(toDel, root);
	return remove(toDel, cur);
} // END delete(toDel)

template<typename U>
bool bst<U>::remove(U toDel, bstNode<U>*& cur) {
	if(!cur) {
		return false;
	} // END if

	if(cur->data == toDel) {
		bstNode<U>* parent = getParent(toDel, root, nullptr);

		if(cur->left == nullptr && cur->right == nullptr) { // Zero children
			cout << "Removed node (" << toDel << ") w/zero children.\n";
		} else if( (cur->left != nullptr) && (cur->right != nullptr) ) { // Two children *****************ERROR HERE********************
				bstNode<U>* min = getMin(cur->right);

				// if(parent->right == cur) { // Node is a right child
				// 	parent->right = min;
				// } else { // Node is a left child
				// 	parent->left = min;
				// } // END if/else

				// min->right = cur->right;
				// min->left = cur->left;

				cout << "Removed node (" << toDel << ") w/two children.\n";
		} else { // One child

			if(toDel < parent->data) { // Node is a left child
				if(cur->left != nullptr) { // Nodes' child is on left
					parent->left = cur->left;
					cur->left = nullptr;
				} else { // Nodes' child is on right
					parent->left = cur->right;
					cur->right = nullptr;
				} // END if/else

			} else { // Node is a right child
				if(cur->left != nullptr) { // Nodes' child is on left
					parent->right = cur->left;
					cur->left = nullptr;
				} else { // Nodes' child is on right
					parent->right = cur->right;
					cur->right = nullptr;
				} // END if/else

			} // END if/else
			cout << "Removed node (" << toDel << ") w/one child.\n";
		} // END if/else

		delete cur;
		cur = nullptr;

		nodeCount--;
	return true;
	} // END if

} // END remove(toDel, cur)


getMin:
1
2
3
4
5
6
7
8
9
 
template<typename U>
bstNode<U>* bst<U>::getMin(bstNode<U>* cur) {
	if(!cur || !cur->left) { // data not found || min is reached
		return cur;
	} else { // min is not reached
		return getMin(cur->left);
	} // END if/else

} // END getMin(data, cur)


Thanks for any input!
helios (17607)
Where's the recursion? I don't see any recursive calls.

Does getParent() always return a non-null pointer? I don't see any checks. What does it return if the node is the root? Also, it's kind of strange that you pass toDel instead of cur.

Line 28 creates a cycle in the tree structure. By definition of getMin(), min is cur->left or an (grand-)child of cur->left, so line 28 causes this loop to never end:
1
2
3
4
 
// min->left = cur->left;
auto current = cur;
while (current)
    current = current->left;
edge6768 (124)
I have updated the remove function to 1) no longer be 'recursive' as all recursion is handled by the helper methods getPtr, getMin, and getParent. I also added a check for the case in which the item to delete is the root, because getParent does return nullptr if it is passed the root (full method below). However, I am still getting SegFaults... I also removed the line min->right = cur->right because as you pointed out it would create a loop.

getParent:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 
template<typename U>
bstNode<U>* bst<U>::getParent(U data, bstNode<U>* cur, bstNode<U>* prev) {
	if(cur->data == data) {
		return prev;
	} else if(!cur) {
		return cur;
	} // END if/else

	if(data < cur->data) {
		return getParent(data, cur->left, cur);
	} else {
		return getParent(data, cur->right, cur);
	} // END if/else

} // END getParent(data)


getPtr:
1
2
3
4
5
6
7
8
9
10
11
12
13
 
template<typename U>
bstNode<U>* bst<U>::getPtr(U data, bstNode<U>* cur) {
	if(!cur || (cur->data == data) ) {
		return cur;
	} // END if

	if(data < cur->data) {
		return getPtr(data, cur->left);
	} else {
		return getPtr(data, cur->right);
	} // END if/else

} // END getPtr(data, cur)


Updated remove():
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
 
template<typename U>
bool bst<U>::remove(U toDel) {
	bstNode<U>* cur = getPtr(toDel, root);
	if(cur == root) {
		root = getMin(root->right);
		delete cur;
		cur = nullptr;
		nodeCount--;
	return true;
	} // END if

	if(!cur) {
		return false;
	} // END if

	if(cur->data == toDel) {
		bstNode<U>* parent = getParent(toDel, root, nullptr);

		if(cur->left == nullptr && cur->right == nullptr) { // Zero children
			cout << "Removed node (" << toDel << ") w/zero children.\n";
		} else if( (cur->left != nullptr) && (cur->right != nullptr) ) { // Two children
				bstNode<U>* min = getMin(cur->right);\
				
				if(parent->right == cur) { // Node is a right child
					parent->right = min;
				} else { // Node is a left child
					parent->left = min;
				} // END if/else

				min->left = cur->left;

				cout << "Removed node (" << toDel << ") w/two children.\n";
		} else { // One child

			if(toDel < parent->data) { // Node is a left child
				if(cur->left != nullptr) { // Nodes' child is on left
					parent->left = cur->left;
					cur->left = nullptr;
				} else { // Nodes' child is on right
					parent->left = cur->right;
					cur->right = nullptr;
				} // END if/else

			} else { // Node is a right child
				if(cur->left != nullptr) { // Nodes' child is on left
					parent->right = cur->left;
					cur->left = nullptr;
				} else { // Nodes' child is on right
					parent->right = cur->right;
					cur->right = nullptr;
				} // END if/else

			} // END if/else
			cout << "Removed node (" << toDel << ") w/one child.\n";
		} // END if/else

		delete cur;
		cur = nullptr;

		nodeCount--;
	return true;
	} // END if
} // END remove(toDel)
cire (8284)
There is an obvious problem with:
 
1
2
3
4
5
6
7
8
9
10
11
12
13
 
template<typename U>
bstNode<U>* bst<U>::getPtr(U data, bstNode<U>* cur) {
	if(!cur || (cur->data == data) ) {
		return cur;
	} // END if

	if(data < cur->data) {
		return getPtr(data, cur->left);
	} else {
		return getPtr(data, cur->right);
	} // END if/else

} // END getPtr(data, cur)


When cur is null, you avoid dereferencing it on line 3, but... you do dereference it on line 7.
Last edited on
edge6768 (124)
@cire
Why wouldn't the return cur; on line 4 prevent line 7 from ever being reached if cur was nullptr? Wouldn't it exit the recursive stack?
cire (8284)
No, no. You're right. I misread.
cire (8284)
Unfortunately, getParent doesn't do that right. If cur is null, it goes ahead and dereferences it on line 3 anyway.
edge6768 (124)
OK, I definitely see that one but I don't see how it would cause a segFault as the remove() method ensures that when getParent is called it will return a valid ptr (unless I am not removing the nodes correctly, which is totally possible) since it handles the root case and not found case before calling getParent. (Right? I'm progressively getting more and more confused lol)
helios (17607)
You removed the wrong line. You're still creating a cycle in the tree.
And once you remove the correct line, you'll still need to do something with cur->left. You can't just leak the node like you're doing now with cur->right.

Post the node destructor.
Last edited on
edge6768 (124)
@cire
Although I don't understand how I did swap around the getParent method to validate cur and the segFault stopped.

@helios
There is no destructor, I created it as a struct.
bstNode:
1
2
3
4
5
6
 
template<typename T>
struct bstNode {
	bstNode* left   = nullptr;
	bstNode* right  = nullptr;
	T data;
}; // END bstNode


Here is the destructor for the bst class though:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
 
template<typename U>
bst<U>::~bst() {
	DESTROY(root);
} // END ~bst()

template<typename U>
void bst<U>::DESTROY(bstNode<U>* cur) {
	if(!cur) {

		if(!cur->left && !cur->right) {
			delete cur;
			cur = nullptr;
		} else {
			DESTROY(cur->left);
			DESTROY(cur->right);
		} // END if/else

	} // END if

return;
} // END DESTROY(cur)


I see the leaked node (I'm gonna' try my hand at fixing that now that the segFault has quit). I think I see the cycle but only in the case the there is no left node to the right child of the node being deleted, in which cur->right would be pointing to min and setting min->right to itself would create the cycle. Is that the only case I need to worry about?
Last edited on
helios (17607)
This is unrelated to your problems, but bst<U>::DESTROY() does nothing unless passed a null pointer, and in that case it tries to dereference it.

Oops. My bad. I thought your were passing cur to getMin(), but you're passing cur->right. You were right to remove that line, and the line that remains should not create a cycle, AFAICT.
edge6768 (124)
O wow, I had gone through and tried to all replace all my 'pointer == something' or 'pointer != something' to just 'pointer' or '!pointer' and got that one mixed up. Not even gonna' ask how that wasn't throwing segFaults =P

Thank you both for all the help I really appreciate it!
cire (8284)
OK, I definitely see that one but I don't see how it would cause a segFault as the remove() method ensures that when getParent is called it will return a valid ptr...
...Although I don't understand how I did swap around the getParent method to validate cur and the segFault stopped.


getParent calls itself and when it calls itself it makes no attempt to ensure it does so with a non-null pointer.
dhayden (5799)
Referring to your latest code:

Line 5:This replaces the entire tree with the smallest node, leaking then rest of the tree.

Line 16. The if is unnecessary since getptr() returned the node that you want.

I think you'll find the code a lot easier to write if you getPtr(), getParent() and getMin() return references to the appropriate pointers rather than copies of them. It means you'll have to pass the root by reference.
dhayden (5799)
I tried writing remove() assuming that getParent(), getMin() and getPtr() return references. As I suspected, it was much shorter: just 39 lines.
Topic archived. No new replies allowed.