# 07 — Trees (Binary Trees and Binary Search Trees)

> **এখান থেকে শুরু করুন:** [সহজ ব্যাখ্যা, শেখার ক্রম ও বাস্তব ব্যবহার](learning-guide.md) → [প্রশ্ন, official link ও স্থানীয় সমাধান](problems/README.md)। [উৎসের তালিকা](source-map.md)-এ reference পাবেন।

Tree-তে এসেই recursion আর party trick থাকে না, স্বাভাবিক ভাষা হয়ে যায়। প্রতিটা tree problem গোপনে একই বাক্য: "এখানে কিছু একটা করো, তারপর আমার left আর right child-এর উপর recursion-কে বিশ্বাস করো।"

## এই data structure-টা কী?

Tree হলো একটা hierarchy: উপরে একটা **root** node, আর বাকি প্রতিটা node ঠিক একটা **parent**-এর নিচে ঝোলে। যে node-গুলোর কোনো child নেই সেগুলো **leaf**। **Binary tree** প্রতিটা node-কে সর্বোচ্চ দুটো child-এ (left আর right) সীমাবদ্ধ করে। **Binary search tree (BST)** এর সাথে একটা ordering-এর প্রতিশ্রুতি যোগ করে: একটা node-এর left subtree-র সবকিছু node-টার চেয়ে ছোট, আর right subtree-র সবকিছু বড়।

```
        8          ← root
       / \
      3   10       ← internal nodes
     / \    \
    1   6   14     ← 1, 6, 14 are leaves (6 has children below in bigger trees)
```

## কেন এটা আছে (কোন ব্যথাটা সারায়)

Array আর linked list সমতল — কিন্তু পৃথিবীটা nested: folder-এর ভেতরে folder, team-এর উপরে manager, subcategory-র উপরে category। Tree এই nesting-টা সরাসরি ধরে রাখে।

এরা একটা গতির সমস্যাও solve করে। Sorted array দেয় O(log n) search কিন্তু O(n) insertion (সবকিছু সরে)। Linked list দেয় O(1) insertion কিন্তু O(n) search। একটা **balanced** BST দেয় O(log n) — search, insert আর delete তিনটাতেই — প্রতি level-এ candidate space অর্ধেক কেটে ফেলে, ঠিক যেন binary search-কে একটা structure বানিয়ে দেওয়া হয়েছে।

## বাস্তব software-এ কোথায় ব্যবহার হয়

- File system: directory-গুলোই tree; `du`, recursive delete আর search এগুলোতে হাঁটে।
- Database: B-tree (BST-র ঝোপালো জ্ঞাতি ভাই) প্রায় প্রতিটা index চালায়।
- HTML/JSON: DOM একটা tree; প্রতিটা render আর query এটা traverse করে।
- Compiler: source code parse হয়ে একটা abstract syntax tree (AST) হয়।
- Autocomplete আর routing table: trie (prefix tree)।
- অনেক language-এর ordered container (যেমন C++ `std::map`) self-balancing BST।

## Prerequisites

- [../06-recursion-and-backtracking/](../06-recursion-and-backtracking/README.md) — এটা ছাড়া চলবেই না। Tree-র code-ই recursion।
- [../04-stack-and-queue/](../04-stack-and-queue/README.md) — iterative traversal explicit stack ব্যবহার করে; level order ব্যবহার করে queue।
- Python-এ class আর `None` (একটা missing child মানে `None`)।

## শেখার আগে কী revise করবে

- Leap of faith: "ধরে নাও subtree-র উপর recursive call-টা ঠিক উত্তর দেয়।"
- Base case: empty tree (`node is None`) tree-দের কাছে তাই, factorial-এর কাছে `n == 0` যা।
- Queue operation (`collections.deque`: `append`, `popleft`)।

## Learning goals

