Question

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;
}
}

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;
    }
}