பைனரி ட்ரீ என்றால் என்ன மற்றும் பொதுவான ட்ராவர்சல் ஆர்டர்கள் என்னவை?

Question

IT Interview Practice · Accepted Answer

A **binary tree** என்பது ஒரு படிநிலை কட்டமைப்பு ஆகும், இதில் ஒவ்வொரு **node** க்கும் அதிகபட்சம் **இரண்டு children** உள்ளன, அவை `left` மற்றும் `right` என்று அழைக்கப்படுகின்றன. இதில் ஒரே **root** உள்ளது; குழந்தைகள் இல்லாத nodes **leaves**. இது BST, heaps மற்றும் expression trees இன் அடிப்படை ஆகும்.

## Structure

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

A **level-order** (BFS) traversal ஒரு queue ஐ பயன்படுத்தி depth by depth ஐ பார்க்கிறது.

| Traversal | Order | Common use |
|---|---|---|
| Inorder | L, N, R | sorted output of a BST |
| Preorder | N, L, R | copy/serialize a tree |
| Postorder | L, R, N | delete a tree, evaluate expr |
| Level-order | by depth | BFS, shortest path on tree |

ஒவ்வொரு traversal ஆனது ஒவ்வொரு node ஐ ஒரு முறை பார்க்கிறது → **O(n)** time, **O(h)** stack space இதில் `h` என்பது ட்ரீயின் உயரம்.

## இது ஏன் முக்கியமாக இருக்கிறது

பைனரி ட்ரீ இயல்பாகவே படிநிலை தரவுகளை (file systems, parse trees, decision trees) மாதிரிப்படுத்துகிறது மற்றும் திறமையான search மற்றும் sorting structures இன் அடிப்படை ஆகும்.

நான்கு traversals ஐ புரிந்துகொள்வது அவசியம் — பெரும்பாலான ட்ரீ interview problems அவற்றில் ஒன்றின் மாறுபாடு ஆகும்.

Traversal	Order	Common use
Inorder	L, N, R	sorted output of a BST
Preorder	N, L, R	copy/serialize a tree
Postorder	L, R, N	delete a tree, evaluate expr
Level-order	by depth	BFS, shortest path on tree

Structure

Traversals

இது ஏன் முக்கியமாக இருக்கிறது

தொடர்புடைய கேள்விகள்