# Tree: গঠন দেখে সঠিক traversal বেছে নেওয়া

[অধ্যায়ের সূচি](README.md) · [অনুশীলন ও সমাধান](problems/README.md) · [মূল ধারণা](concept.md)

একটি tree-তে তথ্যের সঙ্গে **কে কার নিচে আছে** সেটিও রাখা হয়। Folder-এর মোট আকার জানতে তার ভেতরের সব file ও subfolder-এর আকার লাগে। আবার folder-এর পূর্ণ path বানাতে আগে parent-এর path জানতে হয়। একই tree, কিন্তু কাজের ক্রম আলাদা। এই পার্থক্য বুঝলেই traversal মুখস্থ করার প্রয়োজন কমে যায়।

## কোন ক্রমে পড়বেন

| ধাপ | পড়া | পড়ে কী করতে পারবেন |
| --- | --- | --- |
| 1 | [Node, edge, depth, height](concept.md) | একটি node-এর depth ও height আলাদা করে গুনতে |
| 2 | [Traversal-এর সম্পূর্ণ ছবি](visual-explanation.md) | preorder, inorder, postorder ও level order হাতে লিখতে |
| 3 | [Traversal বাছার নিয়ম](traversal-patterns.md) | প্রশ্ন দেখে parent আগে লাগবে, না child আগে লাগবে বুঝতে |
| 4 | [চলমান Python উদাহরণ](implementation.py) | খালি tree, এক node ও একদিকে ঝুঁকে থাকা tree পরীক্ষা করতে |
| 5 | [অনুশীলনের তালিকা](problems/README.md) | মূল প্রশ্ন ও ব্যাখ্যা পাশাপাশি খুলে সমাধান করতে |

## একটি প্রোগ্রাম: folder-এর মোট আকার

ধরি file-এর আকার নিচের ছবিতে দেওয়া আছে। Folder নিজের জন্য আলাদা আকার যোগ করবে না; শুধু children-এর মোট ফেরত দেবে।

```mermaid
flowchart TD
  root["project / মোট 14 KB"] --> src["src / মোট 9 KB"]
  root --> readme["README.md / 5 KB"]
  src --> main["main.py / 6 KB"]
  src --> helper["helper.py / 3 KB"]
```

| শেষ হওয়া কাজ | কী জানা গেল | পরের ধাপ |
| --- | --- | --- |
| main.py পড়া | 6 KB | src-এর অন্য child দেখুন |
| helper.py পড়া | 3 KB | src = 6 + 3 = 9 KB |
| src ফেরত এলো | 9 KB | project-এর README পড়ুন |
| README.md পড়া | 5 KB | project = 9 + 5 = 14 KB |

এটি **postorder**: children-এর উত্তর পাওয়ার পরে parent-এর উত্তর। File system-এর বাস্তব symlink cycle তৈরি করতে পারে; এই উদাহরণে symlink অনুসরণ করা হচ্ছে না।

```python
def total_size(node):
    if "size" in node:        # file
        return node["size"]
    return sum(total_size(child) for child in node["children"])

project = {"children": [
    {"children": [{"size": 6}, {"size": 3}]},
    {"size": 5},
]}
assert total_size(project) == 14
```

প্রতিটি node একবার দেখা হয়, তাই সময় `O(n)`। Recursion stack-এ একসঙ্গে একটি root-to-leaf path থাকে, তাই অতিরিক্ত space `O(h)`; chain হলে `h` বেড়ে `n` হতে পারে।

## প্রশ্ন থেকে traversal

| প্রোগ্রামের কাজ | কী আগে দরকার | পছন্দ |
| --- | --- | --- |
| Menu-র প্রতিটি item-এর পূর্ণ path | Parent-এর path | Preorder; path নিচে পাঠান |
| Folder-এর মোট size বা expression-এর value | Children-এর উত্তর | Postorder; উত্তর উপরে ফেরান |
| Organization chart-এর প্রতি স্তরের মানুষ | একই depth-এর সব node | Queue দিয়ে level order |
| BST থেকে ascending report | ছোট → বর্তমান → বড় | Inorder |
| সাধারণ binary tree থেকে ascending report | BST ordering নেই | Values সংগ্রহ করে sort; শুধু inorder যথেষ্ট নয় |

## একটি শর্ত পুরো subtree-তে প্রযোজ্য

```mermaid
flowchart TD
  a["8"] --> b["3"]
  a --> c["10"]
  b --> d["1"]
  b --> e["9: ভুল অবস্থান"]
```

`9 > 3` হওয়ায় parent-child তুলনা ঠিক মনে হচ্ছে। কিন্তু 9 রয়েছে 8-এর **বাঁ subtree-তে**, যেখানে সব value 8-এর ছোট হতে হবে। তাই validation-এ `(low, high)` সীমা নিচে পাঠাতে হয়। [Validate BST-এর নোট](problems/014-validate-bst.md) খোলার আগে নিজে বলুন: 9-এর জন্য সীমা কত? উত্তর `(3, 8)`।

পরের ধাপে [পূর্ণ অনুশীলন তালিকা](problems/README.md) থেকে traversal, depth, validation এবং LCA ক্রমে নিন। একটি traversal-এর output দেখে সাধারণ tree-এর গঠন সবসময় ফেরত পাওয়া যায় না; serialization-এ missing child-এর marker দরকার।