025 — Tree Diameter

Source

• Original source: CSES Problem Set — Tree Algorithms section
• Platform: CSES — https://cses.fi/problemset/ (task name: Tree Diameter)
• Topic: trees
• Difficulty: Hard
• Pattern: Diameter at CP scale
• Basic idea inherited from: Diameter of Binary Tree (#18), general tree, deep recursion সামলানো

1. Problem in simple words

তোমাকে একটা general tree দেওয়া আছে — nটা node, n−1টা edge, কোনো cycle নেই, সব connected। প্রতিটা node-এর যেকোনো সংখ্যক প্রতিবেশী থাকতে পারে। তোমার কাজ: tree-র diameter বের করা — মানে যেকোনো দুই node-এর মধ্যে সবচেয়ে লম্বা path-এ কতগুলো edge আছে, সেই সর্বোচ্চ সংখ্যা।

এটা LeetCode-এর Diameter (#18)-এর CP-সংস্করণ: গঠন binary নয় (adjacency list দিয়ে আসে), আর n ২ লক্ষ পর্যন্ত — তাই গভীর recursion সামলানোটাও সমস্যার অংশ।

edges: 1-2, 1-3, 3-4, 3-5

        1
       / \
      2   3
         / \
        4   5      সবচেয়ে লম্বা path: 2 → 1 → 3 → 4 (বা 5), 3 edge → diameter 3

2. Which basic idea does this inherit from?

এটা Diameter of Binary Tree (#18)-এর সরাসরি সাধারণীকরণ। সেখানে প্রতিটা node-এ দুই child-এর height যোগ করে diameter পেতে; এখানে child দুটো নয় — যত খুশি — তাই প্রতিটা node-এ সব child-এর height-এর মধ্যে সবচেয়ে বড় দুটো নিয়ে যোগ করতে হয়। মূল চাল একই: "প্রতিটা node-কে path-এর চূড়া ধরে দুই সেরা arm যোগ করো, পাশে global max রাখো।"

3. What is the hidden math or logic?

লুকানো logic — height return করি, পাশে diameter track করি:

height(u) = 1 + max(height(c)) over children c   (edge-গোনায় leaf height 0)
প্রতিটা node u-তে: সব child-এর (height(c)+1) থেকে সেরা দুটো top1, top2 নাও
diameter = max(diameter, top1 + top2)            # u-কে চূড়া ধরে দুই arm
return top1                                       # উপরে শুধু এক arm যায়

মূল বুদ্ধি: u দিয়ে যাওয়া সবচেয়ে লম্বা path = তার দুই গভীরতম child-শাখা জোড়া দেওয়া; কিন্তু parent-এর কাছে u শুধু একটা (গভীরতম) শাখা দিতে পারে।

4. Which data structure is needed?

একটা adjacency list (adj[u] = u-র প্রতিবেশীদের list), একটা side variable diameter, আর DFS। যেহেতু tree unrooted ও general, প্রতিটা DFS-এ parent মনে রাখতে হয় (যাতে যেদিক থেকে এলাম সেদিকে ফিরে না যাই)। CSES-এ n বিশাল ও chain গভীর হতে পারে — তাই iterative DFS (বা recursion limit বাড়ানো) লাগে।

5. Why this data structure fits

General unrooted tree-তে edge দু'মুখী, child-সংখ্যা যেকোনো — adjacency list নমনীয়ভাবে সব প্রতিবেশী ধরে, আর parent বাদ দিলে সেটাই কার্যত rooted DFS হয়ে যায়। diameter যেকোনো node-এ চূড়া পেতে পারে, তাই একটা side variable সব node-এর "দুই-arm যোগফল"-এর সর্বোচ্চটা ধরে। বিশাল n-এ Python recursion ভেঙে পড়ে, তাই explicit stack নিরাপদ।

6. Real-life analogy

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

7. Visual explanation

প্রতিটা node-এ সেরা দুই arm যোগ করে diameter; height উপরে এক arm যায়:

        1            arm থেকে: top1=2 (1-3-4), top2=1 (1-2) → 2+1 = 3 ← diameter
       / \
      2   3          3-এ: top1=1 (3-4), top2=1 (3-5) → 1+1 = 2
          / \
        4   5        leaf height 0

8. Example input and output

Input : n = 5, edges = [(1,2),(1,3),(3,4),(3,5)]
Output: 3                  (path 2→1→3→4, 3 edge)

Input : n = 1, edges = []          -> Output: 0   (একা node, কোনো edge নেই)
Input : n = 2, edges = [(1,2)]     -> Output: 1   (একটামাত্র edge)
Input : n = 4, edges = [(1,2),(2,3),(3,4)] -> Output: 3  (সোজা chain)

9. Brute force thinking

প্রথম সরল চিন্তা: প্রতিটা node থেকে আলাদা BFS/DFS চালিয়ে বাকি সব node-এর দূরত্ব মাপো, সবচেয়ে দূরেরটা রাখো, তারপর সব node-এর সর্বোচ্চটা নাও।

1) প্রতিটা node u-র জন্য:
2)    u থেকে BFS করে সব দূরত্ব বের করো
3)    সবচেয়ে দূরের দূরত্ব মনে রাখো (eccentricity)
4) সব eccentricity-র max = diameter

