Please show how to do the code step by step in detail with comments. The solutio

Question

Please show how to do the code step by step in detail with comments. The solution needs to be in recursion. See the given code for this project.

Implement the BinarySearchTree class. The BinarySearchTree class extends the BinaryTree class which implements the Tree interface. Your assignment is to implement all of the abstract methods of the BinaryTree class recursively.

They are:
Insert
Iterator (non-recursive)
Remove
Search

You must also implement an Iterator inner class for the BinarySearchTree class. You must submit a modified BinarySearchTree.java file with your source code. Do not submit and do not modify or change the Tree.java or BinaryTree.java files.

Explanation / Answer

class BinarySearchTree<E extends Comparable<? super E>> extends BinaryTree<E> {

    //This method new Generic Node

     public Node<E> createNewNode(E data)
     {
        return new Node<E>(data);
     }
   //Method to insert node in BST
    public void insert(E data) {
        if(root==null)// Check if root is null i.e. no element in tree
            root=createNewNode(data);// Create a root node
        else
        {
          // find the parent node
        Node<E> parent = null;
        Node<E> current = root;
        while (current != null)
            {
                if (data.compareTo(current.data) < 0) // if current node's data is greater than data passed then move to //left subtree
                {
                parent = current;
                current = current.left;
                }
                else if (data.compareTo(current.data) > 0)// else move to right sub tree
                {
                    parent = current;
                    current = current.right;
                }
                else
                   return;//Duplicate node not inserted
            }
    // Create the new node and attach it to the parent node i.e. inserting node to the leaf level
        if (data.compareTo(parent.data) < 0)
            parent.left = createNewNode(data);
        else
            parent.right = createNewNode(data);
        }
       
    }
  

    public Iterator<E> iterator() {
        return new InorderIterator();
    }
    // Inner class InorderIterator
    class InorderIterator implements Iterator<E>{
        // Store the elements in a list
       private ArrayList<E> list = new ArrayList<E>();
       private int current = 0;// Point to the current element in list
      
       public InorderIterator(){
           inorder();// Traverse binary tree and store elements in list
       }
       //Inorder traversal from the root
       public void inorder(){
           inorder(root);
       }
       // Inorder traversal from a subtree
       public void inorder(Node<E> root){
           if(root==null)return;
           inorder(root.left);
           list.add(root.data);
           inorder(root.right);
       }
      
      
        // The overriden method which indicates is there any next element available for traversing
       @Override
       public boolean hasNext() {
           if(current<list.size())
               return true;
           return false;
       }
        // Get the current element and move cursor to the next
       @Override
       public E next() {
           return(list.get(current));
       }

      
      
   }

    public void remove(E key) {
      
            // Locate the node to be deleted and also locate its parent node
    Node<E> parent = null;
    Node<E> current = root;
    while (current != null)
    {
        if (key.compareTo(current.data) < 0)
        {
            parent = current;
            current = current.left;
        }
        else if (key.compareTo(current.data) > 0)
        {
        parent = current;
        current = current.right;
        }
        else
            break; // Element is in the tree pointed by current
    }

    if (current == null)
        return; // Element is not in the tree

// Case 1: current has no left children
    if (current.left == null)
    {
    // Connect the parent with the right child of the current node
        if (parent == null)
        {
            root = current.right;
        }
        else
        {
            if (key.compareTo(parent.data) < 0)
                parent.left = current.right;
            else
                parent.right = current.right;
        }
    }
else
{
    // Case 2: The current node has a left child
    // Locate the rightmost node in the left subtree of
    // the current node and also its parent
    Node<E> parentOfRightMost = current;
    Node<E> rightMost = current.left;

    while (rightMost.right != null)
    {
        parentOfRightMost = rightMost;
        rightMost = rightMost.right; // Keep going to the right
    }

// Replace the element in current by the element in rightMost
    current.data = rightMost.data;

// Eliminate rightmost node
    if (parentOfRightMost.right == rightMost)
        parentOfRightMost.right = rightMost.left;
    else
// Special case: parentOfRightMost == current
    parentOfRightMost.left = rightMost.left;
}
}

    public boolean search(E key) {
        Node<E> current = root; // Start from the root

        while (current != null)
        {
            if (key.compareTo(current.data) < 0)
            {
                current = current.left;
            }
        else if (key.compareTo(current.data) > 0)
            {
                current = current.right;
            }
        else // element matches current.element
            return true; // Element is found
        }

        return false;

}
}

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.