001 — Maximum Depth of Binary Tree¶

Source¶

Original source: Classic binary tree recursion exercise
Platform: LeetCode — https://leetcode.com/problems/maximum-depth-of-binary-tree/
Topic: trees
Difficulty: Easy
Pattern: Height (postorder)
Basic idea inherited from: factorial-style unwind (../../06-recursion-and-backtracking/) — উত্তর নিচ থেকে বুদবুদ হয়ে উপরে ওঠে

1. Problem in simple words¶

তোমাকে একটা binary tree-র root দেওয়া আছে। তোমার কাজ: এর maximum depth বের করা — মানে root থেকে সবচেয়ে দূরের leaf পর্যন্ত পথে কতগুলো node আছে, সেই সংখ্যা।

LeetCode এখানে depth-কে node গুনে মাপে (edge না)। তাই খালি tree-র depth 0, একটামাত্র node-এর depth 1।

        3
       / \
      9   20
         /  \
        15   7      ← সবচেয়ে লম্বা path: 3 → 20 → 15 (অথবা 3 → 20 → 7), 3 node, depth 3

2. Which basic idea does this inherit from?¶

এটা সরাসরি recursion-এর সেই unwind pattern থেকে আসে যেটা তুমি ../../06-recursion-and-backtracking/-এ factorial-এ দেখেছ। factorial-এ ছোট answer ((n-1)!) উপরে এসে n দিয়ে গুণ হয়। এখানে দুই child-এর depth উপরে এসে, বড়টা বেছে নিয়ে, তার সাথে 1 যোগ হয়। একই "নিচের উত্তর থেকে আমার উত্তর" সুর।

3. What is the hidden math or logic?¶

লুকানো সমীকরণটা একটা recurrence:

depth(empty) = 0
depth(node)  = 1 + max(depth(left), depth(right))

মানে: একটা node-এর depth = তার নিচের সবচেয়ে গভীর দিকের depth, plus নিজের জন্য 1। এটা concept.md-র height-এর hisaab, শুধু খালি tree-কে -1-এর বদলে 0 ধরা হচ্ছে (কারণ এখানে আমরা node গুনছি, edge না)।

4. Which data structure is needed?¶

কোনো extra data structure লাগে না। শুধু recursion call stack — Python নিজেই প্রতিটা চলমান call মনে রাখে। tree-টা নিজেই তোমার data structure।

5. Why this data structure fits¶

Tree self-similar: প্রতিটা node নিজেই একটা ছোট tree-র root (concept.md দেখো)। তাই একটা recursive function নিখুঁত খাপ খায় — সে নিজেকে left-এ ডাকে, নিজেকে right-এ ডাকে, প্রতিটা subtree-কে এক-একটা পূর্ণ tree হিসেবে treat করে। call stack এমনিতেই কোন path-এ কতদূর নেমেছি সেটা ধরে রাখে।

6. Real-life analogy¶

একটা company-র org chart ভাবো। CEO জিজ্ঞেস করেন, "আমার নিচে সবচেয়ে লম্বা reporting chain কত গভীর?" উনি সরাসরি জানেন না। উনি দুই VP-কে জিজ্ঞেস করেন, "তোমাদের নিচে সবচেয়ে গভীর chain কত?" প্রত্যেক VP নিজের নিচে একই প্রশ্ন পাঠায়। উত্তরগুলো নিচ থেকে উপরে ফিরে আসে; প্রত্যেকে নিজের দুই দিকের বড়টা নিয়ে, নিজের জন্য 1 যোগ করে উপরে পাঠায়।

7. Visual explanation¶

প্রতিটা node-এ ছোট সংখ্যাটা হলো সেই node-এর depth (তার subtree-র উত্তর)। উত্তরগুলো নিচ থেকে উপরে ওঠে:

              3   depth = 1 + max(1, 2) = 3
             / \
   depth=1  9   20  depth = 1 + max(1, 1) = 2
               / \
     depth=1  15  7  depth=1
              |   |
           leaves → depth 1 each (1 + max(0,0))

8. Example input and output¶

