Deleting Node from BST

Question

I think I got most of the cases to work except for case 2 (deletion node has only one subtree). My test case is the tree below without the 1, 2, 3 and 4 nodes:

This program is telling me that 6 was deleted from the tree but when I try printing the tree, it still shows that 6 is in the tree.

public class RandomNode {

static int size;

public static class Node {

    int data;
    Node left;
    Node right;

    public Node(int data) {

        this.data = data;
        left = null;
        right = null;
        size++;
    }

}

// delete node in right subtree
public Node delete(Node root, int data) {
    // base case - if tree is empty
    if (root == null)
        return root;

    // search for deletion node 
    else if (data < root.data)
        root.left = delete(root.left, data);
    else if (data > root.data) {
        root.right = delete(root.right, data);

    } else {

        // case 1: deletion node has no subtrees
        if (root.left == null && root.right == null) {
            root = null;
            size--;
            System.out.println(data + " successfully deleted from tree (case1)");

            // case 2: deletion node has only one subtree
        } else if (root.left != null && root.right == null) {
            root = root.left;
            size--;
            System.out.println(data + " successfully deleted from tree (case2a)");
        } else if (root.left == null && root.right != null) {
            root = root.left;
            size--;
            System.out.println(data + " successfully deleted from tree (case2b)");

            // case 3: deletion node has two subtrees
            // *find min value in right subtree
            // *replace deletion node with min value
            // *remove the min value from right subtree or else there'll be
            // a duplicate
        } else if (root.left != null && root.right != null) {

            Node temp;
            if (root.right.right == null && root.right.left == null)
                temp = findMinNode(root.left);
            else
                temp = findMinNode(root.right);

            System.out.println(root.data + " replaced with " + temp.data);
            root.data = temp.data;

            if (root.right.right == null || root.left.left == null)
                root.left = delete(root.left, root.data);
            else
                root.right = delete(root.right, root.data);

            size--;
            System.out.println(temp.data + " succesfuly deleted from tree (case3)");

        }
    }

    return root;

}

// find min value in tree
public Node findMinNode(Node root) {

    while (root.left != null)
        root = root.left;
    System.out.println("min value: " + root.data);
    return root;

}

public void preOrderTraversal(Node root) {

    if (root == null)
        return;

    preOrderTraversal(root.left);
    System.out.println(root.data);
    preOrderTraversal(root.right);

}

public static void main(String[] args) {

    RandomNode r = new RandomNode();

    Node root = new Node(6);
    //root.left = new Node(2);
    root.right = new Node(9);
    //root.left.left = new Node(1);
    //root.left.right = new Node(5);
    //root.left.right.left = new Node(4);
    //root.left.right.left.left = new Node(3);
    root.right.left = new Node(8);
    root.right.right = new Node(13);
    root.right.left.left = new Node(7);
    root.right.right.left = new Node(11);
    root.right.right.right = new Node(18);

    r.delete(root, 6);
    r.preOrderTraversal(root);

}

}

Answer 1

It's rather hard for me to follow since I'd write it functionally.
However,

if (root.right.right == null || root.left.left == null)
    root.left = delete(root.left, root.data);
else
    root.right = delete(root.right, root.data);

Is probably wrong, since it should mirror your earlier findMinNode() calls, and thus should probably be

if(root.right.right == null && root.right.left == null)
    root.left = delete(root.left, root.data);

There is more wrong when debugging it.

First off, java is pass by value, so if you're deleting the top node (root), your pointer should be updated too. Hence, the call should be root = r.delete(root, 6);

Second, there's another bug. Case 2a assigns root to root.left... which is null. It should be root.right.

Having made those changes, the output then becomes:

6 successfully deleted from tree (case2b)
7
8
9
11
13
18

Answer 2

When you do root = root.left; and size --, you must also make root.left = null.

Here you are simply making root as root.left but are not making root.left as null.