İkili Arama Ağacı (BST)

from __future__ import annotations

from dataclasses import dataclass


@dataclass
class Node:
    value: int
    left: Node | None = None
    right: Node | None = None


def insert(node: Node | None, value: int) -> Node:
    if node is None:
        return Node(value)
    if value < node.value:
        node.left = insert(node.left, value)
    elif value > node.value:
        node.right = insert(node.right, value)
    return node  # duplicates are ignored


def contains(node: Node | None, value: int) -> bool:
    while node is not None:
        if value == node.value:
            return True
        node = node.left if value < node.value else node.right
    return False


def remove(node: Node | None, value: int) -> Node | None:
    if node is None:
        return None
    if value < node.value:
        node.left = remove(node.left, value)
    elif value > node.value:
        node.right = remove(node.right, value)
    elif node.left and node.right:
        # Two children: copy the in-order successor, then remove it from the right subtree.
        succ = node.right
        while succ.left:
            succ = succ.left
        node.value = succ.value
        node.right = remove(node.right, succ.value)
    else:
        # Zero or one child: the child (or None) takes this node's place.
        return node.left or node.right
    return node


def inorder(node: Node | None) -> list[int]:
    if node is None:
        return []
    return inorder(node.left) + [node.value] + inorder(node.right)


root = None
for v in (50, 30, 70, 20, 40, 60, 80):
    root = insert(root, v)

print(*inorder(root))  # sorted order
print(str(contains(root, 60)).lower())
root = remove(root, 50)  # the root has two children
print(*inorder(root))