Below is a method to remove a node from a binary search tree. I don't get why we need the first if statement. If the binaryTree is null, why do we return binaryTree? Shouldn't we return null? I will really appreciate your response.
public BST remove(int valueToRemove) {//12
removeHelper(this,valueToRemove);
return this;
}
public BST removeHelper(BST binaryTree,int valueToRemove) {
if(binaryTree==null){
return binaryTree;
}
//larger->go to the right
if(valueToRemove>binaryTree.value){
binaryTree.right=removeHelper(binaryTree.right,valueToRemove);//to remove
//smaller->go to the left
}else if(valueToRemove< binaryTree.value){
binaryTree.left=removeHelper(binaryTree.left,valueToRemove);//to remove
}else{
if(binaryTree.left==null&&binaryTree.right==null){
return null;
}else if(binaryTree.left!=null&&binaryTree.right==null){
binaryTree.value= binaryTree.left.value;
binaryTree.left=binaryTree.left.left;
binaryTree.right=binaryTree.left.right;
}
else if(binaryTree.left==null&&binaryTree.right!=null){
binaryTree.value= binaryTree.right.value;
binaryTree.left=binaryTree.right.left;
binaryTree.right=binaryTree.right.right;
}else{//when you find the value to remove
binaryTree.value=getSmallestValue(binaryTree.right);
binaryTree.right=removeHelper(binaryTree.right,binaryTree.value);//to remove
return binaryTree;
}
}
return this;
}
public int getSmallestValue(BST binaryTree) {
return binaryTree.left==null? binaryTree.value:getSmallestValue(binaryTree.left);
}