# Trees — লাইব্রেরির ক্যাটালগ নতুন করে সাজান

একটি লাইব্রেরিতে নতুন বইয়ের ID আসার ক্রমে BST-তে ঢোকানো হয়েছে। ID-গুলো ক্রমবর্ধমান হলে tree একটি লম্বা শিকলের মতো হয়ে যায়। আপনার কাজ হলো সেই tree থেকে তথ্য উদ্ধার করে একটি balanced BST বানানো, তারপর পাঠকের কয়েকটি প্রশ্নের উত্তর দেওয়া।

**Microsoft কোর্সের সংযোগ:** Module 3-এর tree, traversal ও balanced tree ধারণা। এখানে একবার tree পুনর্গঠন করবেন; AVL/Red–Black tree-এর rotation বাস্তবায়ন এই lab-এর অংশ নয়।

## ১. আগে যা পড়বেন ও করবেন

| ক্রম | পড়া / অনুশীলন | নিজে কী ব্যাখ্যা করতে পারবেন |
|---|---|---|
| ১ | [Tree-এর ধারণা](../07-trees/concept.md), [চিত্র](../07-trees/visual-explanation.md) | Root, child, height ও BST ordering |
| ২ | [Traversal patterns](../07-trees/traversal-patterns.md), [Inorder](../07-trees/problems/002-inorder-traversal.md) | Inorder কেন ছোট থেকে বড় ID দেয় |
| ৩ | [Level order](../07-trees/problems/012-level-order-traversal.md), [Maximum depth](../07-trees/problems/001-maximum-depth.md) | Queue-এর এক round কেন একটি level |
| ৪ | [Validate BST](../07-trees/problems/014-validate-bst.md), [Balanced tree](../07-trees/problems/010-balanced-binary-tree.md) | Local parent-child তুলনা একা যথেষ্ট নয় কেন |
| ৫ | [K-th smallest](../07-trees/problems/015-kth-smallest-bst.md), [LCA of BST](../07-trees/problems/016-lca-of-bst.md) | Ordering দিয়ে কোন subtree বাদ দেবেন |

প্রথমে ২ ও ৩ নম্বর সারির problem নিজে করুন। ৪ ও ৫ নম্বরের ধারণা নিয়ে নিচের lab শুরু করুন; আটকে গেলে সংশ্লিষ্ট explanation-এ ফিরে যান।

## ২. সুনির্দিষ্ট সমস্যা

`catalogue_report(book_ids, low, high, k, pair)` লিখুন।

- `book_ids`-এর ID একই ক্রমে একটি **বাস্তব node-ভিত্তিক BST**-তে insert করুন। সব ID আলাদা।
- পুরোনো tree-এর height মাপুন; height হলো root থেকে deepest leaf পর্যন্ত **node-এর সংখ্যা**।
- Inorder traversal থেকে sorted ID নিন। প্রতি অর্ধখোলা range `[left, right)`-এর `(left + right) // 2` index-কে root করে নতুন balanced BST বানান। জোড় সংখ্যক ID হলে এটি ডানদিকের মাঝের ID বেছে নেয়।
- নতুন tree থেকে inclusive range `[low, high]`-এর বই, ১-ভিত্তিক `k`-তম ছোট ID এবং `pair`-এর দুই ID-এর LCA দিন।
- Sorted ID, আগে/পরের height ও নতুন tree-এর level-গুলোও রিপোর্টে দিন। সব query **নতুন tree**-তে হবে।

**সীমা:** `1 ≤ n ≤ 2,000`, ID ও query bound পূর্ণসংখ্যা, `1 ≤ k ≤ n`, `low ≤ high`; `pair`-এর দুই ID অবশ্যই বইয়ের তালিকায় আছে। একই ID দুইবার query করা যায়। Duplicate বই, ফাঁকা তালিকা বা ভুল query-তে `ValueError` দিন।

এটি Python function-এর input/output সমস্যা; stdin parser বা database লাগবে না। মূল `book_ids` বদলাবেন না।

```python
catalogue_report([10, 20, 30, 40, 50], 20, 45, 3, (10, 20))
```

```python
{
    "ordered": [10, 20, 30, 40, 50],
    "height_before": 5,
    "height_after": 3,
    "levels": [[30], [20, 50], [10, 40]],
    "in_range": [20, 30, 40],
    "kth": 30,
    "lca": 20,
}
```

পুরোনো tree-তে `10 → 20 → 30 → 40 → 50` ডানদিকে নেমেছে। নতুন tree:

```mermaid
flowchart TD
    root["30"] --> left["20"]
    root --> right["50"]
    left --> a["10"]
    right --> b["40"]
```

`10` ও `20`-এর সাধারণ ancestor `20` নিজেই। নতুন tree-এর তিনটি level আছে, তাই height `3`।

## ৩. ধাপে ধাপে নির্মাণ

### ধাপ A — Node ও insertion

`Node(key, left, right)` এবং `insert(root, key)` লিখুন। প্রথম ID root হবে। পরের ID ছোট হলে বামে, বড় হলে ডানে হাঁটুন; প্রথম খালি child-এ নতুন node বসান।

**Invariant:** প্রতিটি node-এর সম্পূর্ণ বাম subtree ছোট, সম্পূর্ণ ডান subtree বড়। Duplicate পেলে থামুন। **Hint:** পুরোনো tree খুব গভীর হতে পারে; insertion-এ loop ব্যবহার করলে Python recursion limit এড়ানো যায়।

