Thread: Delete root node in Binary Search Tree

Hi everyone,

I'm learning data structure and this is the example code from the textbook.

package lab7.part2;
 
public class BinarySearchTree_Pham {
    TreeNode root;
 
    public BinarySearchTree_Pham() {
        root = null;
    }
 
    public boolean insert(Student_Pham newStudent) {
        TreeNodeWrapper p = new TreeNodeWrapper();
        TreeNodeWrapper c = new TreeNodeWrapper();
        TreeNode n = new TreeNode();
        if(n == null)
            return false;
        else {
            n.node = newStudent.deepCopy();
            n.lc = null;
            n.rc = null;
            if(root == null) {
                root = n;
            }
            else {
                findNode(newStudent.getId(), p, c);
                if(newStudent.getId().compareTo(p.get().node.getId()) < 0)
                    p.get().lc = n;
                else
                    p.get().rc = n;
            }
            return true;
        }
    } //end insert
 
    public Student_Pham fetch(String id) {
        boolean found;
        TreeNodeWrapper p = new TreeNodeWrapper();
        TreeNodeWrapper c = new TreeNodeWrapper();
        found = findNode(id, p, c);
        if (found == true)
            return c.get().node.deepCopy();
        else
            return null;
    } //end fetch
 
    public boolean delete(String id) {
        boolean found;
        TreeNodeWrapper p = new TreeNodeWrapper();
        TreeNodeWrapper c = new TreeNodeWrapper();
        TreeNode largest;
        TreeNode nextLargest;
        found = findNode(id, p, c);
        if(found == false)
            return false;
        else {
            if(c.get().lc == null && c.get().rc == null) {
                if (p.get().lc == c.get())
                    p.get().lc = null;
                else
                    p.get().rc = null;
            } //end case 1
            else if (c.get().lc == null || c.get().rc == null) {
                if (p.get().lc == c.get()) {
                    if (c.get().lc != null)
                        p.get().lc = c.get().lc;
                    else
                        p.get().lc = c.get().rc;
                }
                else {
                    if (c.get().lc != null)
                        p.get().rc = c.get().lc;
                    else
                        p.get().rc = c.get().rc;
                }
            } // end case 2
            else {
                nextLargest = c.get().lc;
                largest = nextLargest.rc;
                if (largest != null) {
                    while (largest.rc != null) {
                        nextLargest = largest;
                        largest = largest.rc;
                    }
                    c.get().node = largest.node;
                    nextLargest.rc = largest.lc;
                }
                else {
                    nextLargest.rc = c.get().rc;
                    if (p.get().lc == c.get())
                        p.get().lc =nextLargest;
                    else
                        p.get().rc = nextLargest;
                }
            } // end case 3
            return true;
        }
    } // end of delete
 
    public boolean update(String id, Student_Pham newStudent) {
        if(delete(id) == false)
            return false;
        else if (insert(newStudent) == false)
            return false;
        return true;
    } // end update
 
    public void showAll() {
        if (root == null)
            System.out.println("Structure is empty.");
        else
            LNRoutputTraversal(root);
    } //end showAll
 
    private void LNRoutputTraversal(TreeNode root) {
        if (root.lc != null)
            LNRoutputTraversal(root.lc);
        System.out.println(root.node);
        if (root.rc != null)
            LNRoutputTraversal(root.rc);
    }
 
    public class TreeNode {
        private Student_Pham node;
        private TreeNode lc;
        private TreeNode rc;
        public TreeNode() {}
    }
 
    private boolean findNode(String targetKey, TreeNodeWrapper parent, TreeNodeWrapper child) {
        parent.set(root);
        child.set(root);
        if (root == null)
            return true;
        while (child.get() != null) {
            if(child.get().node.getId().compareTo(targetKey) == 0)
                return true;
            else {
                parent.set(child.get());
                if(targetKey.compareTo(child.get().node.getId()) < 0)
                    child.set(child.get().lc);
                else
                    child.set(child.get().rc);
            }
        } //end while
        return false;
    }
 
    public class TreeNodeWrapper {
        TreeNode treeRef = null;
        public TreeNodeWrapper() {}
        public TreeNode get() {return treeRef;}
        public void set(TreeNode t) {treeRef = t;}
    }
}

It cannot handle deleting root node in the tree and my task is to modify it to make it delete root node. Can anyone help me?

Thank you