কনটেন্টে যান

018 — Diameter of Binary Tree

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

Problem link ও উৎস

  • Original source: Classic tree height-with-side-channel exercise
  • Platform: LeetCode — https://leetcode.com/problems/diameter-of-binary-tree/
  • Topic: trees
  • Difficulty: Medium
  • Pattern: Diameter via height
  • Basic idea inherited from: Maximum Depth + side-channel update (এই tracker-এর #1)

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

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

তোমাকে একটা binary tree দেওয়া আছে। তোমার কাজ: এর diameter বের করা — যেকোনো দুটো node-এর মধ্যে সবচেয়ে লম্বা path-এ কতগুলো edge আছে, সেই সংখ্যা। এই path root-এর ভেতর দিয়ে নাও যেতে পারে।

উদাহরণ
        1
       / \
      2   3        সবচেয়ে লম্বা path: 4 → 2 → 1 → 3 (অথবা 5 → 2 → 1 → 3)
     / \
    4   5          3 edge → diameter = 3

Input ও output

উদাহরণ
Input : root = [1,2,3,4,5]
Output: 3      (path 4→2→1→3, 3 edge)

Input : root = [1,2]      -> Output: 1   (এক edge)
Edge  : root = [1]        -> Output: 0   (একক node, কোনো edge নেই)
Edge  : root = []         -> Output: 0   (খালি tree)

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

একটা পাহাড়ি এলাকার সব শিখরের উচ্চতা মাপতে মাপতে তুমি এগোচ্ছ। প্রতিটা চূড়ায় দাঁড়িয়ে তুমি ভাবো "আমার দুই ঢালের সবচেয়ে দূরের দুই বিন্দুর মধ্যে দূরত্ব কত?" — সেটা একটা নোটবুকে (shared holder) টুকে রাখো যদি আগের চেয়ে বড় হয়। উপরে তুমি শুধু তোমার নিজের উচ্চতা রিপোর্ট করো, কিন্তু সবচেয়ে লম্বা বিস্তারটা নোটবুকে জমা থাকে।

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

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

এটা Maximum Depth (#1)-এর postorder height-fold থেকে আসে, একটা side-channel update যোগ করে। Maximum Depth-এ প্রতিটা node তার height উপরে ফেরত দিত। এখানে একই height হিসাব করি, কিন্তু পথে পথে একটা shared "best diameter" variable-ও update করি। এক traversal, দুটো কাজ।

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

লুকানো logic হলো প্রতিটা node-এ একটা path-candidate মাপা:

উদাহরণ
height(empty) = -1                       (edge গোনা)
এই node-এর ভেতর দিয়ে path = left_height + right_height + 2  (edge সংখ্যা)
best = max(best, এই candidate)
height(node) = 1 + max(left_height, right_height)  (উপরে শুধু height যায়)

প্রতিটা node ভাবে "আমার ভেতর দিয়ে সবচেয়ে লম্বা path কত?" — দুই দিকের height যোগ + 2 edge। সব node-এর candidate-এর সর্বোচ্চটাই diameter।

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

কোনো বড় data structure লাগে না। recursion call stack (height bottom-up হিসাব করে) আর একটা ছোট shared mutable holder (এক-element list বা nonlocal variable) যাতে best diameter সব call জুড়ে update হতে পারে।

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

Height হিসাব নিজেই একটা postorder recursion — call stack তা সামলায়। কিন্তু diameter পুরো tree-জুড়ে একটা চলমান max, তাই একটা shared holder লাগে যা প্রতিটা call থেকে লেখা যায়। এক-element list (best[0]) বা nonlocal এই "side channel"-টা দেয়, return value-কে শুধু height-এর জন্য মুক্ত রেখে।

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

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

প্রথম সরল চিন্তা: প্রতিটা node-কে আলাদা করে ভাবি — "এই node-এর ভেতর দিয়ে সবচেয়ে লম্বা path" = বাঁ subtree-র height + ডান subtree-র height + 2। প্রতিটা node-এ এটা মাপি, সর্বোচ্চটা নিই।

উদাহরণ
প্রতিটা node-এর জন্য:
    lh = height(node.left)   ← আলাদা পুরো traversal
    rh = height(node.right)  ← আলাদা পুরো traversal
    candidate = lh + rh + 2
সব candidate-এর max = diameter

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

এই সরল রূপে প্রতিটা node-এ আলাদা করে height() ডাকা হয়, আর height নিজেই পুরো subtree ঘোরে। তাই একই height বারবার হিসাব হয় — মোট O(n²) (skewed tree-তে আরো খারাপ)। আসলে height আর diameter-update একই traversal-এ করা যায়, প্রতিটা subtree একবার ঘুরে।

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

মূল observation: একটা postorder walk এমনিতেই সব height bottom-up হিসাব করে — তাই প্রতিটা node-এ height পাওয়ার ঠিক সেই মুহূর্তেই diameter-candidate (lh+rh+2) মাপা যায়, কোনো বাড়তি traversal ছাড়াই। Return value height-এর জন্য, side-channel diameter-এর জন্য।

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

এটা "একটা জিনিস return করো, আরেকটা update করো" pattern। একটা postorder height function: base-এ খালি subtree -1 (edge গোনা); প্রতিটা node-এ best = max(best, lh + rh + 2) দিয়ে diameter update; তারপর 1 + max(lh, rh) height উপরে দাও। একবার tree ঘোরা — O(n)।

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

মোচড়: "সবচেয়ে লম্বা path খুঁজে বের করব" ভাবা বন্ধ করো। বরং ভাবো "প্রতিটা node-কে জিজ্ঞেস করব: তোমার ভেতর দিয়ে গেলে path কত লম্বা?" — সেটা শুধু তার দুই দিকের height-এর যোগ। সব node-এর এই উত্তরের সর্বোচ্চটাই diameter। আর height তো এমনিতেই হিসাব হচ্ছে, তাই candidate পাশে free-তে পাওয়া যায়।

ছবিতে বোঝা

প্রতিটা node-এ candidate = বাঁ height + ডান height + 2; best update হয়:

উদাহরণ
              1   lh=1 (2-এর দিক), rh=0 (3) → cand 1+0+2 = 3 ← best
             / \
   lh=0,rh=0 2   3  (leaf, height 0)
            / \
           4   5    (leaf, height 0)

node 2: cand = 0+0+2 = 2 ;  node 1: cand = 1+0+2 = 3 → diameter 3

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

Input [1,2,3,4,5], best = 0 শুরুতে:

  1. height(4): leaf → lh=-1, rh=-1, cand = -1+-1+2 = 0, best=0; height = 0।
  2. height(5): একই, height = 0, best=0।
  3. height(2): lh=0 (4), rh=0 (5), cand = 0+0+2 = 2, best=2; height = 1।
  4. height(3): leaf, height = 0, cand 0, best stays 2।
  5. height(1): lh=1 (2), rh=0 (3), cand = 1+0+2 = 3, best=3; height = 2।
  6. উত্তর = best = 3।

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

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 diameter_of_binary_tree(root):
    best = [0]                        # shared side-channel (সব call জুড়ে)

    def height(node):
        if node is None:              # খালি subtree: -1 (edge গোনা)
            return -1
        lh = height(node.left)        # বাঁ দিকের height
        rh = height(node.right)       # ডান দিকের height
        best[0] = max(best[0], lh + rh + 2)   # এই node-এ বাঁকা path-এর edge
        return 1 + max(lh, rh)        # উপরে শুধু height যায়

    height(root)
    return best[0]


# ---- tests ----
assert diameter_of_binary_tree(build_tree([1, 2, 3, 4, 5])) == 3
assert diameter_of_binary_tree(build_tree([1, 2])) == 1
assert diameter_of_binary_tree(build_tree([1])) == 0
assert diameter_of_binary_tree(build_tree([])) == 0
assert diameter_of_binary_tree(build_tree([1, 2, None, 3, None, 4])) == 3
print("সব test pass!")

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

  • best = [0] — এক-element list, একটা shared mutable holder; সব recursive call এতে লিখতে পারে।
  • if node is None: return -1 — খালি subtree-র height -1, কারণ আমরা edge গুনছি (node না)।
  • lh = height(node.left) / rh = height(node.right) — দুই দিকের height bottom-up।
  • best[0] = max(best[0], lh + rh + 2) — এই node-এর ভেতর দিয়ে যাওয়া path-এর edge সংখ্যা; running max update।
  • return 1 + max(lh, rh) — উপরে শুধু নিজের height পাঠাও (পুরো diameter না)।
  • height(root); return best[0] — traversal চালাও, তারপর জমা-হওয়া best ফেরত দাও।

Output মিলিয়ে দেখা

build_tree([1,2,3,4,5]) ওই ছবির tree বানায়; diameter_of_binary_tree 3 ফেরত দেয় (path 4→2→1→3) — assert pass। [1,2] দেয় 1, একক node দেয় 0, খালি tree দেয় 0, আর একপাশে-ঝোলা chain [1,2,None,3,None,4] দেয় 3 (3 edge) — সব pass। শেষে print: সব test pass!।

JavaScript ও test cases

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

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

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 diameterOfBinaryTree(root) {
  let best = 0;                                  // shared side-channel (closure)
  const height = (node) => {
    if (node === null) return -1;                // খালি subtree: -1 (edge গোনা)
    const lh = height(node.left);                // বাঁ দিকের height
    const rh = height(node.right);               // ডান দিকের height
    best = Math.max(best, lh + rh + 2);          // এই node-এ বাঁকা path-এর edge
    return 1 + Math.max(lh, rh);                 // উপরে শুধু height যায়
  };
  height(root);
  return best;
}

// ---- test cases ----
assert(diameterOfBinaryTree(buildTree([1, 2, 3, 4, 5])) === 3, "diameter 3");
assert(diameterOfBinaryTree(buildTree([1, 2])) === 1, "এক edge");
assert(diameterOfBinaryTree(buildTree([1])) === 0, "একক node");
assert(diameterOfBinaryTree(buildTree([])) === 0, "খালি tree");
assert(diameterOfBinaryTree(buildTree([1, 2, null, 3, null, 4])) === 3, "skewed chain");
console.log("সব JS test pass!");

JS টীকা: Python-এ side-channel-এর জন্য এক-element list (best[0]) বা nonlocal লাগে; JS-এ আরও সহজ — একটা let best outer scope-এ রাখলে inner arrow-function closure দিয়ে সরাসরি reassign করতে পারে (best = ...)। কোনো mutable wrapper-এর দরকার নেই। Math.max plain number-এ কাজ করে, আর -1 base case edge-গোনা convention।

TypeScript ও test cases

TypeScript
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 diameterOfBinaryTree(root: TreeNode | null): number {
  let best = 0;
  const height = (n: TreeNode | null): number => {
    if (n === null) return -1;
    const lh = height(n.left);
    const rh = height(n.right);
    best = Math.max(best, lh + rh + 2);
    return 1 + Math.max(lh, rh);
  };
  height(root);
  return best;
}

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

expect(diameterOfBinaryTree(buildTree([1, 2, 3, 4, 5])) === 3, "3");
expect(diameterOfBinaryTree(buildTree([1, 2])) === 1, "1");
expect(diameterOfBinaryTree(buildTree([1])) === 0, "0");
expect(diameterOfBinaryTree(buildTree([])) === 0, "খালি");
expect(diameterOfBinaryTree(buildTree([1, 2, null, 3, null, 4])) === 3, "chain");
console.log("সব TS test pass!");

TS টীকা: let best = 0 থেকে TS নিজেই infer করে best একটা number, তাই inner height-এ best = Math.max(...) type-safe থাকে। height-এর return type number স্পষ্ট করে দেয় — উপরে সবসময় height (একটা সংখ্যা) যায়, কখনো ভুল করে diameter বা অন্য কিছু না। এই দুই দায়িত্ব (return height, update best) পরিষ্কারভাবে আলাদা থাকে।

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

সময়

O(n) — প্রতিটা node ঠিক একবার করে visit হয় (n = node সংখ্যা)। side-channel update O(1), তাই brute force-এর O(n²) থেকে নেমে O(n)।

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

O(h) — recursion call stack tree-র height h সমান গভীর। Balanced tree-তে O(log n), skewed chain-এ O(n)। best holder O(1)।

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

  • খালি subtree-তে 0 ফেরত দেওয়া (node-গোনা convention) — তখন edge সংখ্যা ভুল আসে; এই edge-গোনা সূত্রে -1 দরকার।
  • diameter হিসেবে height ফেরত দেওয়া — height আর diameter আলাদা; diameter side-channel-এ জমে, return-এ না।
  • প্রতিটা node-এ আলাদা height() ডেকে O(n²) করে ফেলা — একই traversal-এ দুটো কাজ করো।

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

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

ভিত্তি: Maximum Depth (#1)-এর postorder height-fold আর traversal-patterns.md-র Pattern E (diameter via height)। "এক জিনিস return, আরেক জিনিস update" — এই ভাগটাই মূল শিক্ষা।

পরের অনুশীলন

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

Compute-one, update-another: একটা postorder traversal-এ একটা জিনিস (height) RETURN করো, আর পাশে একটা shared best-কে UPDATE করো (এই node-এ বাঁকা path)। এটাই কঠিন tree interview-গুলোর signature চাল — diameter, max path sum, longest univalue path সবই এই কাঠামোয় দাঁড়ায়।

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

ভবিষ্যতের আমাকে: "diameter = প্রতিটা node-এ (বাঁ height + ডান height + 2) candidate, সর্বোচ্চটা রাখো; উপরে শুধু height দাও।" Height এমনিতেই হিসাব হচ্ছে, তাই candidate free। 'longest path / একটা compute করতে করতে আরেকটা track' দেখলেই এই side-channel চালটা মনে করবে।

কোথায় কাজে লাগে

  • Network latency (longest path): একটা tree-আকৃতির network-এ যেকোনো দুই node-এর মধ্যে সবচেয়ে দীর্ঘ পথ (worst-case hop) বের করা — capacity planning-এ।
  • File system longest path: দুটো সবচেয়ে দূরের ফাইলের মধ্যে directory-দূরত্ব — backup/sync tool-এর জন্য।
  • Critical path-জাতীয় analysis: dependency tree-তে সবচেয়ে দীর্ঘ chain খোঁজা (যদিও পুরো critical path আরও জটিল, এই "একটা compute করতে করতে আরেকটা track" কাঠামো ভিত্তি)।
  • Graphics / mesh: একটা tree-structured 3D model বা skeleton-এ সবচেয়ে দূরের দুই অংশের দূরত্ব মাপা।
  • Social network reach: একটা tree-আকৃতির sub-network-এ দুই সবচেয়ে দূরবর্তী ব্যক্তির মধ্যে connection-দূরত্ব।

মূল সুর: "একটা জিনিস (height) হিসাব করতে করতে পাশে আরেকটা best (longest path) track করো" — এই side-channel pattern diameter, max path sum, longest univalue path সবার ভিত্তি।

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