Binary Search Tree not deleting Node

Question

I have created a Binary Search Tree and am trying to delete specific nodes after adding them. I can successfully delete about 5 Nodes but when I try to delete a Node with id 109 it just ignores it and nothing happens. I have tried many methods to delete it and it just does not work.

myBinaryTree.deleteNode(myBinaryTree.root, 109);

Here is the delete method in my Binary Tree.

public Node deleteNode(Node root, int ID){

    if (root == null)  return root;
    if (ID < root.ID)
        root.leftChild = deleteNode(root.leftChild, ID);
    else if (ID > root.ID)
        root.rightChild = deleteNode(root.rightChild, ID);

    else
    {
        if (root.leftChild == null)
            return root.rightChild;
        else if (root.rightChild == null)
            return root.leftChild;

        root.ID = minValue(root.rightChild);
        root.rightChild = deleteNode(root.rightChild, root.ID);
    }

    return root;
}


int minValue(Node root)
{
    int minv = root.ID;
    while (root.leftChild != null)
    {
        minv = root.leftChild.ID;
        root = root.leftChild;
    }
    return minv;
}

And my Node:

public class Node {
    int ID;
    Dancer.Gender gender;
    int height;

    Node leftChild;
    Node rightChild;

    Node(int ID, Dancer.Gender gender, int height) {

        this.ID = ID;
        this.gender = gender;
        this.height = ID;

    }

    public int getID() {
        return ID;
    }

    public void setID(int ID) {
        this.ID = ID;
    }

}

The ID works as intended meaning the method deleteNode gets correct ID, it just does not delete it.

Here is a picture of a the tree I am trying to delete from:

If more information on how I add the nodes etc is needed then I can provide that aswell. It is just so wierd that it all works perfectly until I try to delete node with ID = 109.

Answer 1

Your code looks fine.

By the way, how did you verify that the node was not deleted ? I just checked your code and printed inorder traversal. And it works fine.

// This is java code.
void inorder(Node root){
    if (root ==null)return;
    inorder(root.leftChild);
    System.out.print(root.ID + "  ");
    inorder(root.rightChild);
}

// verify deletion by printing inorder traversal before and after
public static void main(String[] args) {
    // creating the tree
    Node root = new Node(60);
    root.leftChild = new Node(40);
    root.rightChild = new Node(109);
    root.leftChild.leftChild = new Node(20);
    root.leftChild.rightChild = new Node(49);

    inorder(root); // Printing before deleting
    System.out.println();
    myBinaryTree.root = deleteNode(myBinaryTree.root, 109); // delete the node and collect the new reference of the root.
    inorder(root); // Printing after tree
    System.out.println();
}