- [ ] Root, leaf, height, আর depth — notes ছাড়া define করা আর ছবিতে প্রতিটা দেখিয়ে দেওয়া।
- [ ] BST property নির্ভুলভাবে বলা (এটা পুরো subtree-কে বাঁধে, শুধু child-দের না)।
- [ ] তিনটা depth-first traversal-ই recursively লেখা, প্রতিটা দুই মিনিটের মধ্যে।
- [ ] Queue দিয়ে level-order traversal লেখা আর stack কেন ভুল হতো তা ব্যাখ্যা করা।
- [ ] তিন-লাইনের recursive function দিয়ে height আর node count বের করা।
- [ ] Balanced tree কেন O(log n) দেয় আর কোন input একটা BST-কে O(n)-এ নামিয়ে দেয় তা ব্যাখ্যা করা।
- [ ] BST সঠিকভাবে validate করা (min/max-bounds পদ্ধতি, children-only ফাঁদটা না)।
- [ ] Diameter-via-height ব্যাখ্যা করা: একটা জিনিস compute করো, ওঠার পথে আরেকটা update করো।

## Problem categories

| Category | One-line idea |
| --- | --- |
| Traversal order | নির্দিষ্ট একটা order-এ প্রতিটা node visit করো (in/pre/post/level) |
| Single-value computation | Height, count, sum, max — child-দের উত্তর জোড়া লাগাও |
| Tree shape / comparison | Same tree, symmetric, invert, subtree-of |
| Path problems | Root-to-leaf sums, longest paths, diameter |
| BST property exploitation | Ordering ব্যবহার করে tree-র অর্ধেকটা skip করো |
| Construction / serialization | Traversal বা string থেকে tree আবার বানাও |

## Practice list

### Easy

| Problem | Source | Pattern |
| --- | --- | --- |
| Maximum Depth of Binary Tree | <https://leetcode.com/problems/maximum-depth-of-binary-tree/> | Single-value computation (height) |
| Binary Tree Inorder Traversal | <https://leetcode.com/problems/binary-tree-inorder-traversal/> | Traversal order |
| Binary Tree Preorder Traversal | <https://leetcode.com/problems/binary-tree-preorder-traversal/> | Traversal order |
| Binary Tree Postorder Traversal | <https://leetcode.com/problems/binary-tree-postorder-traversal/> | Traversal order |
| Invert Binary Tree | <https://leetcode.com/problems/invert-binary-tree/> | Tree shape |
| Same Tree | <https://leetcode.com/problems/same-tree/> | Tree comparison |
| Symmetric Tree | <https://leetcode.com/problems/symmetric-tree/> | Tree comparison (mirrored recursion) |
| Path Sum | <https://leetcode.com/problems/path-sum/> | Path problems |
| Search in a Binary Search Tree | <https://leetcode.com/problems/search-in-a-binary-search-tree/> | BST property |
| Balanced Binary Tree | <https://leetcode.com/problems/balanced-binary-tree/> | Height + verdict combo |

### Medium

| Problem | Source | Pattern |
| --- | --- | --- |
| Binary Tree Level Order Traversal | <https://leetcode.com/problems/binary-tree-level-order-traversal/> | Level order (BFS) |
| Validate Binary Search Tree | <https://leetcode.com/problems/validate-binary-search-tree/> | BST property (bounds) |
| Lowest Common Ancestor of a Binary Search Tree | <https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree/> | BST property + LCA |
| Lowest Common Ancestor of a Binary Tree | <https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/> | LCA (general) |
| Diameter of Binary Tree | <https://leetcode.com/problems/diameter-of-binary-tree/> | Diameter via height |
| Kth Smallest Element in a BST | <https://leetcode.com/problems/kth-smallest-element-in-a-bst/> | Inorder = sorted |
| Construct Binary Tree from Preorder and Inorder Traversal | <https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/> | Construction |
| Binary Tree Right Side View | <https://leetcode.com/problems/binary-tree-right-side-view/> | Level order |
| Path Sum II | <https://leetcode.com/problems/path-sum-ii/> | Path + backtracking |
| Subtree Tree Matching: Subtree of Another Tree | <https://leetcode.com/problems/subtree-of-another-tree/> | Subtree comparison |

### Hard

| Problem | Source | Pattern |
| --- | --- | --- |
| Binary Tree Maximum Path Sum | <https://leetcode.com/problems/binary-tree-maximum-path-sum/> | Diameter idea + values |
| Serialize and Deserialize Binary Tree | <https://leetcode.com/problems/serialize-and-deserialize-binary-tree/> | Preorder construction |
| CSES "Subordinates" | <https://cses.fi/problemset/task/1674> (task name: Subordinates) | Subtree sizes on general trees |
| CSES "Tree Diameter" | <https://cses.fi/problemset/task/1131> (task name: Tree Diameter) | Diameter at CP scale |

