Binary search trees

English

A binary search tree (BST) stores values so they stay sorted and are fast to find.
Each node holds a value and links to up to two children: a left and a right.
The top node is the root. A node with no children is a leaf.

Bahasa Indonesia

Pohon Pencarian Biner

Pohon pencarian biner (BST) menyimpan nilai sehingga tetap terurut dan cepat ditemukan.
Setiap simpul menyimpan nilai dan terhubung ke maksimal dua anak: satu left dan satu right.
Simpul teratas adalah akar. Simpul tanpa anak adalah **daun.

English

The BST rule

For every node: everything in its left subtree is smaller, everything in its right is larger.
This one rule is what lets you find a value by going left or right — never both.

Bahasa Indonesia

Aturan BST

Untuk setiap simpul: semua di subtree kiri-nya lebih kecil, semua di subtree kanan-nya lebih besar.
Satu aturan inilah yang memungkinkan Anda menemukan nilai dengan bergerak ke kiri atau kanan — tidak pernah keduanya.

        5
       / \
      3   8
     / \   \
    1   4   9

left < node < right, at every node

English

A node

We model a node as a small object with a value, a left, and a right.
A brand-new node has no children yet, so left and right start as None.

Bahasa Indonesia

Sebuah Simpul

Kita memodelkan simpul sebagai objek kecil dengan value, left, dan right.
Simpul baru belum memiliki anak, sehingga left dan right dimulai sebagai None.

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

n = Node(5)
print(n.value)   # 5
print(n.left)    # None

English

Inserting a value

Start at the root. If the tree is empty, the new value becomes the root.
If the value is smaller than the current node, go left; otherwise go right.
Repeat until you reach an empty spot, and put the new node there.

Bahasa Indonesia

Menyisipkan Nilai

Mulai dari akar. Jika pohon kosong, nilai baru menjadi akar.
Jika nilai lebih kecil dari simpul saat ini, pergi ke kiri; jika tidak, pergi ke kanan.
Ulangi hingga mencapai posisi kosong, lalu letakkan simpul baru di sana.

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

def insert(root, value):
    if root is None:
        return Node(value)
    if value < root.value:
        root.left = insert(root.left, value)
    else:
        root.right = insert(root.right, value)
    return root

root = None
for v in [5, 3, 8, 1]:
    root = insert(root, v)
print(root.value)            # 5
print(root.left.value)       # 3
print(root.right.value)      # 8

English

In-order traversal gives sorted order

In-order traversal visits: the left subtree, then the node, then the right subtree.
Because of the BST rule, this visits the values in sorted order — for free.
It is naturally recursive: traverse left, take the value, traverse right.

Bahasa Indonesia

Penelusuran In-Order Menghasilkan Urutan Terurut

Traversing in-order mengunjungi: subtree kiri, kemudian node, lalu subtree kanan.
Karena aturan BST, ini mengunjungi nilai-nilai dalam urutan terurut — secara gratis.
Secara alami rekursif: traverse kiri, ambil nilainya, traverse kanan.

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

def insert(root, value):
    if root is None:
        return Node(value)
    if value < root.value:
        root.left = insert(root.left, value)
    else:
        root.right = insert(root.right, value)
    return root

def in_order(root):
    if root is None:
        return []
    return in_order(root.left) + [root.value] + in_order(root.right)

root = None
for v in [5, 3, 8, 1, 4]:
    root = insert(root, v)
print(in_order(root))   # [1, 3, 4, 5, 8]

English

Searching is fast

To find a value, compare it with the node, then go left or right — skipping half the tree each step.
In a balanced tree this takes about O(log n) steps, much faster than scanning a list.
A badly-shaped tree (values inserted already sorted) can degrade to a line — O(n).

Bahasa Indonesia

Pencarian berlangsung cepat