Input : root = [3,9,20,null,null,15,7]
Output: 3

Input : root = [1,null,2]      -> Output: 2   (chain: 1 → 2)
Edge  : root = []              -> Output: 0   (খালি tree)
Edge  : root = [1]             -> Output: 1   (একটামাত্র node)

9. Brute force thinking¶

প্রথম সরল চিন্তা: tree-র সব root-to-leaf path আলাদা করে বের করি, প্রতিটার length মাপি, তারপর সবচেয়ে বড়টা নিই।

1) সব path খুঁজে বের করো: [3,9], [3,20,15], [3,20,7]
2) length: 2, 3, 3
3) max = 3

10. Why brute force is slow¶

সব path আলাদা করে জমালে অনেক path-এর shared উপরের অংশ বারবার লেখা হয় — extra memory আর কাজ নষ্ট হয়। আসলে full path list দরকারই নেই; প্রতিটা node-এ শুধু "আমার নিচে কত গভীর" — একটাই সংখ্যা — জানলেই চলে। সেটাই recursion সরাসরি দেয়, কোনো path জমানো ছাড়াই।

11. Key observation¶

মূল observation: একটা node-এর depth পুরোপুরি তার দুই child-এর depth দিয়ে ঠিক হয়ে যায়। তাই পুরো tree একসাথে ভাবার দরকার নেই — শুধু "নিচ থেকে দুটো সংখ্যা পাও, বড়টায় 1 যোগ করো, উপরে পাঠাও।"

12. Optimized intuition¶

এটা একটা postorder কাজ (Left → Right → Node): node-এর উত্তর হিসাব করার আগে তার দুই child সম্পূর্ণ শেষ হতে হবে। প্রতিটা call দুটো ছোট সংখ্যা ফেরত পায়, max নেয়, 1 যোগ করে উপরে দেয়। পুরো tree একবার ঘোরা — এর চেয়ে দ্রুত সম্ভব না, কারণ প্রতিটা node তো অন্তত একবার দেখতেই হবে।

13. Thinking tweak¶

মোচড়: "সবচেয়ে গভীর path খুঁজব" ভাবা বন্ধ করো। বরং ভাবো "প্রতিটা node-কে শুধু একটা প্রশ্ন করব: তোমার নিচে কত গভীর?" — আর leaf-এর জন্য leap of faith নাও যে child-রা নিজের ঠিক উত্তর ফেরত দেবে। বড় path-খোঁজা সমস্যা একটা ছোট, repeatable max-and-add step-এ গলে যায়।

14. Step-by-step dry run¶

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

max_depth(3) ডাকে → আগে left আর right লাগবে।
max_depth(9): 9 leaf → 1 + max(0, 0) = 1 ফেরত।
max_depth(20): আগে তার child লাগবে।
max_depth(15) = 1, max_depth(7) = 1 → max_depth(20) = 1 + max(1, 1) = 2।
এখন max_depth(3) = 1 + max(1, 2) = 3 → 3 return।

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 max_depth(node):
    if node is None:            # খালি subtree: 0 node গভীর
        return 0
    left = max_depth(node.left)     # বাঁ দিক কত গভীর?
    right = max_depth(node.right)   # ডান দিক কত গভীর?
    return 1 + max(left, right)     # বড়টা নাও, নিজের জন্য 1 যোগ করো


# ---- tests ----
assert max_depth(build_tree([3, 9, 20, None, None, 15, 7])) == 3
assert max_depth(build_tree([1, 2])) == 2          # chain 1 → 2
assert max_depth(build_tree([])) == 0              # খালি tree
assert max_depth(build_tree([1])) == 1             # একটামাত্র node
print("সব test pass!")

16. Line-by-line code explanation¶

if node is None: return 0 — base case; খালি subtree-তে কোনো node নেই, তাই 0।
left = max_depth(node.left) — leap of faith: ধরে নাও বাঁ দিক নিজের সঠিক depth ফেরত দেবে।
right = max_depth(node.right) — একই, ডান দিকের জন্য।
return 1 + max(left, right) — দুই দিকের গভীরতমটা বেছে, এই node-এর জন্য 1 যোগ করে উপরে দাও।
build_tree helper level-order list-কে আসল node-এ রূপ দেয়, None দিয়ে missing child চিহ্নিত করে।