## Visualization ideas

- একটা tree এঁকে একই আকৃতিতে চারবার হাঁটো, inorder, preorder, postorder আর level order-এর জন্য visit-গুলোতে নম্বর বসিয়ে — পাশাপাশি তুলনাটা আছে [visual-explanation.md](visual-explanation.md)-তে।
- "Flatten" exercise: ছবির নিচে একটা BST-র inorder output লেখো আর দেখো সেটা sorted হয়ে বেরোয়।
- Height vs balance: 7টা node-কে একবার perfect tree (height 2) আর একবার chain (height 6) হিসেবে আঁকো; দুটোই একই value-গুলোর legal BST, শুধু আলাদা order-এ insert করা।
- Interactive BST insert/search/traversal animation: <https://visualgo.net/en>।

## Common mistakes (সাধারণ ভুল)

- `None` base case ভুলে যাওয়া — tree-র সবচেয়ে common crash।
- BST validate করতে শুধু `left.val < node.val < right.val` (children) check করা, *subtree bounds*-এর বদলে — গভীরের violator-এ fail করে।
- Height (একটা node থেকে নিচের দিকে longest path) আর depth (root থেকে node-এর দূরত্ব) গুলিয়ে ফেলা।
- Level order-এ stack ব্যবহার (DFS order দেয়) বা DFS-এ queue ব্যবহার।
- Shared path list mutate করে pop না করা ([../06-recursion-and-backtracking/](../06-recursion-and-backtracking/README.md)-এর সেই un-choose শিক্ষা)।
- Height-এ off-by-one: empty tree-র height -1 না 0, একবার ঠিক করো আর consistent থাকো।
- ধরে নেওয়া যে BST balanced — sorted insertion order একটা chain বানায় আর operation হয়ে যায় O(n)।

## Interview problem-এর সাথে connection

Big-tech style interview-তে tree-ই সবচেয়ে ভরসাযোগ্যভাবে জিজ্ঞেস করা data structure: traversal, depth, validate-BST, LCA আর diameter মিলে এমন একটা core set যেটা অগুনতি loop-এ আসে। এরা একসাথে ঠিক দুটো skill পরীক্ষা করে — recursion-এ সাবলীলতা, আর প্রতিটা call কী return করে তা define করার শৃঙ্খলা। Diameter আর maximum-path-sum এর সাথে যোগ করে interview-র signature মোচড়টা: একটা quantity (height) compute করতে করতে আরেকটা (best path) ওঠার পথে update করা।

## Competitive programming-এর সাথে connection

- CP-র tree সাধারণত GENERAL tree, edge list হিসেবে দেওয়া; একই recursion adjacency list-এর উপর DFS হিসেবে চলে (subtree size, depth)। CSES Tree Algorithms section: <https://cses.fi/problemset/>।
- Python-এর ~1000-frame recursion limit n = 2·10^5 chain-এ কামড় দেয় — iterative/stack rewrite শেখো বা limit বাড়াও।
- Tree DP (child-দের উত্তর জোড়া লাগানো) আর Euler tour সরাসরি এখানে শেখানো postorder pattern থেকেই গজায়; গভীর theory আছে <https://cp-algorithms.com/>-এ।

## Recommended learning order

1. [concept.md](concept.md) — vocabulary, family-tree analogy, BST-র প্রতিশ্রুতি, log n কেন।
2. [visual-explanation.md](visual-explanation.md) — একটা tree, চারটা traversal walk, ধাপে ধাপে আঁকা।
3. [traversal-patterns.md](traversal-patterns.md) — কখন কোন traversal সঠিক tool + বড় tree pattern-গুলো।
4. [implementation.py](implementation.py) — চালাও; TreeNode, চারটা traversal, height, BST insert/search/validate।
5. [problems/README.md](problems/README.md) — practice ladder, easy থেকে hard।

## Source map

এই folder-এর সব source, link আর copying status: দেখো [source-map.md](./source-map.md)।