Что такое бинарное дерево поиска (BST)?

BST — дерево, где для каждого узла: все в left subtree < node.val, все в right subtree > node.val. In-order traversal даёт sorted order. Операции O(log n) average (balanced), O(n) worst (degenerate).

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def search(root, val):
    while root:
        if val == root.val:
            return root
        elif val < root.val:
            root = root.left
        else:
            root = root.right
    return None

Delete — 3 случая: leaf (просто удалить), один child (заменить на child), два children (найти in-order successor, заменить val, удалить successor). Балансировка: AVL (height diff ≤ 1), Red-Black Tree — O(log n) guaranteed. Traversals: in-order (sorted), pre-order, post-order, level-order (BFS).