কনটেন্টে যান

011 — Minimum Depth of Binary Tree

অধ্যায় · সমস্ত অনুশীলন ও উৎস · ধাপে ধাপে শেখা

Problem link ও উৎস

  • 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

প্রশ্ন ও উদাহরণ

সহজ করে প্রশ্ন

তোমাকে একটা 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 না

Input ও 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)

চেনা উদাহরণে বোঝা

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

ভিত্তির ধারণা

আগের কোন ধারণাটি লাগবে

এটা সরাসরি BFS / level order-এর উপর দাঁড়ানো (../../04-stack-and-queue/-এর queue, traversal-patterns.md দেখো)। BFS layer ধরে ধরে, root থেকে দূরত্ব অনুসারে এগোয় — তাই প্রথম যে leaf-এর দেখা মেলে সেটাই সবচেয়ে কাছের leaf, আর সঙ্গে সঙ্গে থেমে যাওয়া যায় (early exit)। DFS এভাবে আগে থামতে পারে না, কারণ সে এক দিক একদম গভীরে নেমে যায়।

ভেতরের যুক্তি

লুকানো 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) নেওয়া যাবে না।

কী দিয়ে তথ্য রাখব

একটা FIFO queue — Python-এ collections.deque (../../04-stack-and-queue/ দেখো)। BFS-এর engine এটাই: child পেছনে enqueue হয়, সামনে থেকে pop হয়, তাই node-গুলো root থেকে দূরত্ব অনুসারে process হয়।

এটি কেন উপযুক্ত

queue-র FIFO ধর্ম নিশ্চিত করে কাছের node আগে বেরোয় — তাই প্রথম leaf-ই সবচেয়ে কাছের leaf। stack (DFS) হলে গভীরে চলে যেত আর "কাছের leaf আগে" গ্যারান্টিটা ভেঙে পড়ত। len(q) দিয়ে এক layer-এর সীমানা snapshot নিলে কোন depth-এ আছি তা ঠিক রাখা যায়।

ধাপে ধাপে সমাধান

প্রথম সরল উপায়

প্রথম সরল চিন্তা: 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-ই উত্তর

কোথায় বেশি কাজ হচ্ছে

এই naive min-version শুধু slow না, ভুল উত্তরও দেয়। যে node-এর একটা child None আর একটা child-subtree আছে, সেখানে min(0, child) = 0 নিয়ে নেয় — যেন না-থাকা দিকটা একটা leaf, যা ভুল। (যেমন [2,null,3]-এ ভুল করে 1 দিত, ঠিক উত্তর 2।) তাই হয় DFS-এ leaf-শর্ত ঠিকভাবে সামলাতে হয়, নয়তো BFS-এ প্রথম leaf-এ থেমে আগেভাগে শেষ করতে হয়।

যে বিষয়টি খেয়াল করতে হবে

মূল observation: minimum depth জানতে পুরো tree ঘোরার দরকার নেই — প্রথম leaf পেলেই উত্তর। আর BFS layer-by-layer যাওয়ায় প্রথম-দেখা leaf-ই সবচেয়ে কাছের leaf — এই মিলটাই early-exit সম্ভব করে। একটা শাখা গভীর হলেও BFS তাকে আগে ছোঁয় না।

আরও কম কাজে সমাধান

একটা deque-তে (node) রাখো, depth 1 দিয়ে শুরু। প্রতিটা layer পুরো process করো (size = len(q) snapshot)। কোনো node-এর left ও right দুটোই None পেলেই বর্তমান depth ফেরত দাও — থামো। নইলে child enqueue করে পরের layer-এ depth বাড়াও। প্রথম leaf-এর layer-এই function বেরিয়ে যায়।

ভাবনার পরিবর্তন

মোচড়: "depth = কত গভীরে যেতে পারি" ভাবা ছাড়ো; বরং ভাবো "সবচেয়ে কাছের leaf কোথায়?" আর "কাছের" শুনলেই BFS — কারণ সে দূরত্ব অনুসারে ছড়ায়, তাই প্রথম hit-ই minimum। max→min করে DFS চালানোর ফাঁদ এড়িয়ে BFS-এর early-exit-এ যাওয়াই আসল aha।

ছবিতে বোঝা

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

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

ছোট input-এ ধাপে ধাপে

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।

কোড ও ব্যাখ্যা

Python

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!")

কোডের প্রতিটি অংশ

  • 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 মিলিয়ে দেখা

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

খরচ ও সাধারণ ভুল

সময়

O(n) worst case — সব node leaf থেকে দূরে থাকলে পুরো tree ঘুরতে হয়। কিন্তু সাধারণত আগেই থামে: প্রথম leaf-এর level পর্যন্ত মাত্র node দেখা হয়, তাই কাছের leaf থাকলে অনেক কম কাজ।

অতিরিক্ত জায়গা

O(w) — w = tree-র সবচেয়ে চওড়া level-এর node সংখ্যা (queue-তে এক layer জমে)। worst case-এ O(n) (যেমন পুরো শেষ layer), সরু chain-এ O(1)। (DFS-version হলে O(h) call stack হতো।)

যে ভুলগুলো এড়াতে হবে

  • Maximum Depth-এর max-কে min বানিয়ে দেওয়া → এক-child node-এ min(0, child) নিয়ে ভুল ছোট উত্তর।
  • depth ভুল জায়গায় বাড়ানো (প্রতি node-এ, layer-এ না) → level গণনা গোলমাল।
  • খালি tree-তে 0-এর বদলে 1 ফেরানো।

শেখা ও পরের অনুশীলন

ভিত্তির সঙ্গে সম্পর্ক

ভিত্তি: ../../04-stack-and-queue/-র queue ও BFS, traversal-patterns.md-র level-order section, আর Maximum Depth (#1)-র depth ধারণা (এখানে min, সাথে leaf-সতর্কতা)। concept.md-র leaf সংজ্ঞাও মনে রাখা জরুরি।

পরের অনুশীলন

কৌশলটি মনে রাখুন

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

নিজেকে যাচাই করুন

ভবিষ্যতের আমাকে: "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।