Skip to content

023 — Binary Tree Maximum Path Sum

Source

1. Problem in simple words

তোমাকে একটা binary tree দেওয়া আছে যার node-গুলোতে সংখ্যা (ঋণাত্মকও হতে পারে) আছে। একটা path মানে node-এর এমন একটা ক্রম যেখানে পরপর দুটো node edge দিয়ে যুক্ত, কোনো node দু'বার নয়, আর path-এ অন্তত একটা node থাকতেই হবে। তোমার কাজ: এমন path খুঁজে বের করা যার node-value-র যোগফল সর্বোচ্চ, আর সেই যোগফলটা ফেরত দেওয়া।

মূল মোচড়: path-কে root দিয়ে যেতে হবে না — সে tree-র যেকোনো জায়গায় শুরু ও শেষ হতে পারে, এমনকি একটা subtree-র ভেতরে বাঁ-পাশ থেকে উপরে উঠে ডান-পাশে নেমে যেতে পারে (একটা "∧" আকার)।

       -10
       /  \
      9    20        সেরা path: 15 → 20 → 7 = 42
          /  \
        15    7      (root -10 এড়িয়ে গেলেই ভালো)

2. Which basic idea does this inherit from?

এটা Diameter of Binary Tree (#18)-এর সরাসরি জ্ঞাতি। Diameter-এ প্রতিটা node-এ তুমি দুই দিকের height যোগ করে সবচেয়ে লম্বা পথ পাশের একটা variable-এ রাখতে। এখানে height-এর জায়গায় best downward path-sum বসাও, আর "edge গোনা"-র জায়গায় "value যোগ করা"। নতুন যা যোগ হয়: ঋণাত্মক branch থাকলে সেটা বাদ (০ ধরা) — কারণ লোকসানি দিক নেওয়ার চেয়ে না নেওয়া ভালো।

3. What is the hidden math or logic?

লুকানো logic-এ দুটো আলাদা মান আছে — একটা return করি, একটা পাশে track করি:

gain(node):
    node None হলে → 0
    left  = max(gain(node.left), 0)    # ঋণাত্মক হলে বাদ
    right = max(gain(node.right), 0)   # ঋণাত্মক হলে বাদ
    best = max(best, node.val + left + right)   # এই node-এ চূড়া (∧) বানাও
    return node.val + max(left, right)          # উপরে শুধু একটা দিক নেওয়া যায়

মূল বুদ্ধি: parent-এর কাছে একটা path তো একটা দিক দিয়েই উঠতে পারে (max(left, right)), কিন্তু এই node-কে চূড়া ধরে একটা path দুই দিকই ব্যবহার করতে পারে — সেই দুই-দিক যোগফলই global উত্তরের প্রার্থী।

4. Which data structure is needed?

কোনো extra data structure লাগে না — recursion (postorder) আর একটা side-channel variable best (এখন পর্যন্ত পাওয়া সর্বোচ্চ path-sum)। tree নিজেই data structure; call stack নামার পথ মনে রাখে। best-কে nonlocal/list/attribute দিয়ে সব call-এ ভাগ করতে হয়।

5. Why this data structure fits

প্রতিটা node-এ আমাদের দুটো ভিন্ন জিনিস লাগে: (১) উপরে কী return করব (single-arm gain), আর (২) এখানে সেরা ∧-path কত (global update)। একটা postorder recursion ঠিক এই দুটো একসাথে দিতে পারে — child শেষ হলেই দুই arm পাওয়া যায়। আর global সর্বোচ্চটা যেহেতু যেকোনো node-এ ঘটতে পারে, একটা side variable সব node-এর প্রার্থীর মধ্যে সবচেয়ে বড়টা ধরে রাখে।

6. Real-life analogy

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

7. Visual explanation

প্রতিটা node দুই arm-এর gain (ঋণাত্মক হলে ০) নিয়ে ∧-চূড়া বানায়; best সব চূড়ার সর্বোচ্চ:

        -10            চূড়া এখানে: -10 + 15 + 0 = 5  (left=15, right বাদ)
        /  \
       9    20         চূড়া: 20 + 15 + 7 = 42  ← best!
            / \
          15   7       leaf: gain 15, gain 7
                       20 উপরে দেয়: 20 + max(15,7) = 35

8. Example input and output

Input : root = [1,2,3]
Output: 6                 (2 → 1 → 3 = 6, পুরো ∧)

Input : root = [-10,9,20,null,null,15,7]
Output: 42                (15 → 20 → 7)

Edge  : root = [-3]               -> Output: -3   (একটামাত্র node, ঋণাত্মক হলেও নিতেই হবে)
Edge  : root = [2,-1]             -> Output: 2    (-1 বাদ, শুধু 2)
Edge  : root = [-2,-1]            -> Output: -1   (কম খারাপটা)

9. Brute force thinking

প্রথম সরল চিন্তা: tree-র প্রতি জোড়া node-কে এক path-এর দুই প্রান্ত ধরো, তাদের মাঝের পথের যোগফল বের করো, সবগুলোর সর্বোচ্চটা নাও।

1) সব (u, v) জোড়ার জন্য:
2)    u থেকে v পর্যন্ত একমাত্র path খোঁজো
3)    সেই path-এর value যোগ করো
4) সব যোগফলের max নাও

