બાઈનરી ટ્રી શું છે અને સામાન્ય ટ્રાવર્સલ ક્રમ કયા છે?

Question

IT Interview Practice · Accepted Answer

એક **બાઈનરી ટ્રી** એક હાયરાર્કિકલ સ્ટ્રક્ચર છે જ્યાં દરેક **નોડ** પાસે સર્વોચ્છ **બે બાળકો** હોય છે, જેને `left` અને `right` કહેવાય છે. તેની એક જ **root** છે; જે નોડ્સ પાસે કોઈ બાળક નથી તેને **leaves** કહેવાય છે. તે BSTs, heaps, અને expression trees ના પાયા છે.

## સ્ટ્રક્ચર

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

## ટ્રાવર્સલ્સ

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

એક **level-order** (BFS) ટ્રાવર્સલ queue વાપરે છે અને depth દ્વારા depth વિઝિટ કરે છે.

| ટ્રાવર્સલ | ક્રમ | સામાન્ય ઉપયોગ |
|---|---|---|
| Inorder | L, N, R | BST ની sorted output |
| Preorder | N, L, R | ટ્રી કૉપી/serialize કરવી |
| Postorder | L, R, N | ટ્રી ડિલીટ કરવી, expr મૂલ્યાંકન |
| Level-order | by depth | BFS, ટ્રી પર shortest path |

દરેક ટ્રાવર્સલ દરેક નોડને એક વાર વિઝિટ કરે છે → **O(n)** સમય, **O(h)** stack સ્પેસ જ્યાં `h` height છે.

## તે શા માટે મહત્વપૂર્ણ છે

બાઈનરી ટ્રીઝ કુદરતી રીતે હાયરાર્કિકલ ડેટા (file systems, parse trees, decision trees) મોડેલ કરે છે અને કાર્યક્ષમ search અને sorting સ્ટ્રક્ચર્સ આધાર બનાવે છે.

ચાર ટ્રાવર્સલ્સમાં માસ્ટર હોવું આવશ્યક છે — મોટાભાગની tree ઇન્ટરવ્યુ સમસ્યાઓ તેમાંથી એકનો વિવિધતા છે.

Inorder	L, N, R	BST ની sorted output
Preorder	N, L, R	ટ્રી કૉપી/serialize કરવી
Postorder	L, R, N	ટ્રી ડિલીટ કરવી, expr મૂલ્યાંકન
Level-order	by depth	BFS, ટ્રી પર shortest path

સ્ટ્રક્ચર

ટ્રાવર્સલ્સ

તે શા માટે મહત્વપૂર્ણ છે

સંબંધિત પ્રશ્નો