Belajar Data Structure - Binary Tree

#Pendahuluan

Setelah di episode 9 kita menutup Fase 2 dengan deque dan circular buffer, pada episode ini kita memasuki Fase 3: Trees dengan membahas binary tree — struktur data non-linear di mana setiap node memiliki maksimal dua child (kiri dan kanan). Binary tree adalah fondasi untuk BST, AVL, Red-Black tree, B-Tree, dan trie yang akan kita pelajari di episode selanjutnya.

Trees mungkin terasa seperti lompatan besar dari linear structures, tetapi pemahaman kalian tentang rekursi (episode 4) dan traversal berbasis queue/stack (episode 6) sudah menjadi bekal yang cukup. Di balik setiap tree traversal tersembunyi stack frame atau queue yang bekerja.

#Konsep Dasar

#Node dan Edge

Setiap node dalam binary tree berisi:

• Value/data: informasi yang disimpan
• Left child: referensi ke subtree kiri (atau None)
• Right child: referensi ke subtree kanan (atau None)

Root adalah node paling atas. Leaf adalah node tanpa children. Height adalah jumlah edge terpanjang dari root ke leaf. Depth adalah jumlah edge dari root ke node tertentu.

#Full vs Complete vs Perfect

#Representasi

#Node Class

Representasi node class

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

#Array (Heap-Style)

Untuk complete binary tree, bisa direpresentasikan sebagai array tanpa pointer:

Tree:        1
            / \
           2   3
          / \ /
         4  5 6
 
Array: [1, 2, 3, 4, 5, 6]
Node i: left = 2i+1, right = 2i+2

#Traversals

#In-Order (Left, Root, Right)

Mengunjungi subtree kiri, lalu node, lalu subtree kanan. Pada BST, menghasilkan urutan terurut.

In-order traversal

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

#Pre-Order (Root, Left, Right)

Mengunjungi node terlebih dahulu, lalu subtree kiri, lalu subtree kanan. Berguna untuk membuat copy tree.

Pre-order traversal

def pre_order(node):
    if node is None:
        return []
    return [node.value] + pre_order(node.left) + pre_order(node.right)

#Post-Order (Left, Right, Root)

Mengunjungi subtree kiri, lalu subtree kanan, lalu node. Berguna untuk delete tree dan evaluasi expression tree.

Post-order traversal

def post_order(node):
    if node is None:
        return []
    return post_order(node.left) + post_order(node.right) + [node.value]

#Level-Order (BFS)

Mengunjungi node level demi level menggunakan queue.

Level-order traversal

from collections import deque
 
def level_order(root):
    if not root:
        return []
    result = []
    queue = deque([root])
    while queue:
        node = queue.popleft()
        result.append(node.value)
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)
    return result

#Mengukur Tree

#Height

Menghitung height tree

def height(node):
    if node is None:
        return -1
    return 1 + max(height(node.left), height(node.right))

#Size (Jumlah Node)

Menghitung jumlah node

def size(node):
    if node is None:
        return 0
    return 1 + size(node.left) + size(node.right)

#Max Width

Menghitung max width tree

from collections import deque
 
def max_width(root):
    if not root:
        return 0
    max_w = 0
    queue = deque([root])
    while queue:
        level_size = len(queue)
        max_w = max(max_w, level_size)
        for _ in range(level_size):
            node = queue.popleft()
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
    return max_w

#Praktik

Bangun tree manual dan uji traversals

root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
root.right.left = TreeNode(6)
 
print("In-order:", in_order(root))
print("Pre-order:", pre_order(root))
print("Post-order:", post_order(root))
print("Level-order:", level_order(root))
print("Height:", height(root))
print("Size:", size(root))
print("Max width:", max_width(root))

#Penutup

Inti yang harus dibawa pulang:

• Binary tree: setiap node memiliki maksimal dua child (left dan right).
• Empat traversals: in-order (LNR), pre-order (NLR), post-order (LRN), level-order (BFS).
• Representasi: node class (pointer) vs array (heap-style indexing).
• Mengukur: height, size, max-width — semuanya rekursif atau BFS.
• Binary tree adalah fondasi untuk semua tree lain di episode selanjutnya.

Di episode 11 selanjutnya kita akan membahas Binary Search Tree (BST) — binary tree dengan aturan: left child < parent < right child → in-order traversal = urutan terurut. Kita akan mengimplementasikan insert, search, dan delete, serta melihat masalah worst case O(n) saat tree skewed. Pastikan kalian sudah paham binary tree karena BST membangun di atasnya!