Tree-Questions/InsertionanddeletioninBST.cpp at main · subhradeepnag/Tree-Questions · 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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
#include <bits/stdc++.h>
using namespace std;

class BinaryTree
{
    public:
        int value;
        BinaryTree*left;
        BinaryTree*right;

    BinaryTree(int value){
        this->value = value;
        left = nullptr;
        right = nullptr;
    }
};

BinaryTree*insert(BinaryTree*root,int val)
{
    if(root == nullptr)
    {
        return new BinaryTree(val);
    }

    if(val > root->value)
    {
        root->right = insert(root->right,val);
    }
    else
    {
        root->left = insert(root->left,val);
    }

    return root;
}

BinaryTree*findmin(BinaryTree*root)
{
    while(root->left!=NULL)
    {
        root = root->left;
    }

    return root;
}

BinaryTree*remove(BinaryTree*root,int data)
{
    if(root == nullptr)
    {
        return root;
    }

    else if(data < root->value)
    {
        root->left = remove(root->left,data);
    }
    else if (data > root->value)
    {
        root->right = remove(root->right,data);
    }
    else
    {
        // No left and Right Child
        if(root->left == NULL && root->right == NULL)
        {
            delete(root);
            root = NULL;
            return root;
        }

        else if (root->left == NULL)
        {
            BinaryTree*temp = root;
            root = root->right;
            delete (temp);
            return root;
        }
        else if (root->right == NULL)
        {
            BinaryTree*temp = root;
            root = root->left;
            delete (temp);
            return root;
        }
        else
        {
            BinaryTree*temp = findmin(root->right);
            root->value = temp->value;
            root->right = remove(root->right,temp->value);

            return root;
        }
    }
}

void display(BinaryTree*root)
{
    if(root == nullptr)
    {
        return;
    }

    display(root->left);
    cout<<root->value<<" ";
    display(root->right);
}
int main()
{
    BinaryTree*root = new BinaryTree(10);
    root->left = new BinaryTree(5);
    root->right = new BinaryTree(15);
    root->left->left = new BinaryTree(2);
    root->left->right = new BinaryTree(5);
    root->right->left = new BinaryTree(13);
    root->right->right = new BinaryTree(22);
    insert(root,12);
    remove(root,10);
    display(root);


}