Binary Search Tree Implementation in Python

class BSTNode:
    def __init__(self, val: int):
        self.val = val
        self.left: BSTNode | None = None
        self.right: BSTNode | None = None

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

    def insert(self, val: int) -> None:
        self.root = self._insert(self.root, val)

    def _insert(self, node: BSTNode | None, val: int) -> BSTNode:
        if not node: return BSTNode(val)
        if val < node.val: node.left = self._insert(node.left, val)
        elif val > node.val: node.right = self._insert(node.right, val)
        return node

    def search(self, val: int) -> bool:
        return self._search(self.root, val)

    def _search(self, node: BSTNode | None, val: int) -> bool:
        if not node: return False
        if val == node.val: return True
        if val < node.val: return self._search(node.left, val)
        return self._search(node.right, val)

    def inorder(self) -> list[int]:
        result: list[int] = []
        def traverse(node: BSTNode | None):
            if node:
                traverse(node.left)
                result.append(node.val)
                traverse(node.right)
        traverse(self.root)
        return result

tree = BST()
for v in [5, 3, 7, 1, 4, 6, 8]: tree.insert(v)
print(tree.inorder())  # [1, 3, 4, 5, 6, 7, 8]
print(tree.search(4))  # True