10. Why brute force is slow

প্রতিটা node থেকে একটা পূর্ণ traversal মানে O(n²) — n = ২ লক্ষ হলে অসম্ভব। দুটো ভালো বিকল্প আছে, দুটোই O(n): (১) single-DFS — প্রতিটা node-এ সেরা দুই child-height যোগ করে diameter পাও (Diameter #18-এর সাধারণীকরণ); (২) two-BFS চাল — যেকোনো node থেকে সবচেয়ে দূরের node a খোঁজো, তারপর a থেকে সবচেয়ে দূরের b; a–b দূরত্বই diameter। এখানে আমরা single-DFS করব।

11. Key observation

মূল observation: যেকোনো node-কে path-এর চূড়া ধরলে, সেখানে দীর্ঘতম path = তার দুই গভীরতম child-শাখার যোগফল। তাই প্রতিটা node-এ সব child-arm থেকে সেরা দুটো নিয়ে যোগ করলেই সেই node-এ সম্ভাব্য diameter পাওয়া যায়; সব node-এর এমন মানের সর্বোচ্চটাই উত্তর। parent-কে অবশ্য শুধু একটা (গভীরতম) arm দেওয়া যায়।

12. Optimized intuition

একটা DFS চালাও যেটা প্রতিটা node থেকে নিচে নামা সর্বোচ্চ height (edge-এ) ফেরত দেয়। প্রতিটা node-এ সব child-এর height(c)+1 সংগ্রহ করো; তার মধ্যে top1 ও top2 (না থাকলে 0) দিয়ে diameter = max(diameter, top1 + top2) update করো; return করো top1। বিশাল/গভীর tree-তে recursion limit ভাঙতে পারে, তাই একটা explicit-stack iterative postorder ব্যবহার করো। পুরো tree একবার ঘোরা → O(n)।

13. Thinking tweak

মোচড়: binary diameter থেকে এখানে আসতে শুধু "left আর right" বদলে "সব child-এর মধ্যে সেরা দুই" ভাবো — বাকি কাঠামো (return এক arm, update দুই arm) হুবহু একই। আর CP-মোচড়: n বিশাল হলে naive recursion stack overflow করবে — তাই হয় iterative DFS লেখো, নয়তো sys.setrecursionlimit বাড়িয়ে নাও। (চাইলে two-BFS চালও আছে, কিন্তু single-DFS-ই #18-এর সরাসরি জ্ঞাতি।)

14. Step-by-step dry run

n = 5, edges (1,2),(1,3),(3,4),(3,5), root ধরি 1, diameter = 0:

1. height(2): leaf (parent 1 বাদে কেউ নেই) → return 0।
2. height(4): leaf → 0; height(5): leaf → 0।
3. height(3): child 4,5-এর arm = 0+1, 0+1 → top1=1, top2=1 → diameter = max(0, 1+1) = 2; return 1।
4. height(1): child 2,3-এর arm = (0+1)=1, (1+1)=2 → top1=2, top2=1 → diameter = max(2, 2+1) = 3; return 2।
5. উত্তর = diameter = 3 (path 2→1→3→4)।

15. Python solution

import sys
from collections import deque


def tree_diameter(n, edges):
    """n-node general tree-র diameter (edge সংখ্যায়); edges দু'মুখী।"""
    adj = [[] for _ in range(n + 1)]      # 1-indexed adjacency list
    for u, v in edges:
        adj[u].append(v)
        adj[v].append(u)

    if n == 1:                            # একা node, কোনো edge নেই
        return 0

    # iterative DFS: প্রথমে parent সহ একটা visit-order বানাই
    root = 1
    parent = [0] * (n + 1)
    order, stack = [], [root]
    parent[root] = -1                     # root-এর parent নেই
    while stack:
        u = stack.pop()
        order.append(u)
        for w in adj[u]:
            if w != parent[u]:
                parent[w] = u
                stack.append(w)

    height = [0] * (n + 1)                # node থেকে নিচে নামা সর্বোচ্চ edge-দূরত্ব
    diameter = 0
    for u in reversed(order):             # পাতা → root ক্রমে (postorder)
        top1 = top2 = 0                   # সেরা দুই child-arm
        for w in adj[u]:
            if w == parent[u]:
                continue
            arm = height[w] + 1
            if arm > top1:
                top1, top2 = arm, top1
            elif arm > top2:
                top2 = arm
        diameter = max(diameter, top1 + top2)   # u-কে চূড়া ধরে দুই arm
        height[u] = top1                          # উপরে শুধু এক arm
    return diameter


# ---- tests ----
assert tree_diameter(5, [(1, 2), (1, 3), (3, 4), (3, 5)]) == 3
assert tree_diameter(1, []) == 0                       # একা node
assert tree_diameter(2, [(1, 2)]) == 1                 # একটামাত্র edge
assert tree_diameter(4, [(1, 2), (2, 3), (3, 4)]) == 3 # সোজা chain

# তারা-আকার: কেন্দ্র 1-এর সাথে 2,3,4,5 — দীর্ঘতম path যেকোনো দুই পাতা = 2 edge
assert tree_diameter(5, [(1, 2), (1, 3), (1, 4), (1, 5)]) == 2

# গভীর chain (iterative হওয়ায় overflow হয় না): 1-2-...-2000 → diameter 1999
deep_edges = [(i, i + 1) for i in range(1, 2000)]
assert tree_diameter(2000, deep_edges) == 1999
print("সব test pass!")

16. Line-by-line code explanation

• adj = [[] for _ in range(n + 1)]; ... adj[u].append(v); adj[v].append(u) — 1-indexed, দু'মুখী adjacency list (edge উভয় দিকে)।
• if n == 1: return 0 — একা node-এ কোনো edge নেই, diameter 0।
• iterative DFS (order, parent) — recursion ছাড়া একটা visit-order ও প্রতিটা node-এর parent বের করি; w != parent[u] যেদিক থেকে এলাম সেদিকে ফেরা আটকায়।
• for u in reversed(order): — order উল্টালে প্রতিটা parent-এর আগে তার সব child আসে → বৈধ postorder।
• top1, top2 লুপ — u-র সব child-arm (height[w]+1)-এর মধ্যে সেরা দুটো রাখি (general tree বলে দুইয়ের বেশি child হতে পারে)।
• diameter = max(diameter, top1 + top2) — u-কে চূড়া ধরে দুই গভীরতম arm যোগ; global update।
• height[u] = top1 — parent-কে শুধু গভীরতম এক arm ফেরত দিই।

17. Output walkthrough

tree_diameter(5, [(1,2),(1,3),(3,4),(3,5)]) দেয় 3 (path 2→1→3→4) — assert pass। একা node দেয় 0, একটা edge দেয় 1, 4-node chain দেয় 3, তারা-আকার দেয় 2 (যেকোনো দুই পাতা)। 2000-node গভীর chain-এও iterative হওয়ায় overflow ছাড়া 1999 দেয় — pass। শেষে print: সব test pass!।

18. Time complexity

O(n) — order বানাতে প্রতিটা node ও edge একবার, height/diameter জমাতে প্রতিটা node ও তার edge আরেকবার; tree-তে edge n−1টা, তাই মোট রৈখিক। n = ২ লক্ষেও দ্রুত।

19. Space complexity

O(n) — adjacency list O(n) (দু'মুখী edge), parent/height/order/stack প্রতিটা O(n)। iterative DFS হওয়ায় recursion call stack-এর O(n) গভীরতা এড়ানো গেছে — naive recursion-এ ওটাই গভীর chain-এ overflow ঘটাত।

20. Common mistakes

• recursive DFS দিয়ে ২ লক্ষ-লম্বা chain-এ RecursionError — iterative DFS বা বাড়ানো recursion limit লাগে।
• parent বাদ না দেওয়া — তখন DFS যেদিক থেকে এসেছে সেদিকে ফিরে গিয়ে infinite loop/ভুল height হয় (unrooted tree বলে edge দু'মুখী)।
• শুধু top1 দিয়ে diameter হিসাব করা — চূড়ায় দুই arm লাগে; top2 ভুললে diameter কম আসে।
• edge-গোনা বনাম node-গোনা গুলিয়ে ফেলা — এই problem edge গোনে, তাই leaf height 0, একটা edge-এ diameter 1।

21. Which basic problem this inherits from

ভিত্তি: Diameter of Binary Tree (#18)-এর "height return, পাশে দুই-arm diameter track" আর Subordinates (#22)-এর general-tree iterative DFS। দুটো এক হলে — সেরা-দুই-arm + বড় ইনপুটে iterative — CSES Tree Diameter দাঁড়িয়ে যায়।

22. Similar harder problems

• Diameter of Binary Tree (একই ধারণা, binary সংস্করণ) — https://leetcode.com/problems/diameter-of-binary-tree/ (এই tracker-এর #18)
• Tree Distances I (CSES — প্রতিটা node থেকে সর্বোচ্চ দূরত্ব, rerooting) — https://cses.fi/problemset/
• Tree Distances II (CSES — প্রতিটা node থেকে সব দূরত্বের যোগফল, rerooting DP) — https://cses.fi/problemset/

23. Pattern learned

Diameter on a general tree (best-two-arms, iterative): একটা DFS-এ প্রতিটা node থেকে গভীরতম height return করো; প্রতিটা node-এ সব child-arm থেকে সেরা দুটো যোগ করে global diameter update করো; বড় ইনপুটে stack-overflow এড়াতে iterative DFS। যেকোনো tree-তে "সবচেয়ে দূরের দুই বিন্দুর দূরত্ব" টাইপ problem-এর কঙ্কাল এটাই।

24. Final summary

ভবিষ্যতের আমাকে: "tree diameter = প্রতিটা node-এ সেরা দুই child-arm যোগ করে global max; উপরে এক arm দাও; বড় tree-তে iterative DFS।" সেরা-দুই-arm আর recursion-limit সামলানো — এই দুটোই মূল। 'সবচেয়ে লম্বা path / সবচেয়ে দূরের জোড়া' টাইপ general-tree problem দেখলেই এই Diameter চালটা মনে করবে।

---

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