018 — Diameter of Binary Tree¶

Source¶

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)

1. Problem in simple words¶

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

2. Which basic idea does this inherit from?¶

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

3. What is the hidden math or logic?¶

লুকানো 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।

4. Which data structure is needed?¶

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

5. Why this data structure fits¶

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

6. Real-life analogy¶

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

7. Visual explanation¶

প্রতিটা 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

8. Example input and 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)

9. Brute force thinking¶

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

10. Why brute force is slow¶

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

11. Key observation¶

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

12. Optimized intuition¶

এটা "একটা জিনিস 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)।

13. Thinking tweak¶

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

14. Step-by-step dry run¶

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

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

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

16. Line-by-line code explanation¶

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 ফেরত দাও।

17. Output walkthrough¶

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

18. Time complexity¶

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

19. Space complexity¶

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

20. Common mistakes¶

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

21. Which basic problem this inherits from¶

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

22. Similar harder problems¶

Binary Tree Maximum Path Sum (একই bend-pattern, edge-এর জায়গায় value, negative pruning সহ) — https://leetcode.com/problems/binary-tree-maximum-path-sum/ (এই tracker-এর #23)
Longest Univalue Path (একই side-channel, সমান-value path) — https://leetcode.com/problems/longest-univalue-path/
Diameter of N-Ary Tree (একই idea, একাধিক child) — https://leetcode.com/problems/diameter-of-n-ary-tree/

23. Pattern learned¶

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

24. Final summary¶

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

25. JavaScript solution (with test cases)¶

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।

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 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) পরিষ্কারভাবে আলাদা থাকে।

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

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।