0

I am working on Binary Search Tree for the first time and trying to remove a node from the Binary Search Tree.

However, everytime I remove it and then I use inOrder() or preOrder() to check if it's removed or not, it still shows up, which means I fail to remove that particular node.

This is my code:

public class BinaryTree<T extends Comparable<T>> {
    TreeNode<T> root;
    ArrayList<Integer> myArr = new ArrayList<Integer>();
    Random random;
}

public void add(T o) {
    if (root == null) {
        root = new TreeNode<T>(o);
    } else {
        root.insert(o);
    }
}

public TreeNode<T> deleteNode(TreeNode<T> root, int value) {
    if (root == null)
        return null;
    if (root.data > value) {
        root.left = deleteNode(root.left, value);
    } else if (root.data < value) {
        root.right = deleteNode(root.right, value);
    } else {
        // if nodeToBeDeleted have both children
        if (root.left != null && root.right != null) {
            TreeNode<T> temp = root;
            // Finding minimum element from right
            TreeNode<T> minNodeForRight = minimumElement(temp.right);
            // Replacing current node with minimum node from right subtree
            root.data = minNodeForRight.data;
            // Deleting minimum node from right now
            deleteNode(root.right, minNodeForRight.data);
        }
        // if nodeToBeDeleted has only left child
        else if (root.left != null) {
            root = root.left;
        }
        // if nodeToBeDeleted has only right child
        else if (root.right != null) {
            root = root.right;
        }
        // if nodeToBeDeleted do not have child (Leaf node)
        else
            root = null;
    }
    return root;
}

public TreeNode<T> minimumElement(TreeNode<T> root) {
    if (root.left == null){
        return root;
    } else {
        return minimumElement(root.left);
    }
}

public static void main(String[] args){
    BinaryTree<Integer> bst = new BinaryTree<Integer>();
    bst.add(20);
    bst.add(30);
    bst.add(40);
    bst.add(80);
    bst.add(1200);
    bst.inOrder();
    bst.deleteNode(bst.root, 80);
    bst.inOrder();
}

How to solve this problem?

1 Answer 1

1

Change following line

// Deleting minimum node from right now
deleteNode(root.right, minNodeForRight.data);

To

// Deleting minimum node from right now
root.right = deleteNode(root.right, minNodeForRight.data);
Sign up to request clarification or add additional context in comments.

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.