Binary Search Tree (BST) adalah binary tree dengan aturan: nilai kiri < parent < nilai kanan.

Aturan ini membuat pencarian sangat efisien — setiap langkah mengeliminasi setengah data.

Operasi dan kompleksitas:

class BST {
  constructor() {
    this.root = null;
  }

  insert(value) {
    const node = new TreeNode(value);
    if (!this.root) {
      this.root = node;
      return;
    }

    let current = this.root;
    while (true) {
      if (value < current.value) {
        if (!current.left) { current.left = node; return; }
        current = current.left;
      } else {
        if (!current.right) { current.right = node; return; }
        current = current.right;
      }
    }
  }

  search(value) {
    let current = this.root;
    while (current) {
      if (value === current.value) return current;
      if (value < current.value) current = current.left;
      else current = current.right;
    }
    return null; // Tidak ditemukan
  }
}

const bst = new BST();
[8, 3, 10, 1, 6, 14, 4, 7].forEach(v => bst.insert(v));

//        8
//       / \
//      3   10
//     / \    \
//    1   6   14
//       / \
//      4   7

bst.search(6); // Ditemukan! (8→3→6)
bst.search(5); // null (8→3→6→4→null)

Mengapa BST bisa O(n)? Jika data dimasukkan secara berurutan (1, 2, 3, 4...), tree jadi miring seperti linked list. Solusi: gunakan balanced BST (AVL tree, Red-Black tree).

🎭 Analogi sehari-hari: BST = cara kamu cari kata di kamus tebal. Buka tengah, kata yang dicari sebelum atau sesudah? Kalau sebelum, buang setengah belakang, ulangi di setengah depan. Setengah data hilang setiap langkah = O(log n). 1jt kata = max 20 langkah. Itu binary search yang dipersist sebagai struktur.

💡 Kenapa BST sempat populer, sekarang kalah dari Hash Map? BST punya kelebihan yang Hash Map gak punya: data tetap terurut (in-order traversal = sorted). Kalau gak butuh urutan, Hash Map (O(1)) lebih cepat. Tapi kalau butuh "ambil 10 nilai terkecil" atau "range query", BST/balanced BST menang.

⚠️ Jebakan umum:

• Insert berurutan = unbalanced — data 1,2,3,4,5 bikin tree miring kanan total. Pakai balanced variant (AVL, Red-Black) di production
• Delete BST itu rumit — 3 case: leaf, satu child, dua child (cari in-order successor). Banyak yang salah
• Duplicates di BST harus diputuskan: skip, simpan count, atau aturan kiri/kanan. Tidak ada default

🎯 Hash Map vs BST:

• Cuma get/set/has → Hash Map (O(1))
• Range query, sorted iteration, find min/max → BST (O(log n))
• Database index → B-tree (varian BST untuk disk)

🧪 Tebakan cepat: Insert [5, 3, 7, 1, 4] ke BST. Bagaimana strukturnya? Root 5, left 3 (left 1, right 4), right 7. In-order traversal? 1,3,4,5,7 — selalu sorted, itulah magic BST.

TL;DR: BST = binary tree dengan rule kiri<parent<kanan. Search/insert/delete O(log n) jika balanced, O(n) jika miring. Pakai variant balanced (AVL/Red-Black) di production.