# Tree traversal — একই গাছ, চারভাবে পড়া

[অধ্যায়ের সূচি](README.md) · [সহজ ব্যাখ্যা ও বাস্তব ব্যবহার](learning-guide.md) · [অনুশীলন ও সমাধান](problems/README.md)

এই ছয়টি node-ই প্রতিবার থাকবে। বদলাবে শুধু **কখন একটি node-এর value উত্তরে লিখব**। এটি একটি binary search tree (BST): বাম subtree-র মান ছোট, ডান subtree-র মান বড়।

```mermaid
flowchart TD
  n8((8)) -->|বাম| n3((3))
  n8 -->|ডান| n10((10))
  n3 -->|বাম| n1((1))
  n3 -->|ডান| n6((6))
  n10 -->|ডান| n14((14))
```

## চারটি traversal এক নজরে

নিচের প্রতিটি বাক্স একটি visit। বাক্সের ক্রমই সম্পূর্ণ output; কোনো node বাদ যায়নি।

```dsa
kind: array
title: একই tree-এর চারটি output
steps:
  - label: Inorder — বাম, নিজে, ডান
    values: [1, 3, 6, 8, 10, 14]
    indices: false
    note: BST হওয়ায় মানগুলো ছোট থেকে বড় হয়েছে।
  - label: Preorder — নিজে, বাম, ডান
    values: [8, 3, 1, 6, 10, 14]
    indices: false
    note: Parent-এর পরে তার সন্তানগুলো আসে।
  - label: Postorder — বাম, ডান, নিজে
    values: [1, 6, 3, 14, 10, 8]
    indices: false
    note: দুই subtree শেষ হওয়ার পরে parent আসে।
  - label: Level order — এক স্তর শেষ করে পরের স্তর
    values: [8, 3, 10, 1, 6, 14]
    indices: false
    note: স্তরগুলো হলো 8; তারপর 3 ও 10; শেষে 1, 6 ও 14।
```

| Traversal | Value লেখার সময় | কোথায় কাজে লাগে |
| --- | --- | --- |
| Inorder | বাম subtree শেষ হলে | BST-এর মান sorted order-এ পড়া |
| Preorder | node-এ পৌঁছেই | Tree copy, structure-সহ serialization |
| Postorder | দুই subtree শেষ হলে | Height, subtree sum, child-এর ফল জোড়া দেওয়া |
| Level order | queue থেকে বের করলে | প্রতি level-এর তথ্য, নিকটতম node খোঁজা |

সাধারণ binary tree-তে inorder করলেই sorted output আসে না; এর জন্য **BST-এর নিয়ম** দরকার। আর শুধু preorder value দিয়ে সাধারণ binary tree পুনর্গঠন করা যায় না—অনুপস্থিত child বোঝাতে null marker বা অন্য structure-তথ্য লাগে। [Serialization-এর পূর্ণ নোট](problems/024-serialize-deserialize.md)।

## Inorder-এ ফিরে আসার মুহূর্তটি ধরো

প্রথমে 8 থেকে বাঁয়ে 3, তারপর বাঁয়ে 1-এ নামি। কোনো subtree শেষ হলে যে node থেকে এসেছিলাম সেখানে ফিরে যাই।

| Visit | তার আগে কী শেষ হলো | এখন লেখা value | এরপর |
| --- | --- | --- | --- |
| 1 | 1-এর বাম child নেই | 1 | 1-এর ডান child-ও নেই; 3-এ ফিরি |
| 2 | 3-এর বাম subtree | 3 | ডান child 6-এ যাই |
| 3 | 6-এর বাম child নেই | 6 | 6 শেষ; 3 হয়ে 8-এ ফিরি |
| 4 | 8-এর পুরো বাম subtree | 8 | ডান child 10-এ যাই |
| 5 | 10-এর বাম child নেই | 10 | ডান child 14-এ যাই |
| 6 | 14-এর বাম child নেই | 14 | আর কোনো কাজ বাকি নেই |

তিনটি depth-first traversal-এ যাওয়া-ফেরার পথ একই। Preorder পৌঁছানোর সময়, inorder দুই subtree-র মাঝখানে এবং postorder ফেরার আগে value লেখে।

| Node | Inorder-এ অবস্থান | Preorder-এ অবস্থান | Postorder-এ অবস্থান |
| --- | --- | --- | --- |
| 8 | 4 | 1 | 6 |
| 3 | 2 | 2 | 3 |
| 1 | 1 | 3 | 1 |
| 6 | 3 | 4 | 2 |
| 10 | 5 | 5 | 5 |
| 14 | 6 | 6 | 4 |

## Level order-এ queue কেন লাগে

[Queue](../04-stack-and-queue/README.md)-এর সামনে থেকে একটি node নিই, তারপর তার বাম ও ডান child পেছনে যোগ করি। নিচে queue-এর **বাম দিক front**।

| ধাপ | বের হলো | পেছনে যোগ হলো | কাজের পরে queue |
| --- | --- | --- | --- |
| শুরু | — | 8 | `[8]` |
| 1 | 8 | 3, 10 | `[3, 10]` |
| 2 | 3 | 1, 6 | `[10, 1, 6]` |
| 3 | 10 | 14 | `[1, 6, 14]` |
| 4 | 1 | কিছু নেই | `[6, 14]` |
| 5 | 6 | কিছু নেই | `[14]` |
| 6 | 14 | কিছু নেই | `[]` |

পরের level-এর child-গুলো পেছনে থাকে। তাই বর্তমান level শেষ না করে পরের level শুরু হতে পারে না। Stack ব্যবহার করলে এই ক্রম থাকবে না; তখন একটি পথ ধরে গভীরে যাওয়া হবে।

## Postorder দিয়ে height হিসাব

এখানে height মানে নিচের সবচেয়ে দূরের leaf পর্যন্ত **edge-এর সংখ্যা**। খালি subtree-র height `−1`, leaf-এর height `0`। প্রতিটি parent-এর সূত্র: `1 + max(left_height, right_height)`।

```mermaid
flowchart BT
  n1["1: height 0"] --> n3["3: 1 + max(0, 0) = 1"]
  n6["6: height 0"] --> n3
  n14["14: height 0"] --> n10["10: 1 + max(-1, 0) = 1"]
  n3 --> n8["8: 1 + max(1, 1) = 2"]
  n10 --> n8
```

এই ছবির arrow **হিসাবের ফল উপরে যাওয়া** বোঝায়। আগে 1 ও 6-এর ফল পেয়ে 3-এর height, আগে 14-এর ফল পেয়ে 10-এর height, সবশেষে 8-এর height হিসাব করি। এটাই postorder কাজে লাগার কারণ।

## নিজে যাচাই করো

1. Root 8-এর ডান child 10-এর বদলে 9 হলে কোন output বদলাবে? নিজে চারটি traversal লেখো।
2. 6-এর নিচে নতুন child যোগ হলে কোন কোন node-এর height আবার হিসাব করতে হবে?
3. প্রতি level-এর সর্বোচ্চ মান পেতে কোন traversal নেবে, এবং কেন?

পরের পাঠ: [Traversal patterns](traversal-patterns.md)—প্রশ্ন দেখে সঠিক traversal বেছে নেওয়া।