Написание метода Backtrack для нового класса, реализующего дерево двоичного поиска

Question

Я пытаюсь реализовать метод возврата в новом классе с именем BacktrackingBST, который состоит из узла root дерева двоичного поиска и стека. стек используется для хранения вставленных или удаленных узлов из дерева, чтобы позволить нам вернуться к указанным методам. Я столкнулся с проблемой при попытке возврата к удалению, проблема заключалась в том, что в то время как я должен был восстановить удаленный узел обратно в его первоначальное место, мне не удалось найти решение о том, как вернуть новый узел на его место, как его первоначальное место

    BacktrackingBST.Node root = null;
    private Stack stack;
    private Stack redoStack;

    // Do not change the constructor's signature
    public BacktrackingBST(Stack stack, Stack redoStack) {
        this.stack = stack;
        this.redoStack = redoStack;
    }

    public Node getRoot() {
        return root;
    }

    public Node searchNode(BacktrackingBST.Node node, int key) {
        if (node == null || node.key == key)
            return node;
        if (node.key > key)
            return searchNode(node.left, key);
        return searchNode(node.right, key);
    }
        public Node search(int x) {
            return searchNode(root,x);
    }

    public void insert(BacktrackingBST.Node z) {
        if (search(z.getKey()) == null) {
            Node zParent = null;
            var zPlacement = root;
            while (zPlacement != null) {
                zParent = zPlacement;
                if (z.getKey() < zPlacement.getKey())
                    zPlacement = zPlacement.left;
                else
                    zPlacement = zPlacement.right;
            }
            z.parent = zParent;
            if (zParent == null)
                root = z;
            else if (z.getKey() < zParent.getKey())
                zParent.left = z;
            else
                zParent.right = z;
            stack.push(z);
        }
    }
    public void delete(Node x) {
        if(search(x.getKey())!=null){
            stack.push(x);
            if(x.left==null&&x.right==null)
                if(x.parent.getKey()>x.getKey())
                    x.parent.left=null;
                else
                    x.parent.right=null;
            else
            if(x.left==null)
                if(x.parent.getKey()>x.getKey())
                    x.parent.left=x.right;
                else
                    x.parent.right=x.right;
            else
            if(x.right==null)
                if(x.parent.getKey()>x.getKey())
                    x.parent.left=x.left;
                else
                    x.parent.right=x.left;
            else{
                Node suc=successor(x);
                delete(suc);
                stack.pop();
                x.value= suc.getValue();
                x.key = suc.getKey();
            }
        }

    }
    public Node minimumNode(Node z){
        if(z.left != null){
            return minimumNode(z.left);
        }
        return z;
    } public Node maximumNode(Node z){
        if(z.right != null){
            return minimumNode(z.right);
        }
        return z;
    }
    public Node minimum() {
        return minimumNode(root);
    }

    public Node maximum() {
        return maximumNode(root);
    }
    public Node successor(Node x) {
        if (x.right != null) {
            return minimumNode(x.right);
        }
        var parent = x.parent;
        while (parent != null && x == parent.right) {
            x = parent;
            parent = parent.parent;
        }
        return parent;
    }

    public Node predecessor(Node x) {
        if (x.left != null) {
            return maximumNode(x.left);
        }
        var parent = x.parent;
        while (parent != null && x == parent.left) {
            x = parent;
            parent = parent.parent;
        }
        return parent;
    }

    @Override
    public void backtrack() {
        if(!stack.isEmpty()){
        Node pop = (Node) stack.pop();
        if (search(pop.getKey()) == null) {
            search(pop.parent.getKey());


          }
        }
    }

    @Override
    public void print() {
        if (root == null)
            return;
        while(root.left != null){
            root = root.left;
        }while(root.right != null){

        }

        System.out.print(root.key + " ");
    }

    public static class Node {
        public BacktrackingBST.Node left;
        public BacktrackingBST.Node right;

        private BacktrackingBST.Node parent;
        private int key;
        private Object value;

        public Node(int key, Object value) {
            this.key = key;
            this.value = value;
        }

        public int getKey() {
            return key;
        }

        public Object getValue() {
            return value;
        }
    }

}```