python-data-structures-and-algorithms/Trees/Binary Search Tree/BinarySearchTree.py at main · CPWu/python-data-structures-and-algorithms · 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
## Creation of Binary Search Tree ##

## Valid BST
#                8
#              /   \
#           3        10
#         /   \     /   \
#       1      6   9     11

## Invalid BST ##
#                12
#              /   \
#           3        14
#         /   \     /   \
#       1      13  11    15

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

class BinarySearchTree:
    # Class Constructor
    def __init__(self):
        self.root = None

    # Insertion - Recursion
    def insert(self, data):
        # If tree is empty
        if self.root is None:
            self.root = Node(data)
        else:
            self._insert(data, self.root)

    def _insert(self, data, current_node):
        if data < current_node.data:
            if current_node.left is None:
                current_node.left = Node(data)
            else:
                self._insert(data, current_node.left)
        elif data > current_node.data:
            if current_node.right is None:
                current_node.right = Node(data)
            else:
                self._insert(data, current_node.right)
        else:
            print("The value is already present in tree.")

    # Find value - Recursion
    def search(self, data):
        if self.root:
            is_found = self._search(data, self.root)
            if is_found:
                return True
            return False
        else:
            return None

    def _search(self, data, current_node):
        if data > current_node.data and current_node.right:
            return self._search(data, current_node.right)
        elif data < current_node.data and current_node.left:
            return self._search(data, current_node.left)
        if data == current_node.data:
            return True

    # Print Binary Tree (Inorder)
    # Can be done preorder or postorder also.
    def inorder_print_tree(self):
        if self.root:
            self._inorder_print_tree(self.root)

    def _inorder_print_tree(self, current_node):
        if current_node:
            self._inorder_print_tree(current_node.left)
            print(str(current_node.data))
            self._inorder_print_tree(current_node.right)

# Instantiate Binary Search Tree
binarySearchTree = BinarySearchTree()

binarySearchTree.insert(2)
binarySearchTree.insert(3)
binarySearchTree.insert(1)
binarySearchTree.inorder_print_tree()
print(binarySearchTree.search(3))
print(binarySearchTree.search(4))