X'inhu l-binaryu tree u x'inhuma l-ordnijiet ta' traversal komuni?

Question

Accepted Answer

A **binary tree** huwa struttura ġerarkika fejn kull **node** għandu l-aktar **żewġ iben**, imsejħin `left` u `right`. Għandu **root** wieħed; in-nodi mingħajr iben huma **leaves**. Hu l-bażi għal BSTs, heaps, u expression trees.

## Struttura

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

## Traversals

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

Traversal **level-order** (BFS) juża queue u jivżita depth by depth.

| Traversal | Ordni | Użu komuni |
|---|---|---|
| Inorder | L, N, R | sorted output ta' BST |
| Preorder | N, L, R | copy/serialize ta' tree |
| Postorder | L, R, N | delete ta' tree, evaluate expr |
| Level-order | by depth | BFS, shortest path fuq tree |

Kull traversal jivżita kull node darba → **O(n)** ħin, **O(h)** stack space fejn `h` huwa l-għoli.

## Għaliex huwa importanti

Binary trees jimmudellaw data ġerarkika b'mod naturali (file systems, parse trees, decision trees) u huma bażi għal strutturi ta' search u sorting effiċjenti.

Igħarraf l-erba' traversals huwa essenzjali — ħafna problemi ta' tree interview huma varjazzjoni ta' wieħed minnhom.

Traversal	Ordni	Użu komuni
Inorder	L, N, R	sorted output ta' BST
Preorder	N, L, R	copy/serialize ta' tree
Postorder	L, R, N	delete ta' tree, evaluate expr
Level-order	by depth	BFS, shortest path fuq tree