Question

Here is a modification of the BST program that includes a recursive find method: BinarySearchTree2C.java (posted...

Here is a modification of the BST program that includes a recursive find method:

BinarySearchTree2C.java (posted below)

Implement the following methods using recursion:

int depth() // returns the length of the deepest path from root to any leaf

int node_count() // returns the number of nodes in the tree

void insert(int n) // inserts value n into the tree

BinarySearchTree2C clone() // returns a clone (deep copy) of the tree

Add code to the main method to test these methods.

CODE:

//====================================================
public class BinarySearchTree2C
{
private Node root;
public BinarySearchTree2C(){
this.root = null;
}
//====================================================
public boolean find(int id)
{
Node current = root;
while(current!=null){
if(current.data==id){
return true;
}else if(current.data>id){
current = current.left;
}else{
current = current.right;
}
}
return false;
}
//====================================================
public boolean find2(int id)
{
return find2(id, root);
}
private boolean find2(int id, Node n)
{
if (n == null) return false;
if (n.data == id) return true;
if (id < n.data) return find2(id, n.left);
return find2(id, n.right);
}
//====================================================
public boolean delete(int id)
{
Node parent = root;
Node current = root;
boolean isLeftChild = false;
while(current.data!=id){
parent = current;
if(current.data>id){
isLeftChild = true;
current = current.left;
}else{
isLeftChild = false;
current = current.right;
}
if(current ==null){
return false;
}
}
//if i am here that means we have found the node
//Case 1: if node to be deleted has no children
if(current.left==null && current.right==null){
if(current==root){
root = null;
}
if(isLeftChild ==true){
parent.left = null;
}else{
parent.right = null;
}
}
//Case 2 : if node to be deleted has only one child
else if(current.right==null){
if(current==root){
root = current.left;
}else if(isLeftChild){
parent.left = current.left;
}else{
parent.right = current.left;
}
}
else if(current.left==null){
if(current==root){
root = current.right;
}else if(isLeftChild){
parent.left = current.right;
}else{
parent.right = current.right;
}
}else if(current.left!=null && current.right!=null){

//now we have found the minimum element in the right sub tree
Node successor = getSuccessor(current);
if(current==root){
root = successor;
}else if(isLeftChild){
parent.left = successor;
}else{
parent.right = successor;
}   
successor.left = current.left;
}
return true;
}
//====================================================
public Node getSuccessor(Node deleleNode)
{
Node successsor =null;
Node successsorParent =null;
Node current = deleleNode.right;
while(current!=null){
successsorParent = successsor;
successsor = current;
current = current.left;
}
//check if successor has the right child, it cannot have left child for sure
// if it does have the right child, add it to the left of successorParent.
// successsorParent
if(successsor!=deleleNode.right){
successsorParent.left = successsor.right;
successsor.right = deleleNode.right;
}
return successsor;
}
//====================================================
public void insert(int id)
{
Node newNode = new Node(id);
if(root==null){
root = newNode;
return;
}
Node current = root;
Node parent = null;
while(true){
parent = current;
if(id<current.data){
current = current.left;
if(current==null){
parent.left = newNode;
return;
}
}else{
current = current.right;
if(current==null){
parent.right = newNode;
return;
}
}
}
}
//====================================================
private void display(Node root)
{
if(root!=null)
{
display(root.left);
System.out.print(" " + root.data);
display(root.right);
}
}
public void display(){
display(root);
System.out.println();
}
//====================================================
public static void main(String arg[])
{
BinarySearchTree2C b = new BinarySearchTree2C();
BinarySearchTree2C c = b;
b.insert(3);b.insert(8);
b.insert(1);b.insert(4);b.insert(6);b.insert(2);b.insert(10);b.insert(9);
b.insert(20);b.insert(25);b.insert(15);b.insert(16);
System.out.println("Original Tree b: ");
b.display();
System.out.println("Copy Tree c: ");
c.display();
System.out.println("");
System.out.println("Check whether Node with value 4 exists : " + b.find2(4));
System.out.println("Delete Node with no children (2) : " + b.delete(2));
b.display();
System.out.println("\n Delete Node with one child (4) : " + b.delete(4));
b.display();
System.out.println("\n Delete Node with Two children (10) : " + b.delete(10));
System.out.println("Original Tree b: ");
b.display();
System.out.println("Copy Tree c: ");
c.display();
}
}
//====================================================
class Node
{
int data;
Node left;
Node right;
public Node(int data)
{
this.data = data;
left = null;
right = null;
}
}

Homework Answers

Answer #1

Attached the code with the required methods. If you have any queries, feel free to talk.

Program Screenshot for Indentation Reference:

Sample Output:

Program code to copy:

public class BinarySearchTree2C {
    private Node root;

    public BinarySearchTree2C() {
        this.root = null;
    }

    // ====================================================
    public boolean find(int id) {
        Node current = root;
        while (current != null) {
            if (current.data == id) {
                return true;
            } else if (current.data > id) {
                current = current.left;
            } else {
                current = current.right;
            }
        }
        return false;
    }

    // ====================================================
    public boolean find2(int id) {
        return find2(id, root);
    }

    private boolean find2(int id, Node n) {
        if (n == null)
            return false;
        if (n.data == id)
            return true;
        if (id < n.data)
            return find2(id, n.left);
        return find2(id, n.right);
    }

    // ====================================================
    public boolean delete(int id) {
        Node parent = root;
        Node current = root;
        boolean isLeftChild = false;
        while (current.data != id) {
            parent = current;
            if (current.data > id) {
                isLeftChild = true;
                current = current.left;
            } else {
                isLeftChild = false;
                current = current.right;
            }
            if (current == null) {
                return false;
            }
        }
        // if i am here that means we have found the node
        // Case 1: if node to be deleted has no children
        if (current.left == null && current.right == null) {
            if (current == root) {
                root = null;
            }
            if (isLeftChild == true) {
                parent.left = null;
            } else {
                parent.right = null;
            }
        }
        // Case 2 : if node to be deleted has only one child
        else if (current.right == null) {
            if (current == root) {
                root = current.left;
            } else if (isLeftChild) {
                parent.left = current.left;
            } else {
                parent.right = current.left;
            }
        } else if (current.left == null) {
            if (current == root) {
                root = current.right;
            } else if (isLeftChild) {
                parent.left = current.right;
            } else {
                parent.right = current.right;
            }
        } else if (current.left != null && current.right != null) {

            // now we have found the minimum element in the right sub tree
            Node successor = getSuccessor(current);
            if (current == root) {
                root = successor;
            } else if (isLeftChild) {
                parent.left = successor;
            } else {
                parent.right = successor;
            }
            successor.left = current.left;
        }
        return true;
    }

    // ====================================================
    public Node getSuccessor(Node deleleNode) {
        Node successsor = null;
        Node successsorParent = null;
        Node current = deleleNode.right;
        while (current != null) {
            successsorParent = successsor;
            successsor = current;
            current = current.left;
        }
        // check if successor has the right child, it cannot have left child for sure
        // if it does have the right child, add it to the left of successorParent.
        // successsorParent
        if (successsor != deleleNode.right) {
            successsorParent.left = successsor.right;
            successsor.right = deleleNode.right;
        }
        return successsor;
    }

    // ====================================================
    public void insert(int id) {
        Node newNode = new Node(id);
        if (root == null) {
            root = newNode;
            return;
        }
        Node current = root;
        Node parent = null;
        while (true) {
            parent = current;
            if (id < current.data) {
                current = current.left;
                if (current == null) {
                    parent.left = newNode;
                    return;
                }
            } else {
                current = current.right;
                if (current == null) {
                    parent.right = newNode;
                    return;
                }
            }
        }
    }

    // ====================================================
    private void display(Node root) {
        if (root != null) {
            display(root.left);
            System.out.print(" " + root.data);
            display(root.right);
        }
    }

    public void display() {
        display(root);
        System.out.println();
    }

    // ====================================================
    public int depth() {
        // call recursize helper
        return depth(root);
    }

    private int depth(Node node) {
        // current NULL then return -1
        if (node == null) {
            return -1;
        }
        // return 1 + max of both left and right child
        return 1 + Math.max(depth(node.left), depth(node.right));
    }

    // ====================================================
    public int node_count() {
        // call recursive helper
        return node_count(root);
    }

    private int node_count(Node node) {
        // if null then return 0
        if (node == null) {
            return 0;
        }
        // else return 1 + count of both subtree
        return 1 + node_count(node.left) + node_count(node.right);
    }

    // ====================================================
    public void insert2(int n) {
        // call private recursive method
        root = insert2(root, n);
    }

    private Node insert2(Node node, int n) {
        // is current node is null then return a new Node
        if (node == null) {
            return new Node(n);
        }
        else if ( n > node.data ) {
            // add in right subtree
            node.right = insert2(node.right, n);
        }
        else {
            node.left = insert2(node.left, n);
        }
        // return current node
        return node;
    }

    // ====================================================
    public BinarySearchTree2C clone() {
        // create a binarty tree
        BinarySearchTree2C b = new BinarySearchTree2C();
        // call helper
        b.root = clone(root);
        return b;
    }

    private Node clone(Node source) {
        // if node is Null then return null
        if(source == null) {
            return null;
        }
        Node newNode = new Node(source.data);
        // allocate current node
        // call for left subtree
        newNode.left = clone(source.left);
        newNode.right = clone(source.right);
        // return newNode
        return newNode;
    }

    // ====================================================
    public static void main(String arg[]) {
        BinarySearchTree2C b = new BinarySearchTree2C();
        BinarySearchTree2C c = b;
        b.insert(3);
        b.insert(8);
        b.insert(1);
        b.insert(4);
        b.insert(6);
        b.insert(2);
        b.insert(10);
        b.insert(9);
        b.insert(20);
        b.insert(25);
        b.insert(15);
        b.insert(16);
        System.out.println("Original Tree b: ");
        b.display();
        System.out.println("Copy Tree c: ");
        c.display();
        System.out.println("");
        System.out.println("Check whether Node with value 4 exists : " + b.find2(4));
        System.out.println("Delete Node with no children (2) : " + b.delete(2));
        b.display();
        System.out.println("\n Delete Node with one child (4) : " + b.delete(4));
        b.display();
        System.out.println("\n Delete Node with Two children (10) : " + b.delete(10));
        System.out.println("Original Tree b: ");
        b.display();
        System.out.println("Copy Tree c: ");
        c.display();

        // insert in b
        b.insert2(30);
        // display
        System.out.println("Original Tree b: ");
        b.display();
        // get depth and node count
        System.out.println("\nDepth: " + b.depth());
        // print node_count
        System.out.println("Node Count: " + b.node_count());
        // make a clone
        BinarySearchTree2C d = b.clone();
        System.out.println("Clone Tree d: ");
        d.display();
    }
}

// ====================================================
class Node {
    int data;
    Node left;
    Node right;

    public Node(int data) {
        this.data = data;
        left = null;
        right = null;
    }
}

Know the answer?
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Not the answer you're looking for?
Ask your own homework help question
Similar Questions
Complete the redblacktree in Java. Add a public boolean isBlack field to the Node inner class....
Complete the redblacktree in Java. Add a public boolean isBlack field to the Node inner class. Make every Node object have a false isBlack field, all new node is red by default. In the end of the insert method, set the root node of your red black tree to be black. Implement the rotate() and recolor() functions, and create tests for them in a separate class. import java.util.LinkedList; public class BinarySearchTree<T extends Comparable<T>> { protected static class Node<T> { public...
The Binary Search Tree implementation for bst.zip. The code in the destructor of the BST class...
The Binary Search Tree implementation for bst.zip. The code in the destructor of the BST class is empty. Complete the destructor so the memory allocated for each node in the BST is freed. Make a couple of different trees in your main method or in a function to test the destructor (the program should not crash upon exiting). bst.zip (includes the following files below in c++): bst.h: #pragma once #include #include "node.cpp" using namespace std; template class BST { public:...
do a code trace on how a key gets deleted package interview; import java.util.*; public class...
do a code trace on how a key gets deleted package interview; import java.util.*; public class binarySearchTree { Node root; void insert(int key) { root = insertRec(root,key); } void delete(int key) { root = deleteRec(root,key); } Node insertRec(Node root, int key) { if(root == null) { root = new Node(key); return root; } if(key < root.key) { root.leftChild = insertRec(root.leftChild,key); } else if(key > root.key){ root.rightChild = insertRec(root.rightChild,key); } return root; } Node deleteRec(Node root, int key) { if(root ==...
Java Program: You will be traversing through an integer tree to print the data. Given main(),...
Java Program: You will be traversing through an integer tree to print the data. Given main(), write the methods in the 'IntegerBinaryTree' class specified by the // TODO: sections. There are 6 methods in all to write. Ex: If the input is: 70 86 60 90 49 62 81 85 38 -1 the output should be: Enter whole numbers to insert into the tree, -1 to stop Inorder: 38 - 49 - 60 - 62 - 70 - 81 -...
In this lab, you will write a program that creates a binary search tree based on...
In this lab, you will write a program that creates a binary search tree based on user input. Then, the user will indicate what order to print the values in. **Please write in C code** Start with the bst.h and bst.c base code provided to you. You will need to modify the source and header file to complete this lab. bst.h: #ifndef BST_H #define BST_H typedef struct BSTNode { int value; struct BSTNode* left; struct BSTNode* right; } BSTNode; BSTNode*...
c++ data structures linked list delete node bool deleteNode(int); pass this method an id to delete....
c++ data structures linked list delete node bool deleteNode(int); pass this method an id to delete. Return true or false to indicate success or failure. Delete the memory the node was using The algorithm for deleting a Node to a Linked List (general case): ● Begin at the head. ● Compare the id to the current node. ● If search id > current id, stop. ● Detach the current Node ○ current->previous->next = current->next ○ current->next->previous = current->previous ● Deallocate...
Question: I get a Segmentation fault error sometimes when I addElementBack or print. Am I using...
Question: I get a Segmentation fault error sometimes when I addElementBack or print. Am I using pointers correctly and deleting memory properly? #ifndef DYNAMICARRAY_H #define DYNAMICARRAY_H #include <cstdlib> #include <iostream> using namespace std; // Node class class Node { int data; Node* next; Node* prev; public: Node(); Node(int); void SetData(int newData) { data = newData; }; void SetNext(Node* newNext) { next = newNext; }; void SetPrev(Node* newPrev) { prev = newPrev; }; int getData() { return data; }; Node* getNext()...
You will be traversing through an integer tree to print the data. Given main(), write the...
You will be traversing through an integer tree to print the data. Given main(), write the methods in the 'IntegerBinaryTree' class specified by the // TODO: sections. There are 6 methods in all to write. Ex: If the input is 70 86 60 90 49 62 81 85 38 -1 the output should be: Enter whole numbers to insert into the tree, -1 to stop Inorder: 38 - 49 - 60 - 62 - 70 - 81 - 85 -...
Java Language Add a method (convertToRing ()) that converts the list to a circular. This is,...
Java Language Add a method (convertToRing ()) that converts the list to a circular. This is, which makes the last node instead of pointing to null point to the first. Code: class Node { int value; Node nextNode; Node(int v, Node n) { value = v; nextNode = n; } Node (int v) { this(v,null); } } class LinkedList { Node head; //head = null; LinkedList() { } int length() { Node tempPtr; int result = 0; tempPtr = head;...
Java Language Add a method (convertToRing ()) that converts the list to a circular. This is,...
Java Language Add a method (convertToRing ()) that converts the list to a circular. This is, which makes the last node instead of pointing to null point to the first. Code: class Node { int value; Node nextNode; Node(int v, Node n) { value = v; nextNode = n; } Node (int v) { this(v,null); } } class LinkedList { Node head; //head = null; LinkedList() { } int length() { Node tempPtr; int result = 0; tempPtr = head;...
ADVERTISEMENT
Need Online Homework Help?

Get Answers For Free
Most questions answered within 1 hours.

Ask a Question
ADVERTISEMENT