# Trees — The Concept [অধ্যায়ের সূচি](README.md) · [সহজ ব্যাখ্যা ও বাস্তব ব্যবহার](learning-guide.md) · [অনুশীলন ও সমাধান](problems/README.md) ## একটা বাস্তব জীবনের analogy দিয়ে শুরু করি তোমার computer-এর file explorer খোলো। উপরে একটাই folder। তার ভেতরে: file আর আরো folder। সেগুলোর ভেতরে: file আর আরো folder। এই nesting-টা — প্রতিটা জিনিসের ঠিক একটা container, আর container-গুলো অনেক জিনিস ধরে — এটাই একটা tree। অথবা genealogy-র কায়দায় আঁকা একটা family tree কল্পনা করো: উপরে এক পূর্বপুরুষ, নিচে সন্তানেরা, তাদের নিচে নাতি-নাতনিরা। ছবিতে প্রতিটা মানুষের (সবার উপরের পূর্বপুরুষ বাদে) ঠিক একজন parent। Tree-র vocabulary আক্ষরিক অর্থেই এই ছবি থেকে ধার করা: parent, child, sibling, ancestor, descendant। মূল অনুভূতিটা: tree হলো **one-to-many, কোনো cycle নেই**। একটা folder কখনো নিজের ভেতরে থাকে না; তুমি নিজের দাদা হতে পারো না। ## এক ছবিতে পুরো vocabulary ``` (A) ← ROOT: the one node with no parent / \ (B) (C) ← B and C are CHILDREN of A; A is their PARENT / \ \ B and C are SIBLINGS (D) (E) (F) ← D, E, F: LEAVES (no children) ``` - **Node**: একটা গোলক। একটা value আর child-দের link ধরে রাখে। - **Edge**: parent আর child-এর মাঝের দাগ। n-টা node-এর tree-তে সবসময় ঠিক n - 1টা edge। - **Root**: একমাত্র উপরের node (A)। - **Leaf**: যে node-এর কোনো child নেই (D, E, F)। - **Depth of a node**: ROOT থেকে তার পর্যন্ত edge-এর সংখ্যা। depth(A)=0, depth(B)=1, depth(D)=2। - **Height of a node**: তার থেকে নিচে কোনো leaf পর্যন্ত LONGEST path-এর edge-এর সংখ্যা। height(D)=0, height(B)=1, height(A)=2। Tree-র height = root-এর height। - **Subtree**: যেকোনো node আর তার নিচের সবকিছু। B-র subtree নিজেই একটা সম্পূর্ণ ছোট tree — এই self-similarity-র কারণেই recursion নিখুঁত খাপ খায়। Depth মাপে উপর থেকে; height মাপে নিচ পর্যন্ত। এ দুটো গুলিয়ে ফেলাই classic vocabulary bug। ## Memory-র ছবি: একটা node আসলে কী Binary tree-র node মানে শুধু একটা value আর দুটো reference: ``` class TreeNode: one node in memory: def __init__(self, val): self.val = val ┌─────────────┐ self.left = None │ val: 8 │ self.right = None │ left: ●───┼──► (node 3 (left child)) │ right: ●───┼──► (node 10 (right child)) └─────────────┘ ``` পুরো tree মানে memory-তে ছড়িয়ে থাকা node, এই reference-গুলো দিয়ে সেলাই করা — হুবহু linked list-এর মতো, শুধু প্রতিটা node সর্বোচ্চ দুটো node-এর দিকে নিচে point করে। কোনো বড় contiguous block নেই; প্রতিটা missing child-কে `None` চিহ্নিত করে। ``` ┌───────┐ │ 8 │ └─┬───┬─┘ left │ │ right ┌─────▼┐ ┌▼──────┐ │ 3 │ │ 10 │ └┬────┬┘ └─┬────┬┘ ┌▼┐ ┌▼┐ (None) ┌▼─┐ │1│ │6│ │14│ leaves: left=None, right=None └─┘ └─┘ └──┘ ``` ## Binary tree vs binary search tree **Binary tree** শুধু প্রতিশ্রুতি দেয় "সর্বোচ্চ দুটো child।" Value যেখানে খুশি বসতে পারে। **Binary search tree (BST)** এর সাথে ordering invariant-টা যোগ করে: > প্রতিটা node-এর জন্য: তার **left subtree**-র সব value কঠোরভাবে ছোট, আর **right subtree**-র সব value কঠোরভাবে বড়। ``` A valid BST: NOT a BST (looks fine locally!): 8 8 / \ / \ 3 10 3 10 / \ \ / \ \ 1 6 14 1 9 14 ▲ 9 > 8 but sits in 8's LEFT subtree. Each parent-child pair is ordered, yet the WHOLE-SUBTREE rule is broken. ``` ডানদিকের ফাঁদটার জন্যই "validate BST" এত বিখ্যাত interview question: নিয়মটা পুরো subtree-কে বাঁধে, শুধু সরাসরি child-দের না। সঠিক validation recursion-এর নিচে (low, high) bounds পাঠিয়ে দেয় — দেখো [implementation.py](implementation.py)। ## Core invariants 1. ঠিক একটা root; বাকি প্রতিটা node-এর ঠিক একটা parent। 2. কোনো cycle নেই — child link ধরে গেলে কোনো node-এ দ্বিতীয়বার ফেরা যায় না। 3. n-টা node ⇒ n - 1টা edge। 4. প্রতিটা subtree নিজেই একটা valid tree (recursion-এর আইনি ভিত্তি)। 5. শুধু BST-তে: left subtree < node < right subtree, প্রতিটা node-এ। ## Tree কেন O(log n) দেয় — যখন balanced উপরের BST-তে 15 খোঁজা: 15 > 8 → ডানে যাও (পুরো বাঁ অর্ধেক — 3, 1, 6 — না তাকিয়েই বাদ)। 15 > 10 → ডানে। 15 vs 14 → not found। ছয়টি node-এর মধ্যে তিনটির সঙ্গে তুলনা করেই অনুসন্ধান শেষ। একটি perfect binary tree-তে প্রতিটি level সম্পূর্ণ ভরা থাকে; তাই প্রতি level-এ node-এর সংখ্যা দ্বিগুণ হয়। শুধু full binary tree বললে এই শর্ত নিশ্চিত হয় না: ``` level 0: 1 node level 1: 2 nodes level 2: 4 nodes level 3: 8 nodes 4 levels: 1 + 2 + 4 + 8 = 15 nodes h + 1 filled levels: 2^(h+1) - 1 nodes 20 filled levels: 2^20 - 1 = 1,048,575 nodes ``` Search প্রতি level-এ একটা node হাঁটে, তাই balanced BST উত্তর দেয় O(log n)-এ — binary search, structure-এর রূপ নিয়ে, কিন্তু সাথে O(log n) insert আর delete-ও (sorted array সেটা দিতে পারে না)। **ফাঁকটা:** balance ফ্রি না। একটা naive BST-তে 1, 2, 3, 4, 5 ক্রম অনুযায়ী insert করো: ``` 1 \ 2 \ 3 ← a chain. Height n-1. Every operation O(n). \ A "tree" cosplaying as a linked list. 4 ``` Self-balancing tree (AVL, Red-Black — পরের topic) node rotate করে height-কে যেকোনো insertion order-এ O(log n) রাখে। এই folder-এর জন্য শুধু জানো: BST-র complexity বলে "O(h)", আর h-এর range log n (balanced) থেকে n (chain)। ## কখন tree ব্যবহার করবে - Data সত্যিকারের hierarchical: file system, org chart, parse করা document, game state। - Sorted-order operation দরকার সাথে fast update-ও: range query, predecessor/successor, k-th smallest (BST এখানে জ্বলে; hash map order পারেই না)। - Divide-by-structure recursion problem-এ খাপ খায় (expression evaluation, decision tree)। ## কখন tree ব্যবহার করবে না - শুধু exact-key lookup, কোনো ordering লাগে না → [../05-hashing/](../05-hashing/README.md) সহজ আর average-এ দ্রুত। - Data সমতল আর index দিয়ে address করা → array। - শুধু বারবার min বা max দরকার → heap একটা হালকা, array-backed tree। - Time pressure-এ Python-এ হাতে balanced BST বানাতে যাচ্ছ → `sorted` container ব্যবহার করো বা নতুন করে ভাবো; interview-তে হাতে-বানানো balancing-এর দাম প্রায় কখনোই ওঠে না। ## Complexity table | Operation | Balanced BST | Degenerate BST (chain) | Any binary tree | | --- | --- | --- | --- | | Search | O(log n) | O(n) | O(n) (কাজে লাগানোর মতো order নেই) | | Insert | O(log n) | O(n) | — | | Delete | O(log n) | O(n) | — | | Min / Max | O(log n) | O(n) | O(n) | | Full traversal | O(n) | O(n) | O(n) | | Space | O(n) | O(n) | O(n) | | Recursion stack | O(log n) | O(n) | O(height) | ## Dry run সহ ছোট্ট snippet ### 1. Height — tree recursion-এর আদিরূপ ```python def height(node): if node is None: # empty tree: height -1 by convention return -1 return 1 + max(height(node.left), height(node.right)) ``` উপরের 8/3/10 tree-তে dry run: height(1)=1+max(-1,-1)=0, height(6)=0 → height(3)=1+max(0,0)=1; height(14)=0 → height(10)=1+max(-1,0)=1; height(8)=1+max(1,1)=2। উত্তরগুলো হুবহু factorial-এর unwind-এর মতো বুদবুদ হয়ে উপরে ওঠে। ### 2. Node গোনা ```python def count(node): if node is None: return 0 return 1 + count(node.left) + count(node.right) ``` Dry run, 3-এর subtree: count(1)=1, count(6)=1 → count(3)=1+1+1=3। বাক্যের মতো পড়ো: "আমি, plus আমার বাঁয়ের সবাই, plus আমার ডানের সবাই।" ### 3. BST search — প্রতি step-এ tree-র অর্ধেক হাওয়া ```python def bst_search(node, target): if node is None or node.val == target: return node if target < node.val: return bst_search(node.left, target) return bst_search(node.right, target) ``` Dry run, target 6: 8-এ, 6 < 8 → বাঁয়ে (10-এর পুরো subtree ছোঁয়াই হলো না); 3-এ, 6 > 3 → ডানে; 6-এ → পাওয়া গেছে। ছয়টা node-এর মধ্যে তিনটা visit। ## এক বাক্যের সারমর্ম Tree হলো self-similar nesting — প্রতিটা node তার নিজের ছোট tree-র root — তাই প্রতিটা tree algorithm-এর recipe: `None` সামলাও, এই node-এর ছোট কাজটা করো, আর left আর right-এর জন্য leap of faith নাও। পরের file: [visual-explanation.md](./visual-explanation.md) — একটা tree, চারটা traversal walk, প্রতিটা চাল ধরে ধরে আঁকা।