Home > Back-end >  Why do we need the first if statement to remove a node from a binary search tree?
Why do we need the first if statement to remove a node from a binary search tree?

Time:09-16

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);
}

CodePudding user response:

When you try to remove a value from the binary search tree, there are three possibilities.

  1. the value is not in the tree
  2. the value is less than the value of the node
  3. the value is greater than the value of the node
  4. the value is equal to the value of the node

The first if statement is for handling case 1.

CodePudding user response:

The if statement is try only when the "binaryTree" is null. Then we are returning the "binaryTree" (Which is null). So we are actually returing null. You can return null too.

  • Related