Apakah itu binary tree dan apakah susunan traversal yang biasa?

Question

Accepted Answer

Suatu **binary tree** ialah struktur berhierarki di mana setiap **nod** mempunyai paling banyak **dua anak**, dipanggil `left` dan `right`. Ia mempunyai satu **root** tunggal; nod tanpa anak ialah **leaf**. Ia merupakan asas untuk BST, heap, dan expression tree.

## Struktur

```text
        1            depth 0 (root)
       / \
      2   3          depth 1
     / \
    4   5            depth 2 (leaves: 4,5,3)
```

## Traversal

```python
class Node:
    def __init__(self, val, left=None, right=None):
        self.val, self.left, self.right = val, left, right

def inorder(n):     # left, node, right -> 4 2 5 1 3
    if n:
        inorder(n.left); print(n.val); inorder(n.right)

def preorder(n):    # node, left, right -> 1 2 4 5 3
    if n:
        print(n.val); preorder(n.left); preorder(n.right)

def postorder(n):   # left, right, node -> 4 5 2 3 1
    if n:
        postorder(n.left); postorder(n.right); print(n.val)
```

Suatu traversal **level-order** (BFS) menggunakan queue dan melawat kedalaman demi kedalaman.

| Traversal | Susunan | Kegunaan biasa |
|---|---|---|
| Inorder | L, N, R | output terisih bagi BST |
| Preorder | N, L, R | salin/siri (serialize) tree |
| Postorder | L, R, N | padam tree, nilai expr |
| Level-order | mengikut kedalaman | BFS, laluan terpendek pada tree |

Setiap traversal melawat setiap nod sekali → masa **O(n)**, ruang stack **O(h)** di mana `h` ialah ketinggian.

## Mengapa ia penting

Binary tree memodelkan data yang secara semula jadi berhierarki (sistem fail, parse tree, decision tree) dan menyokong struktur carian dan pengisihan yang cekap.

Menguasai keempat-empat traversal adalah penting — kebanyakan masalah tree dalam temu duga ialah variasi salah satu daripadanya.

Traversal	Susunan	Kegunaan biasa
Inorder	L, N, R	output terisih bagi BST
Preorder	N, L, R	salin/siri (serialize) tree
Postorder	L, R, N	padam tree, nilai expr
Level-order	mengikut kedalaman	BFS, laluan terpendek pada tree