Geeks_for_geeks-Data-Structures/Delete a node from BST.java at main · Kumpatlapavankumar/Geeks_for_geeks-Data-Structures · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
// User function Template for Java

class Tree {
    // Function to delete a node from BST.
    public static Node deleteNode(Node root, int x) {
        // code here.
        if(root==null){
            return root;
        }else if(root.data>x){
            root.left=deleteNode(root.left,x);
        }else if(root.data<x){
            root.right=deleteNode(root.right,x);
        }else{
            if(root.left!=null){
                return root.right;
            }else if(root.right!=null){
                return root.left;
            }else{
                Node succ=successor(root);
                root.data=succ.data;
                root.right=deleteNode(root.right,succ.data);
            }
        }

    }
    public static Node successor(Node root){
        root=root.right;
        while(root!=null && root.left!=null){
            root=root.left;
        }
        return root;
    }
}