Data-Structures-in-Python/BST.py at master · AvaGhiasian/Data-Structures-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
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
123
124
125
126
127
128
129
130
131
132
133
134
135
from tool_box.sll_queue import Queue


class BSTNode:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None


class BST:
    def __init__(self):
        self.root = None

    def is_empty(self):
        return not self.root

    def inorder_traversal(self):
        self.inorder(self.root)

    def preorder_traversal(self):
        self.preorder(self.root)

    def postorder_traversal(self):
        self.postorder(self.root)

    def level_order_traversal(self):
        self.level_order(self.root)

    def inorder(self, node):
        if node is None:
            return
        else:
            self.inorder(node.left)
            print(node.data, end="  ")
            self.inorder(node.right)

    def postorder(self, node):
        if node is None:
            return
        else:
            self.postorder(node.left)
            self.postorder(node.right)
            print(node.data)

    def preorder(self, node):
        if node is None:
            return
        else:
            print(node.data)
            self.preorder(node.left)
            self.preorder(node.right)

    def level_order(self, root):
        queue = Queue()
        queue.enqueue(root)
        while queue.length > 0:
            temp = queue.dequeue()
            print(temp.data, end="  ")
            if temp.left is not None:
                queue.enqueue(temp.left)
            if temp.right is not None:
                queue.enqueue(temp.right)

    def insert(self, data):
        node = BSTNode(data)
        if self.is_empty():
            self.root = node
            return
        temp = self.root
        while temp.data != data:
            if node.data > temp.data:
                if temp.right:
                    temp = temp.right
                else:
                    temp.right = node
                    return
            if node.data < temp.data:
                if temp.left:
                    temp = temp.left
                else:
                    temp.left = node
                    return

    def delete_value(self, root, key):
        # base case
        if root is None:
            return root

        if key < root.data:
            root.left = self.delete_value(root.left, key)
        elif key > root.data:
            root.right = self.delete_value(root.right, key)
        else:
            if root.left is None:
                return root.right
            elif root.right is None:
                return root.left

            min_larger_node = self.find_min(root.right)
            root.data = min_larger_node.data
            root.right = self.delete_value(root.right, min_larger_node.data)

        return root

    def delete(self, data):
        self.root = self.delete_value(self.root, data)

    def search(self, data):
        temp = self.root
        while temp is not None:
            if temp.data == data:
                return temp
            elif temp.data > data:
                temp = temp.left
            else:
                temp = temp.right
        return None

    def find_min(self, node):
        current = node
        while current.left is not None:
            current = current.left
        return current

    def find_max(self, node):
        current = node
        while current.right is not None:
            current = current.right
        return current

    def height(self, node):
        if node is None:
            return 0
        return max(self.height(node.left), self.height(node.right)) + 1