17. Output walkthrough¶

build_tree([3,9,20,None,None,15,7]) ওই ছবির tree বানায়; max_depth 3 ফেরত দেয় — assert pass। chain [1,2] দেয় 2, খালি tree দেয় 0, একক node দেয় 1 — সব pass। শেষে print: সব test pass!।

18. Time complexity¶

O(n) — প্রতিটা node ঠিক একবার করে visit হয় (n = node সংখ্যা)। এর চেয়ে কম সম্ভব না, কারণ গভীরতম দিক জানতে সবাইকে অন্তত একবার দেখতেই হবে।

19. Space complexity¶

O(h) — recursion call stack tree-র height h সমান গভীর হয়। Balanced tree-তে O(log n), একপাশে ঝোলা chain-এ O(n)। (concept.md-র complexity table দেখো।)

20. Common mistakes¶

খালি tree-তে -1 ফেরত দেওয়া (সেটা edge-গোনা height-এর convention) — এই problem node গোনে, তাই 0।
max-এর জায়গায় min লিখে minimum depth বানিয়ে ফেলা — ভিন্ন problem (এই tracker-এর #11)।
base case ভুলে গিয়ে None.left ছোঁয়া → AttributeError।

21. Which basic problem this inherits from¶

ভিত্তি: concept.md-র height snippet আর ../../06-recursion-and-backtracking/-এর unwind pattern। এই দুটো এক হলেই "নিচের উত্তর থেকে আমার উত্তর" পুরো tree জুড়ে কাজ করে।

22. Similar harder problems¶

Balanced Binary Tree (height ফেরত দাও, সাথে balanced কিনা যাচাই) — https://leetcode.com/problems/balanced-binary-tree/ (এই tracker-এর #10)
Minimum Depth of Binary Tree (max-এর বদলে min, কিন্তু leaf সাবধানে) — https://leetcode.com/problems/minimum-depth-of-binary-tree/ (#11)
Diameter of Binary Tree (height হিসাব করতে করতে পাশে diameter update) — https://leetcode.com/problems/diameter-of-binary-tree/ (#18)

23. Pattern learned¶

Postorder height-fold: প্রতিটা node-এ দুই child-এর সংখ্যা নাও, combine করো (1 + max), উপরে পাঠাও। এটাই tree DP-র আদিরূপ — height, size, sum, balanced — সব এই একই কঙ্কালের উপর দাঁড়ায়।

24. Final summary¶

ভবিষ্যতের আমাকে: "tree-র depth = 1 + দুই দিকের গভীরতমটা, খালি হলে 0।" যখনই কোনো problem বলবে "তোমার দুই subtree-র উত্তর মিলিয়ে এই node-এর উত্তর দাও," এই postorder fold-টা মনে করবে — Maximum Depth হলো তার সবচেয়ে পরিষ্কার রূপ।

25. JavaScript solution (with test cases)¶

const assert = (cond, msg = "") => { if (!cond) throw new Error("FAIL " + msg); };

// tree node helper
class TreeNode {
  constructor(val = 0, left = null, right = null) {
    this.val = val; this.left = left; this.right = right;
  }
}

// level-order array (null = missing child) থেকে tree বানায়
function buildTree(values) {
  if (!values || values.length === 0) return null;
  const root = new TreeNode(values[0]);
  const q = [root];
  let i = 1, head = 0;
  while (head < q.length && i < values.length) {
    const node = q[head++];
    if (i < values.length && values[i] !== null) {
      node.left = new TreeNode(values[i]); q.push(node.left);
    }
    i++;
    if (i < values.length && values[i] !== null) {
      node.right = new TreeNode(values[i]); q.push(node.right);
    }
    i++;
  }
  return root;
}

function maxDepth(node) {
  if (node === null) return 0;              // খালি subtree: 0 node গভীর
  const left = maxDepth(node.left);          // বাঁ দিক কত গভীর?
  const right = maxDepth(node.right);        // ডান দিক কত গভীর?
  return 1 + Math.max(left, right);          // বড়টা নাও, নিজের জন্য 1 যোগ
}

// ---- test cases ----
assert(maxDepth(buildTree([3, 9, 20, null, null, 15, 7])) === 3, "depth 3");
assert(maxDepth(buildTree([1, 2])) === 2, "chain 1->2");
assert(maxDepth(buildTree([])) === 0, "খালি tree");
assert(maxDepth(buildTree([1])) === 1, "একটামাত্র node");
console.log("সব JS test pass!");

JS টীকা: JS-এ Python-এর deque নেই, কিন্তু buildTree-এ আমরা একটা plain array আর একটা head index দিয়ে queue চালিয়েছি (q.shift() O(n) এড়াতে)। Math.max দুই সংখ্যার বড়টা দেয়, ঠিক Python-এর max-এর মতো। recursion-এর গঠন Python-এর হুবহু এক — শুধু None → null, is None → === null।

26. TypeScript solution (with test cases)¶

interface TreeNode { val: number; left: TreeNode | null; right: TreeNode | null; }

function node(val: number, left: TreeNode | null = null, right: TreeNode | null = null): TreeNode {
  return { val, left, right };
}

function buildTree(values: (number | null)[]): TreeNode | null {
  if (values.length === 0) return null;
  const root = node(values[0] as number);
  const q: TreeNode[] = [root];
  let i = 1, head = 0;
  while (head < q.length && i < values.length) {
    const cur = q[head++];
    if (i < values.length && values[i] !== null) {
      cur.left = node(values[i] as number); q.push(cur.left);
    }
    i++;
    if (i < values.length && values[i] !== null) {
      cur.right = node(values[i] as number); q.push(cur.right);
    }
    i++;
  }
  return root;
}

function maxDepth(root: TreeNode | null): number {
  if (root === null) return 0;
  return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}

const expect = (cond: boolean, msg = ""): void => { if (!cond) throw new Error("FAIL " + msg); };

expect(maxDepth(buildTree([3, 9, 20, null, null, 15, 7])) === 3, "depth 3");
expect(maxDepth(buildTree([1, 2])) === 2, "chain");
expect(maxDepth(buildTree([])) === 0, "খালি");
expect(maxDepth(buildTree([1])) === 1, "একক node");
console.log("সব TS test pass!");

TS টীকা: TreeNode | null type-টা compiler-কে দিয়ে নিশ্চিত করায় — root.left ছোঁয়ার আগে অবশ্যই null check করতে হবে, না হলে compile error। (number | null)[] input type level-order array-তে missing child (null) আর আসল value আলাদা করে। এই type-গুলো "base case ভুলে গেলে null.left ছোঁয়া" বাগ compile-time-এই ধরে ফেলে।

27. কোথায় কাজে লাগে (real-world use)¶

File system depth: নেস্টেড folder structure কত গভীর (root থেকে সবচেয়ে গভীর ফাইল পর্যন্ত) মাপতে — backup tool বা path-length limit চেক করার সময়।
DOM tree analysis: একটা HTML page-এর DOM কত গভীরে nested, browser rendering performance বা accessibility audit-এ এটা একটা গুরুত্বপূর্ণ metric।
Org chart / reporting hierarchy: কোনো company-তে সবচেয়ে লম্বা reporting chain কত স্তর গভীর — management layer কমানোর analysis-এ।
Decision tree / ML model: একটা trained decision tree-র depth জানা overfitting নির্ণয় করতে সাহায্য করে (খুব গভীর tree সাধারণত overfit করে)।
Network routing: spanning tree-তে সবচেয়ে দূরের node পর্যন্ত hop সংখ্যা — latency estimate করতে।

এই সব ক্ষেত্রেই মূল প্রশ্ন এক: "এই hierarchical structure-টা কত স্তর গভীর?" — আর postorder height-fold সবচেয়ে পরিষ্কার, এক-পাস উত্তর।

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