Binary Search Trees (BSTs) are a foundational concept in computer science and software engineering, commonly used in implementing efficient searching, insertion, and deletion operations. A BST is a type of binary tree with a specific structure that allows for fast data retrieval.

A binary search tree is consisted by nodes. Each node contains 3 informations. The data, the value that the node carries, a left node pointer where it points to a node with a value less than the one it carries and a right node pointer where it points to a node with a value larger than the one it carries.

There are four main operations on a binary search tree.

• search
• insert
• delete
• traverse

The main advantage of a BST is the efficient lookup, insert and delete. You move along the nodes by going left or right according to the value you search/insert/delete every time. This comes with a drawback. A binary search tree is not balanced. You might have a node with only left or only right node.

Where it is used

• Databases
• Filesystems
• Auto complete and dictionaries

class Node:
    def __init__(self, value):
        # print("__INIT__: " + str(value))
        self.left = None
        self.right = None
        self.value = value

class BST:
    def __init__(self, value):
        self.root = Node(value)

    def insert(self, value):
        current = self.root
        while True:
            if value < current.value:
                if current.left is None:
                    current.left = Node(value)
                    return
                current = current.left
            else:
                if current.right is None:
                    current.right = Node(value)
                    return
                current = current.right

    def search(self, value):
        current = self.root
        while current is not None:
            if value == current.value:
                return True
            if value < current.value:
                current = current.left
            else:
                current = current.right
        return False




obj = BST(10)
obj.insert(1)
obj.insert(11)
obj.insert(12)
obj.insert(4)
print(obj.search(4))
print(obj.search(2))
print(obj.search(12))