The title is very self explanatory.

I’m curious about how to delete a Node in an AVL Tree.

The only condition is (that’s also what makes other resources in the internet uselesss), the delete function should take the Node to delete directly as a parameter rather than the key of the Node and replacing the key.

I tried to use my functon that I created for a BST for this usecase. But unfortunately, it didn’t work and I wasn’t able to delete the root.

This is my BST code. I added balance tree at the return of the deleteRoot. But it still doesn’t work.

public void delete(TreeNode x) {
        // Function to delete the Node (x) in the BST
        if (root != null) {  // If it's not an empty tree
            if (root == x) {  // If the Node is the root
                root = deleteRoot(root);  // Directly call the deleteRoot function
            } else {
                deleter(root, x);  // If it's not the root, pass to the deleter
            }
        }
    }

    public void deleter(TreeNode parent, TreeNode target) {
        // Recursive delete function to reach the Node we'd like to delete and call the deleteRoot method
        if (parent.getLeft() != null && target.getKey() < parent.getKey()) {  // If left is not empty and target Node is less than the current parent
            if (target.getKey() == parent.getLeft().getKey()) {  // If the left Node is our target
                parent.setLeft(deleteRoot(parent.getLeft()));  // Call the deleteRoot on the left child of the parent and set the new root to the left child of the parent
            } else {
                deleter(parent.getLeft(), target);  // If we don't have a match, proceed further in the BST
            }
        } else if (parent.getRight() != null && target.getKey() > parent.getKey()) {  // If right is not empty and target Node is more than the current parent
            if (target.getKey() == parent.getRight().getKey()) { // Applying the same procedures but for the right side
                parent.setRight(deleteRoot(parent.getRight()));
            } else {
                deleter(parent.getRight(), target);
            }
        }
    }

    private TreeNode deleteRoot(TreeNode x) {
        // Function to delete the Node in a BST that is the root of the tree
        if (x.getLeft() == null) {
            // If the Node we want to delete is a Node with only one right child (This case also catches Nodes with no child)
            TreeNode temp = x;  // Saving the Node in a temp variable
            x = x.getRight();  // Setting it into its right child
            temp.setRight(null);  // Disconnecting the Node we'd like to delete
            return x;
        } else if (x.getRight() == null) {
            // If the Node we want to delete is a Node with only one left child, we apply the same procedure as before but with the left side
            TreeNode temp = x;
            x = x.getLeft();
            temp.setLeft(null);
            return x;
        } else {
            // If the Node we want to delete is a Node with a child on both sides
            TreeNode temp = getSuccessor(x.getRight());  // Finding the successor
            delete(temp);  // Removing the successor from the tree
            temp.setRight(x.getRight());  // Inserting the successor into the place of the Node we'd like to delete
            temp.setLeft(x.getLeft());
            x.setLeft(null);  // Disconnecting the Node we'd like to delete
            x.setRight(null);
            return temp;
        }
    }

    private TreeNode getSuccessor(TreeNode x) {
        // Function to find the successor of a Node
        while (x.getLeft() != null) {  // While the left side is not null
            x = x.getLeft();
        }
        return x;
    }