07 — Trees (Binary Trees and Binary Search Trees)¶
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/— এটা ছাড়া চলবেই না। Tree-র code-ই recursion।../04-stack-and-queue/— 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¶
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 name: Subordinates) | Subtree sizes on general trees |
| CSES "Tree Diameter" | https://cses.fi/problemset/ (task name: Tree Diameter) | Diameter at CP scale |
Visualization ideas¶
- একটা tree এঁকে একই আকৃতিতে চারবার হাঁটো, inorder, preorder, postorder আর level order-এর জন্য visit-গুলোতে নম্বর বসিয়ে — পাশাপাশি তুলনাটা আছে
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 (সাধারণ ভুল)¶
Nonebase 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/-এর সেই 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¶
concept.md— vocabulary, family-tree analogy, BST-র প্রতিশ্রুতি, log n কেন।visual-explanation.md— একটা tree, চারটা traversal walk, ধাপে ধাপে আঁকা।traversal-patterns.md— কখন কোন traversal সঠিক tool + বড় tree pattern-গুলো।implementation.py— চালাও; TreeNode, চারটা traversal, height, BST insert/search/validate।problems/README.md— practice ladder, easy থেকে hard।
Source map¶
এই folder-এর সব source, link আর copying status: দেখো source-map.md।