Binary Search Tree (BST)

A Binary Search Tree (BST) is a tree data structure where each node has at most two children, referred to as the left and right child. The left child contains only nodes with values less than the parent node, and the right child contains only nodes with values greater than the parent node.

Space Complexity: O(n)
Time Complexity: O(log n) for search, insert, and delete operations
Best Case: Ω(log n)
Average Case: Θ(log n)
Worst Case: O(n) (for a degenerate tree)


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

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

    def insert(self, data):
        if self.root is None:
            self.root = Node(data)
        else:
            self._insert(self.root, data)

    def _insert(self, node, data):
        if data < node.data:
            if node.left is None:
                node.left = Node(data)
            else:
                self._insert(node.left, data)
        else:
            if node.right is None:
                node.right = Node(data)
            else:
                self._insert(node.right, data)

    def inorder(self, node):
        result = []
        if node:
            result = self.inorder(node.left)
            result.append(node.data)
            result = result + self.inorder(node.right)
        return result

    def preorder(self, node):
        result = []
        if node:
            result.append(node.data)
            result = result + self.preorder(node.left)
            result = result + self.preorder(node.right)
        return result

    def postorder(self, node):
        result = []
        if node:
            result = self.postorder(node.left)
            result = result + self.postorder(node.right)
            result.append(node.data)
        return result

    def displayTraversal(self, traversal_type):
        if traversal_type == 'inorder':
            return ' -> '.join(map(str, self.inorder(self.root)))
        elif traversal_type == 'preorder':
            return ' -> '.join(map(str, self.preorder(self.root)))
        elif traversal_type == 'postorder':
            return ' -> '.join(map(str, self.postorder(self.root)))

# Example Usage
bst = BinarySearchTree()
for i in range(20):
    bst.insert(random.randint(0, 100))

print("Inorder:", bst.displayTraversal('inorder'))
print("Preorder:", bst.displayTraversal('preorder'))
print("Postorder:", bst.displayTraversal('postorder'))