Binary Search Tree

Invariant মাত্র এক লাইন: node-এর চেয়ে ছোট সব key বামে, বড় সব ডানে।

Search তাই প্রতি ধাপে অর্ধেক tree বাদ দেয়:

def search(node, key):
    while node and node.key != key:
        node = node.left if key < node.key else node.right
    return node

In-order traversal করলে key গুলো sorted বেরিয়ে আসে — invariant-এর সরাসরি ফল।

দুর্বলতা: sorted input ঢুকলে tree হয়ে যায় linked list, খরচ O(log n) থেকে O(n)। এই সমস্যাই AVL আর Red-Black tree-র জন্ম দিয়েছে।