Been working on this binary tree for the past few days, and everything works great except for the node removal which gives me weird results, either crashing the program with a seg fault or, more frequently, creating weird trees that don't make sense. I feel like the issue must be with my design.
Remove(node){
node parent = NULL;
if(node is not root)
parent = getParent(node);
if(node has both children){ //case: node has 2 children
node temp = findMinVal(node.rightChild); //Replace this data with min value leaf from right subtree
node.data = temp.data;
remove(temp); //Remove min value leaf from right subtree
}
if(parent != NULL){ //If this is not the root...
if(node has no children){ //case: node has 0 children
if(node is left child of parent) //These lines detach parent
parent.leftChild = NULL;
if(node is right child of parent)
parent.rightChild = NULL;
delete node;
treeSize--;
}
if(node has right child only){ //case: node has 1 right child
if(node is left child of parent) //These lines attach parent to right child
parent.leftChild = node.rightChild;
if(node is right child of parent)
parent.rightChild = node.rightChild;
delete node;
treeSize--;
}
if(node has left child only){ //case: node has 1 left child
if(node is left child of parent) //These lines attach parent to left child
parent.leftChild = node.leftChild;
if(node is right child of parent)
parent.rightChild = node.leftChild;
delete node;
treeSize--;
}
}
else{ //If this IS the root
if(node has no children){ //case: no children
delete node; //just delete it
treeSize--;
}
if(node has 1 right child){ //case: 1 right child
root = rightChild; //make right child the root
delete node;
treeSize--;
}
if(node has 1 left child){ //case 1 left child
root = leftChlid; //make left child the root
delete node;
treeSize--;
}
}
}
node findMinVal(node){ //Finds and returns the min value node of a tree at root node
if(node has no left child)
return node;
elsereturn findMinVal(node.leftChild)
}