bst deletion

1/* This is just the deletion function you need to write the required code.
2	Thank you. */
3
4void deleteNode(Node *root, int data)
5{
6    if(root == NULL)
7    {
8        cout << "Tree is empty\n";
9        return;
10    }
11
12    queue<Node*> q;
13    q.push(root);
14
15    while(!q.empty())
16    {
17        Node *temp = q.front();
18        q.pop();
19
20        if(temp->data == data)
21        {
22            Node *current = root;
23            Node *prev;
24
25            while(current->right != NULL)
26            {
27                prev = current;
28                current = current->right;
29            }
30
31            temp->data = current->data;
32            prev->right = NULL;
33            free(current);
34
35            cout << "Deleted\n";
36
37            return;
38        }
39
40        if(temp->left != NULL)
41            q.push(temp->left);
42        if(temp->right != NULL)
43            q.push(temp->right);
44    }
45
46    cout << "Node not found for deletion\n";
47}

1public class BinarySearchTree {
2    public static class Node {
3        //instance variable of Node class
4        public int data;
5        public Node left;
6        public Node right;
7
8        //constructor
9        public Node(int data) {
10            this.data = data;
11            this.left = null;
12            this.right = null;
13        }
14    }
15
16    // instance variable
17    public Node root;
18
19    // constructor for initialise the root to null BYDEFAULT
20    public BinarySearchTree() {
21        this.root = null;
22    }
23
24    // insert method to insert the new Date
25    public void insert(int newData) {
26        this.root = insert(root, newData);
27    }
28
29    public Node insert(Node root, int newData) {
30        // Base Case: root is null or not
31        if (root == null) {
32            // Insert the new data, if root is null.
33            root = new Node(newData);
34            // return the current root to his sub tree
35            return root;
36        }
37        // Here checking for root data is greater or equal to newData or not
38        else if (root.data >= newData) {
39            // if current root data is greater than the new data then now process the left sub-tree
40            root.left = insert(root.left, newData);
41        } else {
42            // if current root data is less than the new data then now process the right sub-tree
43            root.right = insert(root.right, newData);
44        }
45        return root;
46    }
47
48    /*
49     * Case 1:- No child
50     * Case 2:- 1 child
51     * case 3:- 2 child
52     * */
53    public void deleteANode(Node node) {
54        deleteNode(this.root, node);
55    }
56
57    private Node deleteNode(Node root, Node node) {
58        // check for node initially
59        if (root == null) {
60            return null;
61        } else if (node.data < root.data) {
62            // process the left sub tree
63            root.left = deleteNode(root.left, node);
64        } else if (node.data > root.data) {
65            // process the right sub tree
66            root.right = deleteNode(root.right, node);
67        } else if(root.data==node.data){
68            // case 3: 2 child
69            if (root.left != null && root.right != null) {
70                int lmax = findMaxData(root.left);
71                root.data = lmax;
72                root.left = deleteNode(root.left, new Node(lmax));
73                return root;
74            }
75            //case 2: one child
76            // case i-> has only left child
77            else if (root.left != null) {
78                return root.left;
79            }
80            // case ii-> has only right child
81            else if (root.right != null) {
82                return root.right;
83            }
84            //case 1:- no child
85            else {
86                return null;
87            }
88        }
89        return root;
90    }
91
92    // inorder successor of given node
93    public int findMaxData(Node root) {
94        if (root.right != null) {
95            return findMaxData(root.right);
96        } else {
97            return root.data;
98        }
99    }
100
101    public void preorder(){
102        preorder(root);
103        System.out.println();
104    }
105    public void preorder(Node node){
106        if(node!=null){
107            System.out.print(node.data+" ");
108            preorder(node.left);
109            preorder(node.right);
110        }
111    }
112
113
114    public static void main(String[] args) {
115        // Creating the object of BinarySearchTree class
116        BinarySearchTree bst = new BinarySearchTree();
117        // call the method insert
118        bst.insert(8);
119        bst.insert(5);
120        bst.insert(9);
121        bst.insert(3);
122        bst.insert(7);                bst.preorder();
123        bst.deleteANode(new Node(9));
124        bst.preorder();
125    }
126}
127