011 — Minimum Depth of Binary Tree¶

Source¶

Original source: Classic binary tree depth exercise
Platform: LeetCode — https://leetcode.com/problems/minimum-depth-of-binary-tree/
Topic: trees
Difficulty: Easy
Pattern: Level order early-exit
Basic idea inherited from: BFS সবচেয়ে কাছেরটা আগে পায় (../../04-stack-and-queue/) — প্রথম যে leaf-এর দেখা মেলে, সেটাই minimum depth

1. Problem in simple words¶

তোমাকে একটা binary tree-র root দেওয়া আছে। তোমার কাজ: এর minimum depth বের করা — মানে root থেকে সবচেয়ে কাছের leaf পর্যন্ত পথে কতগুলো node আছে। (Leaf = যার কোনো child নেই।)

সাবধান: এটা Maximum Depth-এর উল্টোটা না — একটা ফাঁদ আছে। যে node-এর একটা মাত্র child আছে, সেটা leaf নয়, তাই তার "না-থাকা" দিকটাকে depth 0 ধরা যাবে না।

    2
     \
      3
       \
        4        ← এখানে minimum depth = 3 (একমাত্র leaf 4 পর্যন্ত), 1 না

2. Which basic idea does this inherit from?¶

এটা সরাসরি BFS / level order-এর উপর দাঁড়ানো (../../04-stack-and-queue/-এর 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 গোনা হয় এভাবে:

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/ দেখো)। 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-এ আছি তা ঠিক রাখা যায়।

6. Real-life analogy¶

একটা গোলকধাঁধার প্রবেশমুখ থেকে সবচেয়ে কাছের প্রস্থানপথ খোঁজার কথা ভাবো। তুমি যদি সব দিকে এক সাথে এক পা করে ছড়িয়ে এগোও (BFS), তাহলে প্রথম যে exit-এ পৌঁছাবে সেটাই নিশ্চিতভাবে সবচেয়ে কাছের। একটা পথ ধরে শেষ পর্যন্ত দৌড়ে গেলে (DFS) হয়তো অনেক দূরের exit-এ আগে পৌঁছে যাবে।

7. Visual explanation¶

BFS layer ধরে নামে; প্রথম leaf পেলেই থামে (depth শুরু 1, প্রতি layer-এ বাড়ে):

        3            ← depth 1: queue [3], leaf না
       / \
      9   20         ← depth 2: 9 leaf? হ্যাঁ! → থামো, উত্তর 2
         /  \
        15   7       (এই layer আর দেখাই হয় না)

8. Example input and output¶

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)

9. Brute force thinking¶

প্রথম সরল চিন্তা: Maximum Depth-এর কোড নিয়ে শুধু max-কে min বানিয়ে দিই — প্রতিটা node-এ 1 + min(left, right)।

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।

14. Step-by-step dry run¶

Input [3,9,20,null,null,15,7]:

depth 1: queue = [3]। 3-এর left 9, right 20 — leaf না। child enqueue → [9, 20]।
depth 2: এই layer process করি। প্রথম pop = 9; 9-এর left ও right দুটোই None → leaf! → depth 2 ফেরত।
20 আর তার নিচের layer ছোঁয়াই হলো না → উত্তর 2।

15. Python solution¶

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 বাড়াও।

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!।

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 ফেরানো।

21. Which basic problem this inherits from¶

ভিত্তি: ../../04-stack-and-queue/-র 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 রাখো) — https://leetcode.com/problems/binary-tree-level-order-traversal/ (এই tracker-এর #12)
Maximum Depth of Binary Tree (max, leaf-ফাঁদ ছাড়া) — https://leetcode.com/problems/maximum-depth-of-binary-tree/ (#1)
Binary Tree Right Side View (level-order, প্রতি level-এর শেষ node) — https://leetcode.com/problems/binary-tree-right-side-view/ (#13)

23. Pattern learned¶

Level-order early-exit (BFS): "nearest" বা "shortest" প্রশ্নে layer-by-layer BFS চালাও, প্রথম target (এখানে leaf) পাওয়া মাত্র থেমে যাও — সেটাই minimum। FIFO queue কাছেরটাকে আগে আনে।

24. Final summary¶

ভবিষ্যতের আমাকে: "Minimum depth = প্রথম leaf-এর level; BFS দিয়ে layer ধরে নামো, প্রথম leaf পেলেই থামো।" "nearest", "shortest", "minimum depth" শুনলেই BFS early-exit মনে পড়বে — আর max→min DFS-এর leaf-ফাঁদ মাথায় রাখবে। মূল চাবি: কাছের জিনিস চাইলে দূরত্ব অনুসারে ছড়াও।

মনে রাখার নিয়ম (legal): সব নিজের ভাষায় লেখা; problem statement copy করা হয়নি; official link শুধু attribution-এর জন্য; "asked by Google/Amazon" দাবি নেই — এটা একটা common interview pattern।