10. Why brute force is slow

জোড়ার সংখ্যা O(n²), আর প্রতি জোড়ার path বের করতে আরও O(n) পর্যন্ত — সব মিলিয়ে O(n³) (বা সাবধানে করলে O(n²))। বিশাল অপচয়, কারণ আলাদা আলাদা path-এর অনেক অংশ shared। আসল চাল: প্রতিটা node-কে path-এর সর্বোচ্চ বিন্দু (চূড়া) ধরে ভাবা — তখন প্রতিটা সম্ভাব্য সেরা path ঠিক একবার, একটা মাত্র postorder pass-এ দেখা হয়ে যায়।

11. Key observation

মূল observation: যেকোনো path-এর একটা সর্বোচ্চ node থাকে (যেখান থেকে দুই দিকে নামে, বা একদিকে)। সেই চূড়া-node-এ দাঁড়িয়ে উত্তর = node.val + left_gain + right_gain। কিন্তু এই node যখন তার parent-কে gain ফেরত দেবে, তখন একটাই arm দিতে পারে (node.val + max(left, right)) — কারণ একটা path parent-এ ঢুকে আবার এই node-এ ফিরে দুই arm নিতে পারে না।

12. Optimized intuition

একটা postorder gain(node) লেখো যা এই node থেকে নিচে নামা সর্বোচ্চ single-arm path-sum ফেরত দেয়। ভেতরে: দুই child-এর gain নাও, প্রত্যেকটা max(…, 0) দিয়ে ছেঁটে নাও (ঋণাত্মক branch বাদ)। তারপর best-কে node.val + left + right দিয়ে update করো (এই node চূড়া)। শেষে node.val + max(left, right) return করো। পুরো tree একবার ঘোরা → O(n)।

13. Thinking tweak

মোচড়: দুটো প্রশ্ন কখনো মিলিয়ে ফেলো না — "উপরে কী দেব" (one arm) আর "এখানে সেরা কত" (two arms, global)। return করো এক arm, কিন্তু update করো দুই arm দিয়ে। আর দ্বিতীয় মোচড়: ঋণাত্মক gain মানে সেই দিক এড়িয়ে যাও — max(gain, 0)। এই দুটো বুঝলে Hard problem-টা Diameter-এর মতোই সহজ হয়ে যায়।

14. Step-by-step dry run

root = [-10, 9, 20, null, null, 15, 7], best = -inf দিয়ে শুরু:

  1. gain(9): leaf → left=right=0, best = max(-inf, 9) = 9, return 9।
  2. gain(15): leaf → best = max(9, 15) = 15, return 15।
  3. gain(7): leaf → best = max(15, 7) = 15, return 7।
  4. gain(20): left=15, right=7 → best = max(15, 20+15+7) = 42, return 20 + max(15,7) = 35।
  5. gain(-10): left = max(9,0)=9, right = max(35,0)=35 → best = max(42, -10+9+35=34) = 42, return -10 + 35 = 25।
  6. উত্তর = best = 42।

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_path_sum(root):
    best = float("-inf")

    def gain(node):
        nonlocal best
        if node is None:                     # খালি subtree কোনো gain দেয় না
            return 0
        left = max(gain(node.left), 0)        # ঋণাত্মক arm বাদ
        right = max(gain(node.right), 0)      # ঋণাত্মক arm বাদ
        best = max(best, node.val + left + right)   # এই node চূড়া (∧)
        return node.val + max(left, right)    # উপরে শুধু এক arm যায়

    gain(root)
    return best


