dsa-in-python/Data_Structure_BST.py at master · Sorabhkumar-dev/dsa-in-python · 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
class Node:
    def __init__(self,data):
        self.data=data
        self.left=None
        self.right=None

class BST:
    def __init__(self):
        self.root=None
    def insert1(self,data,node):
        if self.root == None:
            self.root=Node(data)
            return
        if data<node.data:
            if node.left is None:
                node.left=Node(data)
                return
            else:
                self.insert1(data,node.left)
        elif data>node.data:
            if node.right is None:
                node.right=Node(data)
            else:
                self.insert1(data,node.right)
        else:
            print("Sorry , You are trying to insert duplicate value")
            return
    def insert(self,data):
        self.insert1(data,self.root)
    def search(self,data):
        return self.search1(data,self.root)
    def search1(self,data,node):
        if node:
            if data==node.data:
                return True
            elif  data<node.data:
                return self.search1(data,node.left)
            elif data>node.data:
                return  self.search1(data,node.right)
            else:
                return "your given data not found"
    def show(self):
        self.inorder(self.root)
    def inorder(self,start):
        if start:
            self.inorder(start.left)
            print(start.data)
            self.inorder(start.right)
        return
    def getmax(self,node):
        if node:
            if node.right:
                return  self.getmax(node.right)
            return node.data
    def get_min(self,node):
        if node:
            if node.left:
                return self.get_min(node.left)
        return  node.data
    def removeNode(self,data,node):
        if not node:
            return node
        if data<node.data:
            node.left=self.removeNode(data,node.left)
        elif data>node.data:
            node.right=self.removeNode(data,node.right)
        else:
            if not node.left and not node.right:
                print("removing leaf node")
                del node
                return None
            if not self.left:
                print("removing node with right child")
                temp=node.right
                del node
                return temp
            elif not self.right:
                print("removing node with left child ")
                temp=node.left
                del node
                return temp
            tempnode=self.get_preceddor(node.left )
            node.data=tempnode.data
            node.left=self.removeNode(tempnode.data,node.left)
    def get_preceddor(self,node):
        if node.right:
            return  self.get_preceddor(node.right)
        return node
bst=BST()
bst.insert(2)
bst.insert(25)
bst.insert(7)
bst.insert(645)
bst.insert(87)
bst.show()
print(bst.removeNode(7,bst.root))
bst.show()