Problem link ও উৎস
- **Original source:** Classic binary tree depth exercise
- **Platform:** LeetCode —
- **Topic:** trees
- **Difficulty:** Easy
- **Pattern:** Level order early-exit
- **Basic idea inherited from:** BFS সবচেয়ে কাছেরটা আগে পায় (../../04-stack-and-queue/) — প্রথম যে leaf-এর দেখা মেলে, সেটাই minimum depth
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
তোমাকে একটা binary tree-র root দেওয়া আছে। তোমার কাজ: এর **minimum depth** বের করা — মানে root থেকে সবচেয়ে **কাছের** leaf পর্যন্ত পথে কতগুলো node আছে। (Leaf = যার কোনো child নেই।)
সাবধান: এটা Maximum Depth-এর উল্টোটা **না** — একটা ফাঁদ আছে। যে node-এর একটা মাত্র child আছে, সেটা leaf নয়, তাই তার "না-থাকা" দিকটাকে depth 0 ধরা যাবে না।
```text
2
\
3
\
4 ← এখানে minimum depth = 3 (একমাত্র leaf 4 পর্যন্ত), 1 না
```
### Input ও output {#8-example-input-and-output}
```text
Input : root = [3,9,20,null,null,15,7] -> Output: 2 (leaf 9, depth 2)
Input : root = [2,null,3,null,4] -> Output: 3 (একমাত্র leaf 4)
Input : root = [] -> Output: 0 (খালি tree)
Input : root = [1] -> Output: 1 (একক node, নিজেই leaf)
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
একটা গোলকধাঁধার প্রবেশমুখ থেকে সবচেয়ে কাছের প্রস্থানপথ খোঁজার কথা ভাবো। তুমি যদি সব দিকে **এক সাথে এক পা করে** ছড়িয়ে এগোও (BFS), তাহলে প্রথম যে exit-এ পৌঁছাবে সেটাই নিশ্চিতভাবে সবচেয়ে কাছের। একটা পথ ধরে শেষ পর্যন্ত দৌড়ে গেলে (DFS) হয়তো অনেক দূরের exit-এ আগে পৌঁছে যাবে।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
এটা সরাসরি **BFS / level order**-এর উপর দাঁড়ানো ([../../04-stack-and-queue/](../../04-stack-and-queue/README.md)-এর queue, traversal-patterns.md দেখো)। BFS layer ধরে ধরে, root থেকে দূরত্ব অনুসারে এগোয় — তাই **প্রথম যে leaf-এর দেখা মেলে সেটাই সবচেয়ে কাছের leaf**, আর সঙ্গে সঙ্গে থেমে যাওয়া যায় (early exit)। DFS এভাবে আগে থামতে পারে না, কারণ সে এক দিক একদম গভীরে নেমে যায়।
### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}
লুকানো logic: minimum depth = **প্রথম leaf-এর level**। BFS-এ level গোনা হয় এভাবে:
```text
depth শুরু 0; প্রতিটা সম্পূর্ণ layer শেষে depth += 1
যেই মুহূর্তে একটা node-এর left ও right দুটোই None (leaf) →
সেই node-এর level-ই উত্তর, থেমে যাও
```
DFS-recurrence-এও করা যায়, কিন্তু সেখানে সতর্কতা লাগে: এক child থাকলে শুধু সেই child-এর দিকেই নামতে হবে, `min(0, child)` নেওয়া যাবে না।
### কী দিয়ে তথ্য রাখব {#4-which-data-structure-is-needed}
একটা **FIFO queue** — Python-এ `collections.deque` ([../../04-stack-and-queue/](../../04-stack-and-queue/README.md) দেখো)। BFS-এর engine এটাই: child পেছনে enqueue হয়, সামনে থেকে pop হয়, তাই node-গুলো root থেকে দূরত্ব অনুসারে process হয়।
### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}
queue-র FIFO ধর্ম নিশ্চিত করে কাছের node আগে বেরোয় — তাই প্রথম leaf-ই সবচেয়ে কাছের leaf। stack (DFS) হলে গভীরে চলে যেত আর "কাছের leaf আগে" গ্যারান্টিটা ভেঙে পড়ত। `len(q)` দিয়ে এক layer-এর সীমানা snapshot নিলে কোন depth-এ আছি তা ঠিক রাখা যায়।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
প্রথম সরল চিন্তা: Maximum Depth-এর কোড নিয়ে শুধু `max`-কে `min` বানিয়ে দিই — প্রতিটা node-এ `1 + min(left, right)`।
```text
1) recursion: depth(node) = 1 + min(depth(left), depth(right))
2) None হলে 0 ফেরাও
3) root-এর depth-ই উত্তর
```
### কোথায় বেশি কাজ হচ্ছে {#10-why-brute-force-is-slow}
এই naive `min`-version শুধু slow না, **ভুল উত্তরও দেয়**। যে node-এর একটা child None আর একটা child-subtree আছে, সেখানে `min(0, child)` = 0 নিয়ে নেয় — যেন না-থাকা দিকটা একটা leaf, যা ভুল। (যেমন `[2,null,3]`-এ ভুল করে 1 দিত, ঠিক উত্তর 2।) তাই হয় DFS-এ leaf-শর্ত ঠিকভাবে সামলাতে হয়, নয়তো BFS-এ প্রথম leaf-এ থেমে আগেভাগে শেষ করতে হয়।
### যে বিষয়টি খেয়াল করতে হবে {#11-key-observation}
মূল observation: minimum depth জানতে পুরো tree ঘোরার দরকার নেই — **প্রথম leaf পেলেই উত্তর।** আর BFS layer-by-layer যাওয়ায় প্রথম-দেখা leaf-ই সবচেয়ে কাছের leaf — এই মিলটাই early-exit সম্ভব করে। একটা শাখা গভীর হলেও BFS তাকে আগে ছোঁয় না।
### আরও কম কাজে সমাধান {#12-optimized-intuition}
একটা deque-তে `(node)` রাখো, depth 1 দিয়ে শুরু। প্রতিটা layer পুরো process করো (`size = len(q)` snapshot)। কোনো node-এর `left` ও `right` দুটোই None পেলেই বর্তমান depth ফেরত দাও — থামো। নইলে child enqueue করে পরের layer-এ depth বাড়াও। প্রথম leaf-এর layer-এই function বেরিয়ে যায়।
### ভাবনার পরিবর্তন {#13-thinking-tweak}
**মোচড়:** "depth = কত গভীরে যেতে পারি" ভাবা ছাড়ো; বরং ভাবো **"সবচেয়ে কাছের leaf কোথায়?"** আর "কাছের" শুনলেই BFS — কারণ সে দূরত্ব অনুসারে ছড়ায়, তাই প্রথম hit-ই minimum। `max`→`min` করে DFS চালানোর ফাঁদ এড়িয়ে BFS-এর early-exit-এ যাওয়াই আসল aha।
### ছবিতে বোঝা {#7-visual-explanation}
BFS layer ধরে নামে; প্রথম leaf পেলেই থামে (depth শুরু 1, প্রতি layer-এ বাড়ে):
```text
3 ← depth 1: queue [3], leaf না
/ \
9 20 ← depth 2: 9 leaf? হ্যাঁ! → থামো, উত্তর 2
/ \
15 7 (এই layer আর দেখাই হয় না)
```
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
Input `[3,9,20,null,null,15,7]`:
1. depth 1: queue = [3]। 3-এর left 9, right 20 — leaf না। child enqueue → [9, 20]।
2. depth 2: এই layer process করি। প্রথম pop = 9; 9-এর left ও right দুটোই None → **leaf!** → depth 2 ফেরত।
3. 20 আর তার নিচের layer ছোঁয়াই হলো না → উত্তর **2**।
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```python
from collections import deque
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def build_tree(values):
"""level-order list (None = missing child) থেকে tree বানায়।"""
if not values:
return None
root = TreeNode(values[0])
q = deque([root])
i = 1
while q and i < len(values):
node = q.popleft()
if i < len(values) and values[i] is not None:
node.left = TreeNode(values[i])
q.append(node.left)
i += 1
if i < len(values) and values[i] is not None:
node.right = TreeNode(values[i])
q.append(node.right)
i += 1
return root
def min_depth(root):
if root is None: # খালি tree: 0 node গভীর
return 0
q = deque([root]) # BFS queue (../../04-stack-and-queue/)
depth = 1 # root নিজেই level 1
while q:
size = len(q) # এই layer-এ ঠিক যতগুলো node
for _ in range(size):
node = q.popleft()
if node.left is None and node.right is None: # প্রথম leaf!
return depth # কাছেরটাই, থামো
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
depth += 1 # পুরো layer শেষ, পরের level
return depth # (এখানে পৌঁছানোর কথা না)
# ---- tests ----
assert min_depth(build_tree([3, 9, 20, None, None, 15, 7])) == 2 # leaf 9
assert min_depth(build_tree([2, None, 3, None, 4])) == 3 # একমাত্র leaf 4
assert min_depth(build_tree([])) == 0 # খালি tree
assert min_depth(build_tree([1])) == 1 # একক node
assert min_depth(build_tree([1, 2])) == 2 # root leaf না
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#16-line-by-line-code-explanation}
- `if root is None: return 0` — খালি tree-তে কোনো node নেই, depth 0।
- `q = deque([root])` — BFS queue; root দিয়ে শুরু।
- `depth = 1` — root নিজেই প্রথম level।
- `size = len(q)` — মূল চাল: এই snapshot-টা একটা layer-এর সীমানা ধরে রাখে।
- `if node.left is None and node.right is None: return depth` — প্রথম leaf পাওয়া মাত্র থেমে যাও; BFS-এ এটাই সবচেয়ে কাছের।
- `if node.left: q.append(...)` / `if node.right: ...` — child-দের পরের layer-এর জন্য enqueue।
- `depth += 1` — পুরো layer শেষ হলে তবেই depth বাড়াও।
### Output মিলিয়ে দেখা {#17-output-walkthrough}
`[3,9,20,null,null,15,7]`: depth 2-তে 9 leaf পাওয়া যায় → 2 (dry run-এর সাথে মেলে)। `[2,null,3,null,4]`: 2 আর 3 leaf না (এক child আছে), শুধু 4 leaf → 3। খালি → 0; একক node → 1; `[1,2]` → 2 (root 1 leaf না, leaf 2 depth 2-তে)। সব assert pass, শেষে print: `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#18-time-complexity}
**O(n)** worst case — সব node leaf থেকে দূরে থাকলে পুরো tree ঘুরতে হয়। কিন্তু সাধারণত আগেই থামে: প্রথম leaf-এর level পর্যন্ত মাত্র node দেখা হয়, তাই কাছের leaf থাকলে অনেক কম কাজ।
### অতিরিক্ত জায়গা {#19-space-complexity}
**O(w)** — w = tree-র সবচেয়ে চওড়া level-এর node সংখ্যা (queue-তে এক layer জমে)। worst case-এ O(n) (যেমন পুরো শেষ layer), সরু chain-এ O(1)। (DFS-version হলে O(h) call stack হতো।)
### যে ভুলগুলো এড়াতে হবে {#20-common-mistakes}
- Maximum Depth-এর `max`-কে `min` বানিয়ে দেওয়া → এক-child node-এ `min(0, child)` নিয়ে ভুল ছোট উত্তর।
- `depth` ভুল জায়গায় বাড়ানো (প্রতি node-এ, layer-এ না) → level গণনা গোলমাল।
- খালি tree-তে 0-এর বদলে 1 ফেরানো।
## শেখা ও পরের অনুশীলন {#practice}
### ভিত্তির সঙ্গে সম্পর্ক {#21-which-basic-problem-this-inherits-from}
ভিত্তি: [../../04-stack-and-queue/](../../04-stack-and-queue/README.md)-র queue ও BFS, traversal-patterns.md-র level-order section, আর Maximum Depth (#1)-র depth ধারণা (এখানে min, সাথে leaf-সতর্কতা)। concept.md-র leaf সংজ্ঞাও মনে রাখা জরুরি।
### পরের অনুশীলন {#22-similar-harder-problems}
- Binary Tree Level Order Traversal (একই BFS কঙ্কাল, প্রতি level-এর সব value রাখো) —