# ---- tests ----
assert max_path_sum(build_tree([1, 2, 3])) == 6
assert max_path_sum(build_tree([-10, 9, 20, None, None, 15, 7])) == 42
assert max_path_sum(build_tree([-3])) == -3        # একক ঋণাত্মক node
assert max_path_sum(build_tree([2, -1])) == 2      # -1 arm বাদ
assert max_path_sum(build_tree([-2, -1])) == -1    # কম খারাপটা
print("সব test pass!")

16. Line-by-line code explanation

  • best = float("-inf") — global সর্বোচ্চ; -inf দিয়ে শুরু যাতে একটামাত্র ঋণাত্মক node-ও সঠিকভাবে নেওয়া হয়।
  • if node is None: return 0 — খালি subtree gain ০; এটাই "ঋণাত্মক বাদ"-এর neutral মান।
  • left = max(gain(node.left), 0) — বাঁ arm-এর gain; ঋণাত্মক হলে ০ ধরে সেই দিক এড়িয়ে যাই।
  • right = max(gain(node.right), 0) — একই, ডান arm-এর জন্য।
  • best = max(best, node.val + left + right) — এই node-কে চূড়া ধরে দুই arm যোগ করা ∧-path; global update।
  • return node.val + max(left, right) — parent-কে শুধু এক arm দেওয়া যায়, তাই বড় arm-টা বেছে নিয়ে নিজের value-সহ ফেরত।

17. Output walkthrough

[1,2,3] দেয় 6 (পুরো ∧: 2→1→3) — assert pass। [-10,9,20,null,null,15,7] দেয় 42 (15→20→7, root এড়িয়ে)। একক node -3 দেয় -3 (নিতেই হবে), [2,-1] দেয় 2 (-1 arm বাদ), [-2,-1] দেয় -1 (কম খারাপ) — সব pass। শেষে print: সব test pass!।

18. Time complexity

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

19. Space complexity

O(h) — recursion call stack tree-র height h সমান গভীর হয় (balanced হলে O(log n), skewed হলে O(n))। best একটা মাত্র scalar, তাই বাড়তি memory নগণ্য।

20. Common mistakes

  • ঋণাত্মক arm না ছাঁটা (max(gain, 0) ভুলে যাওয়া) — লোকসানি branch যোগ হয়ে উত্তর ছোট হয়ে যায়।
  • best-কে 0 দিয়ে শুরু করা — সব-ঋণাত্মক tree-তে ভুল 0 দেয়; -inf লাগে কারণ অন্তত একটা node নিতেই হবে।
  • parent-কে দুই arm যোগ করে ফেরত দেওয়া — তখন path দু'বার এক node ছুঁয়ে ফেলে; return-এ শুধু max(left, right)।
  • global update আর return মান গুলিয়ে ফেলা — update দুই arm, return এক arm।

21. Which basic problem this inherits from

ভিত্তি: Diameter of Binary Tree (#18)-এর "height return করো, পাশে দুই-দিক যোগফল track করো" কাঠামো, আর Maximum Depth-এর postorder fold। height→gain আর "edge গোনা"→"value যোগ + ঋণাত্মক বাদ" — এই দুটো বদল করলেই Max Path Sum দাঁড়িয়ে যায়।

22. Similar harder problems

23. Pattern learned

Return-one-arm, update-two-arms (postorder): প্রতিটা node-এ child-দের থেকে single-arm মান নাও, ঋণাত্মক হলে ০ ধরে ছাঁটো; দুই arm যোগ করে global সর্বোচ্চ update করো (এই node চূড়া), কিন্তু parent-কে শুধু বড় arm ফেরত দাও। Diameter / max-path টাইপ সব problem-এর কঙ্কাল এটাই।

24. Final summary

ভবিষ্যতের আমাকে: "max path sum = প্রতিটা node-কে চূড়া ধরে দুই arm যোগ করে best update; উপরে এক arm দাও; ঋণাত্মক arm বাদ।" return-এক-arm আর update-দুই-arm আলাদা রাখা, আর max(gain, 0) — এই দুটোই মূল। 'tree-র যেকোনো জায়গায় সেরা path' টাইপ problem দেখলেই এই Diameter-জাত চালটা মনে করবে।

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