**Checkpoint:** `[10, 20, 30]` insert করার পরে `root.right.right.key == 30`; height `3`।

### ধাপ B — পুরোনো tree থেকে তথ্য উদ্ধার

একটি explicit stack দিয়ে inorder এবং queue দিয়ে level order লিখুন। Inorder ফলই পরের ধাপের input; এই lab-এ `sorted(book_ids)` দিয়ে tree traversal এড়াবেন না।

**Invariant:** stack-এ থাকা node-এর বামদিকের কাজ শেষ হলে তবেই node visit হবে। Queue-এর বর্তমান দৈর্ঘ্য ধরে এক round চালালে নতুন child-গুলো পরের level-এ থাকবে।

**Checkpoint:** example-এর inorder `[10, 20, 30, 40, 50]`, পুরোনো level count `5`।

### ধাপ C — মাঝের ID দিয়ে tree পুনর্গঠন

`build(left, right)`-এ খালি range হলে `None`; অন্যথায় middle-এ একটি node বানিয়ে দুই অর্ধে recursion করুন। Slice করে নতুন array বানানোর দরকার নেই।

**Invariant:** recursion-এর প্রতিটি range sorted এবং তার বাইরের ID ওই subtree-তে ঢুকবে না। অর্ধেক অর্ধেক ভাগ হওয়ায় height ছোট হয়।

**Checkpoint:** `[10, 20, 30, 40, 50]` থেকে root `30`; তার right child `50`, `50`-এর left child `40`।

### ধাপ D — পাঠকের query ও চূড়ান্ত রিপোর্ট

Range query-তে `key < low` হলে বাম subtree বাদ দিন। `kth`-এর জন্য inorder visit গুনুন। LCA-তে দুই ID ছোট হলে বামে, দুইটি বড় হলে ডানে; দুই দিকে ভাগ হলে বর্তমান node-ই উত্তর।

**Invariant:** LCA খোঁজার সময় দুই target এখনও বর্তমান subtree-র মধ্যে আছে। Pair-এর সদস্য tree-তে আছে কি না আগে যাচাই করুন।

**Checkpoint:** example-এর range উত্তর তিনটি ID; `kth=30`, `lca=20`। সব ধাপের ফল একই report-এ মিলতে হবে।

## ৪. সমাধান বুঝে মিলিয়ে নিন

??? success "Reference solution-এর যুক্তি"

    পুরোনো tree সত্যিকারের insertion order ধরে, তাই তার height সমস্যাটির অবস্থা দেখায়। Iterative inorder একবার প্রতিটি node visit করে sorted sequence উদ্ধার করে। সেই sequence-এর midpoint দিয়ে node তৈরি করলে প্রতিটি subtree-র আকার কাছাকাছি থাকে।

    Query-গুলোর উত্তর নতুন node-গুলোতে হাঁটেই পাওয়া হয়। শুধু sorted list থেকে সব উত্তর দিলে height, child relation ও LCA শেখা হতো না। LCA-র ক্ষেত্রে ordering দুই target-এর সম্ভাব্য subtree একসঙ্গে ছোট করতে দেয়।

    [সম্পূর্ণ Python solution](../practice/trees_lab.py){ download } এবং [unit test](../practice/test_trees_lab.py){ download }। আগে নিজে ধাপ A–D লিখে তারপর তুলনা করুন।

## ৫. Unit test ও edge case

Repository root থেকে চালান। Download করলে দুই ফাইল `practice/` folder-এ রাখুন।

```bash
python -m unittest discover -s practice -p 'test_trees_lab.py' -v
```

৮টি test method-এ worked example, এক বই, range-এর বাইরে query, duplicate/invalid input, node-ভিত্তিক BST ও balance invariant, ১,২০০ node-এর skewed tree এবং ৮০টি seeded random query যাচাই হয়। Random query-র oracle হিসেবে আলাদা sorted-list filter ব্যবহার করা হয়েছে।

নিজে আরও ভাবুন: `low == high`, `k == n`, দুই target একই node এবং ancestor নিজেই target হলে কী হবে।

## ৬. কী শিখলেন, কী বাকি

| এই lab-এ ব্যবহার | কোথায় | আলাদা করে অনুশীলন দরকার |
|---|---|---|
| BST insertion, ordering | A | Deletion-এর তিনটি case |
| DFS inorder, BFS level order | B | Preorder/postorder construction |
| Balanced shape ও recursion | C | AVL/Red–Black rotation, online balancing |
| Range pruning, k-th, LCA | D | Arbitrary binary-tree LCA, subtree matching |
| Tree-এর গঠন ও height | পুরো report | Diameter, maximum path sum, serialization |

**Complexity:** সাধারণ BST insertion-এর worst case `O(n²)`; এটি ইচ্ছাকৃত, পুরোনো skewed tree তৈরি করতে হবে। Inorder, rebuild ও level report `O(n)`। Rebuilt tree-তে range query `O(log n + r)`, k-th traversal `O(log n + k)`, LCA `O(log n)`; `r` হলো মিলে যাওয়া বইয়ের সংখ্যা। মোট node/report storage `O(n)`।

শেষে [সব tree problem](../07-trees/problems/README.md)-এ ফিরে বাকি pattern আলাদা করে করুন। একটি capstone সেই অনুশীলনের বিকল্প নয়।