Question

Write methods contains and remove for the BinarySearchTree class. Use methods find and delete to do the work

Answer 1

Code :
class Node
{
    public int data;
    public Node left;
    public Node right;
    public Node parent;

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

class BinarySearchTree
{
    public Node root;

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

    public Node minimum(Node x)
    {
        while(x.left != null)
            x = x.left;
        return x;
    }

    public void insert(Node n)
    {
        Node y = null;
        Node temp = this.root;
        while(temp != null)
        {
            y = temp;
            if(n.data < temp.data)
                temp = temp.left;
            else
                temp = temp.right;
        }
        n.parent = y;

        if(y == null) //newly added node is root
            this.root = n;
        else if(n.data < y.data)
            y.left = n;
        else
            y.right = n;
    }

    public void transplant(Node u, Node v)
    {
        if(u.parent == null) //u is root
            this.root = v;
        else if(u == u.parent.left) //u is left child
            u.parent.left = v;
        else //u is right child
            u.parent.right = v;

        if(v != null)
            v.parent = u.parent;
    }

    public void delete(Node z)
    {
        if(z.left == null)
        {
            transplant(z, z.right);
        }
        else if(z.right == null)
        {
            transplant(z, z.left);
        }
        else
            {
                Node y = minimum(z.right); //minimum element in right subtree
                if(y.parent != z) {
                    transplant(y, y.right);
                    y.right = z.right;
                    y.right.parent = y;
            }
            transplant(z, y);
            y.left = z.left;
            y.left.parent = y;
        }
    }

    public void inorder(Node n)
    {
        if(n != null)
        {
            inorder(n.left);
            System.out.println(n.data);
            inorder(n.right);
        }
    }
    public static boolean searchRecursively(Node root, int value) {


        if (root == null)
            return false;


        if ((int) root.data == value)
            return true;

        if (value < (int) root.data)
            return searchRecursively(root.left, value);

        else if (value > (int) root.data)
            return searchRecursively(root.right, value);


        return false;
    }
    public static void main(String[] args)
    {
        BinarySearchTree t = new BinarySearchTree();

        Node a, b, c, d, e, f, g, h, i, j, k, l, m;
        a = new Node(1);
        b = new Node(2);
        c = new Node(3);
        d = new Node(10);
        e = new Node(9);
        f = new Node(4);
        g = new Node(59);
        h = new Node(6);
        i = new Node(790);
        j = new Node(800);

        System.out.println("After insert");
        t.insert(a);
        t.insert(b);
        t.insert(c);
        t.insert(d);
        t.insert(e);
        t.insert(f);
        t.insert(g);
        t.insert(h);
        t.insert(i);
        t.insert(j);

        t.inorder(t.root);
        System.out.println("--------------------------------------------------------------");
        System.out.println("After Delete");

        t.delete(a);
        t.delete(e);

        t.inorder(t.root);
        System.out.println("--------------------------------------------------------------");
        System.out.println("Search element ");


        System.out.println("Search Value 503 is in tree? " + searchRecursively(t.root, 503));
        System.out.println("Search Value 4 in tree? " + searchRecursively(t.root, 4));
        System.out.println("Search Value 6 in tree? " + searchRecursively(t.root, 6));
        System.out.println("Search Value 401 in tree? " + searchRecursively(t.root, 401));
    }
}

output:

After insert
1
2
3
4
6
9
10
59
790
800
-------------------------------------------------------------------------
After Delete
2
3
4
6
10
59
790
800
-------------------------------------------------------------------------
Search element
Search Value 503 is in tree? false
Search Value 4 in tree? true
Search Value 6 in tree? true
Search Value 401 in tree? false

output(SS):

Explain:

Binary Search Tree is a special kind of binary tree in which the values of all the nodes of the left subtree of any node of the tree are smaller than the value of the node. Also, the values of all the nodes of the right subtree of any node are greater than the value of the node.