Što je binarno stablo i koji su česti redoslijedi obilaska?

Question

Accepted Answer

**Binarno stablo** je hijerarhijska struktura gdje svaki **čvor** ima maksimalno **dvoje djece**, nazvane `left` i `right`. Ima jedan **korijen**; čvorovi bez djece su **listovi**. To je temelj za BST-e, heape i stabla izraza.

## Struktura

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

## Obilasci

```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)
```

**Obilazak razinom** (BFS) koristi red čekanja i obnavlja dubinu po dubinu.

| Obilazak | Redoslijed | Česta primjena |
|---|---|---|
| Inorder | L, N, D | sortirani izlaz BST-a |
| Preorder | N, L, D | kopiranje/serijalizacija stabla |
| Postorder | L, D, N | brisanje stabla, evaluacija izraza |
| Level-order | po dubini | BFS, najkraći put u stablu |

Svaki obilazak posjećuje svaki čvor jednom → **O(n)** vremenska složenost, **O(h)** prostorna složenost nastack-u gdje je `h` visina stabla.

## Zašto je važno

Binarna stabla prirodno modeliraju hijerarhijske podatke (datotečni sustavi, stabla analize, stabla odlučivanja) i temelje se na učinkovitim strukturama za pretragu i sortiranje.

Svladavanje četiriju obilazaka je bitno — većina problema s intervjuom o stablima je varijacija jednog od njih.

Obilazak	Redoslijed	Česta primjena
Inorder	L, N, D	sortirani izlaz BST-a
Preorder	N, L, D	kopiranje/serijalizacija stabla
Postorder	L, D, N	brisanje stabla, evaluacija izraza
Level-order	po dubini	BFS, najkraći put u stablu