Binary search tree from scratch

Build an unbalanced binary search tree of distinct integer keys, using real linked nodes (no sorted lists, no bisect).

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

BST() starts empty. Its root node is the attribute root (None when empty). The tests walk your nodes to check that the tree is a valid BST, so keep Node exactly as above.

• insert(key) -> bool: add the key. Keys are distinct, so inserting a key that's already present changes nothing and returns False; otherwise return True.
• search(key) -> bool: is the key in the tree?
• delete(key) -> bool: remove the key and return True, or return False if it isn't there. The node must actually leave the tree (no "deleted" flags). Handle all three cases: a leaf, a node with one child, and a node with two children (swap in the in-order successor or predecessor, then remove that one).
• inorder() -> list[int]: all keys in ascending order.
• __len__(): number of keys.

t = BST()
for k in [50, 30, 70, 20, 40, 60, 80]:
    t.insert(k)
t.insert(30)      # False, already there
t.delete(30)      # True; 30 had two children
t.search(30)      # False
t.inorder()       # [20, 40, 50, 60, 70, 80]
t.delete(50)      # True; the root itself
len(t)            # 5

Every operation should take time proportional to the tree's height. The tests insert up to a few hundred keys in sorted order, so a recursive version fits within Python's default recursion limit, but an iterative one is safer.

Discussion (not tested)

• What are the average and worst-case costs of each operation? Which insertion order produces the worst case?
• How does an AVL tree stay balanced? Name the four rotation cases (LL, LR, RR, RL) and walk through one insertion that needs a double rotation.
• What are the red-black tree invariants, and why do they keep the height within about 2 log n?
• In C++, how would you manage node ownership (unique_ptr children versus raw pointers with a destructor)?