binary_tree/binary_tree.py at master · jackhamby/binary_tree · 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
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190

class BinaryTree:

    def __init__(self):

        self.root = None

    ### ================================================================ ###
    ### INSERT                                                           ###
    ### ================================================================ ###

    def insert(self, value):
        node = Node(value)
        if (not self.root):
            self.root = node
            return
        self.insert_node(self.root, node)

    def insert_node(self, node, inserted_node):
        # Right child
        if (inserted_node.value >= node.value):
            if (not node.r_child):
                node.r_child = inserted_node
            else:
                self.insert_node(node.r_child, inserted_node)
        # Left child
        else:
            if (not node.l_child):
                node.l_child = inserted_node
            else:
                self.insert_node(node.l_child, inserted_node)


    ### ================================================================ ###
    ### MAX / MIN VALUES                                                 ###
    ### ================================================================ ###

    def max_value(self):
        if (not self.root):
            return False
        max_value = self.root.value
        r_child = self.root.r_child
        while(r_child):
            max_value = r_child.value
            r_child = r_child.r_child
        return max_value

    def min_value(self):
        if (not self.root):
            return False
        min_value = self.root.value
        l_child = self.root.l_child
        while(l_child):
            min_value = l_child.value
            l_child = l_child.l_child
        return min_value


    ### ================================================================ ###
    ### MAX / MIN DEPTH                                                  ###
    ### ================================================================ ###


    def max_depth(self):
        self.max_depth = 0
        if (not self.root):
            return self.max_depth
        self.traverse_depth(self.root, 0)
        return self.max_depth

    def traverse_depth(self, node, current_depth):
        current_depth += 1
        if (current_depth > self.max_depth):
            self.max_depth = current_depth
        if (node.l_child):
            self.traverse_depth(node.l_child, current_depth)
        if (node.r_child):
            self.traverse_depth(node.r_child, current_depth)


    def min_depth(self):
        pass


    ### ================================================================ ###
    ### SEARCH                                                           ###
    ### ================================================================ ###

    def search(self, value):
        if (not self.root):
            return False
        return self.search_node(self.root, value)

    def search_node(self, node, value):
        if (not node):
            return False
        if (node.value == value):
            return True
        elif (value >= node.value):
            return self.search_node(node.r_child, value)
        else:
            return self.search_node(node.l_child, value)


    ### ================================================================ ###
    ### SIZE                                                             ###
    ### ================================================================ ###

    def size(self):
        self.size = 0
        if (not self.root):
            return self.size
        self.count_node(self.root)
        return self.size

    def count_node(self, node):
        self.size += 1
        if (node.l_child):
            self.count_node(node.l_child)
        if (node.r_child):
            self.count_node(node.r_child)


    ### ================================================================ ###
    ### PRINT                                                            ###
    ### ================================================================ ###

    def show(self):
        tree = []
        level = 0
        tree.append([])
        self.show_node(level, self.root, tree)
        print(tree)

    def show_node(self, level, node, tree):
        tree[level].append(node.value)
        level += 1
        if (len(tree) <= level):
            tree.append([])
        if (node.l_child):
            self.show_node(level, node.l_child, tree)
        if (node.r_child):
            self.show_node(level, node.r_child, tree)

class Node:

    def __init__(self, value):

        self.value = value

        self.l_child = None
        self.r_child = None

        # print(f'creating node with value {self.value}')

    def show(self):
        print(f' {self.value}        ')
        print(f'{self.l_child.value}      {self.r_child.value}')


if __name__ == '__main__':
    tree = BinaryTree()


    tree.insert(6)
    tree.insert(3)
    tree.insert(4)
    tree.insert(8)
    tree.insert(7)
    tree.insert(2)
    tree.insert(4)
    tree.insert(4)
    tree.insert(12)
    tree.insert(1)
    tree.insert(4)

    tree.show()

    print(f'looking for 3 : {tree.search(3)}')
    print(f'looking for 5 : {tree.search(5)}')
    print(f'looking for 8 : {tree.search(8)}')

    print(f'tree size is: {tree.size()} nodes')
    print(f'tree max value is: {tree.max_value()}')
    print(f'tree min value is: {tree.min_value()}')

    print(f'tree max depth is: {tree.max_depth()}' )