Untuk menemukan suatu nilai, bandingkan dengan node, lalu pergi ke kiri atau kanan — melewatkan setengah pohon setiap langkahnya.
Pada pohon yang seimbang ini memakan waktu sekitar O(log n) langkah, jauh lebih cepat daripada menelusuri daftar.
Pohon dengan bentuk buruk (nilai disisipkan sudah terurut) dapat memburuk menjadi garis lurus — O(n).

English

Common mistakes

In a binary search tree: left child < node < right child.
An unbalanced tree loses the speed advantage.

Bahasa Indonesia

Kesalahan umum

Dalam binary search tree: anak kiri < node < anak kanan.
Pohon yang tidak seimbang kehilangan keunggulan kecepatannya.

English

Now you try

Build the three core operations: insert, in_order, and contains.
The Node class (and a working insert, where you need it) is provided.
Press Check answer to test it on several trees.

Bahasa Indonesia

Sekarang Anda coba

Bangun tiga operasi inti: insert, in_order, dan contains.
Kelas Node (dan implementasi insert yang berfungsi, jika diperlukan) disediakan.
Tekan Periksa jawaban untuk mengujinya pada beberapa pohon.

Explore · ⁨Jelajahi⁩

Searching a BST · ⁨Mencari BST⁩

Left is smaller, right is bigger — so each step skips half the tree. · ⁨Kiri lebih kecil, kanan lebih besar—sehingga setiap langkah melewati separuh pohon.⁩

The Node class is provided. Write insert(root, value) that adds value to the BST and returns the root. If root is None, return a new Node(value). If value < root.value go left, otherwise go right — and reassign that child to the result of inserting into it. · ⁨Kelas Node disediakan. Tulis insert(root, value) yang menambahkan value ke BST dan mengembalikan akar. Jika root adalah None, kembalikan baru Node(value). Jika value < root.value pergi ke kiri, sebaliknya pergi ke kanan—dan tetapkan ulang anak tersebut ke hasil penyisipan ke dalamnya.⁩

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

def insert(root, value):
    # Empty -> new Node. Else go left if smaller, right otherwise. Return root.
    pass

Click Run to see the output here. · ⁨Klik Jalankan untuk melihat output di sini.⁩

Node and a working insert are provided. Write in_order(root) that returns a list of the values from an in-order traversal: left subtree, then this node's value, then right subtree. Thanks to the BST rule the list comes out sorted. An empty tree (None) gives []. · ⁨Node dan insert yang berfungsi disediakan. Tulis in_order(root) yang mengembalikan daftar nilai dari traversal in-order: subtree kiri, lalu nilai node ini, kemudian subtree kanan. Aturan BST membuat daftar keluar terurut. Pohon kosong (None) menghasilkan [].⁩

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

def insert(root, value):
    if root is None:
        return Node(value)
    if value < root.value:
        root.left = insert(root.left, value)
    else:
        root.right = insert(root.right, value)
    return root

def in_order(root):
    # Return left values + [this value] + right values; [] when root is None
    pass

Click Run to see the output here. · ⁨Klik Jalankan untuk melihat output di sini.⁩

Node and a working insert are provided. Write contains(root, value) that returns True if value is in the tree, else False. Use the BST rule: if it equals this node return True; if it is smaller search left, otherwise search right; an empty branch (None) means it is not there. · ⁨Node dan insert yang berfungsi disediakan. Tulis contains(root, value) yang mengembalikan True jika value ada di pohon, selain itu False. Gunakan aturan BST: jika sama dengan node ini kembalikan True; jika lebih kecil cari kiri, sebaliknya cari kanan; cabang kosong (None) berarti tidak ada.⁩

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

def insert(root, value):
    if root is None:
        return Node(value)
    if value < root.value:
        root.left = insert(root.left, value)
    else:
        root.right = insert(root.right, value)
    return root

def contains(root, value):
    # None -> False. Equal -> True. Smaller -> search left, else search right.
    pass

Click Run to see the output here. · ⁨Klik Jalankan untuk melihat output di sini.⁩

Binary search trees · ⁨Pohon pencarian biner (BST)⁩