কনটেন্টে যান

004 — Binary Tree Postorder Traversal

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

Problem link ও উৎস

  • Original source: Classic tree traversal exercise
  • Platform: LeetCode — https://leetcode.com/problems/binary-tree-postorder-traversal/
  • Topic: trees
  • Difficulty: Easy
  • Pattern: Traversal order
  • Basic idea inherited from: Inorder, visit-মুহূর্ত সরানো — একই recursion কঙ্কাল, value নেওয়ার লাইনটা একদম শেষে

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

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

তোমাকে একটা binary tree-র root দেওয়া আছে। তোমার কাজ: সব node-এর value একটা list-এ ফেরত দাও, কিন্তু postorder ক্রমে — মানে Left → Right → Node।

প্রতিটা node-এ নিয়ম এক: আগে পুরো বাঁ-দিক সারো, তারপর পুরো ডান-দিক সারো, আর সবার শেষে নিজের value নাও। মানে parent তার দুই child-এর পরে আসে।

উদাহরণ
1
 \
  2
 /
3        ← postorder = [3, 2, 1]

Input ও output

উদাহরণ
Input : root = [1,null,2,3]
Output: [3, 2, 1]

Input : root = []        -> Output: []     (খালি tree)
Input : root = [1]       -> Output: [1]    (একটা node)

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

একটা folder মুছে ফেলার কথা ভাবো। তুমি কোনো folder সরাসরি delete করতে পারো না যতক্ষণ না তার ভেতরের সব subfolder আর file আগে মুছে যায়। তাই তুমি সবচেয়ে ভেতরের জিনিস আগে সারো, তারপর তাদের parent folder, এভাবে উপরে উঠতে থাকো — সবার শেষে root। এটাই postorder: children আগে, parent শেষে।

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

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

এটা সরাসরি Inorder traversal (#2) থেকে আসে। Inorder-এ value নেওয়া হতো দুই recursive call-এর মাঝখানে। এখানে শুধু সেই একটা লাইন নিচে সরিয়ে — দুই call-এর পরে — বসিয়ে দিলেই postorder। একই DFS trio (traversal-patterns.md), শুধু visit-মুহূর্ত বদলালো।

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

লুকানো logic হলো একটা ক্রমের সংজ্ঞা:

উদাহরণ
postorder(empty) = []
postorder(node)  = postorder(node.left) + postorder(node.right) + [node.val]

মানে node-এর value list-এর একদম শেষে আসে, তার দুই subtree সম্পূর্ণ লেখা হওয়ার পর। এর গভীর অর্থ: children আগে, parent পরে — যেকোনো কাজ যেখানে child-দের উত্তর না পেলে node-এর উত্তর দেওয়া যায় না (height, size, sum, delete), সেটার natural order এটাই।

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

একটা output list (জমা করার জন্য) আর recursion call stack (কোন path-এ আছি মনে রাখতে)। চাইলে recursion-এর বদলে একটা explicit stack-ও ব্যবহার করা যায় (../../04-stack-and-queue/), কিন্তু recursion-টা সবচেয়ে পরিষ্কার।

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

Tree self-similar (concept.md দেখো), তাই recursion প্রতিটা subtree-কে আলাদা ছোট tree হিসেবে সামলায়। call stack এমনিতেই "বাঁয়ে নামলাম, ডানে নামলাম, এখন উপরে উঠে নিজের value নেব" — এই ফেরার পথটা মনে রাখে। output list শুধু সঠিক ক্রমে value জড়ো করে।

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

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

"Traversal" নিজেই মূল কাজ, তাই brute force বলতে এখানে বোঝায় iterative ভাবে নিজের হাতে stack চালানো — recursion-কে অবিশ্বাস করে প্রতিটা node manually push/pop করা।

উদাহরণ
1) একটা সহজ কৌশল: preorder-এর মতো করো কিন্তু Node → Right → Left ক্রমে জমাও
2) সেই list-টা উল্টে (reverse) দাও
3) উল্টানো list-টাই postorder (Left → Right → Node)

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

Iterative version slow না (একই O(n)), কিন্তু লিখতে ও বুঝতে কঠিন — postorder-এ node-টা তখনই নিতে হবে যখন তার দুই child শেষ, তাই হাতে stack চালালে "এই node-এ কি দ্বিতীয়বার ফিরলাম?" track করতে হয়, বা reverse-ট্রিক মনে রাখতে হয়। recursion সেই সব book-keeping নিজেই করে দেয়, তাই কম bug, পরিষ্কার code। (iterative version লাগে শুধু খুব গভীর tree-তে recursion limit এড়াতে।)

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

মূল observation: value নেওয়ার মুহূর্তটাই পুরো খেলা। postorder = বাঁ-call আর ডান-call দুটোর পরে value নাও। এই এক লাইন উপরে নিলে preorder, মাঝে নিলে inorder — সম্পূর্ণ ভিন্ন ক্রম পাও। তিনটা traversal আসলে একই recursion, শুধু এক লাইনের অবস্থান আলাদা।

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

তিন লাইনের recursion: বাঁয়ে নামো, ডানে নামো, তারপর এই node-এর value append করো। base case-এ None হলে চুপচাপ ফিরে যাও। একবার পুরো tree ঘোরা — প্রতিটা node ঠিক একবার append হয়, আর সবসময় তার child-দের পরে।

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

মোচড়: তিনটা traversal আলাদা করে মুখস্থ কোরো না। একটাই কঙ্কাল মনে রাখো — "left, right, [value কোথায় বসবে]" — postorder মানে value-নেওয়ার লাইনটা একদম শেষে, দুই call-এর নিচে। আর মনে রাখো postorder-ই সেই order যেখানে "নিচের উত্তর দিয়ে আমার উত্তর" বানানো যায় — Maximum Depth (#1)-এর height-fold এটারই উপর দাঁড়ানো।

ছবিতে বোঝা

তীরগুলো recursion-এর ক্রম; ★ মানে এই মুহূর্তে value নেওয়া হলো (Left আর Right দুটোই শেষ হওয়ার পর):

উদাহরণ
        4
       / \
      2   6
     / \ / \
    1  3 5  7

হাঁটা: 1★ → 3★ → 2★ → 5★ → 7★ → 6★ → 4★
postorder = [1, 3, 2, 5, 7, 6, 4]   (root 4 সবার শেষে)

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

Input [1,null,2,3] (tree: 1-এর right 2, 2-এর left 3):

  1. visit(1): আগে left = None → চুপচাপ ফিরল।
  2. visit(1.right = 2): আগে তার left।
  3. visit(2.left = 3): left None ফিরল, right None ফিরল → এখন append 3। out = [3]।
  4. উপরে উঠে 2-এর right None → ফিরল → এখন append 2। out = [3, 2]।
  5. উপরে উঠে 1-এর দুই call শেষ → append 1। out = [3, 2, 1] → [3, 2, 1]।

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

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 postorder_traversal(root):
    out = []

    def visit(node):
        if node is None:        # base case: খালি subtree, কিছু নেই
            return
        visit(node.left)        # 1) আগে পুরো বাঁ-দিক
        visit(node.right)       # 2) তারপর পুরো ডান-দিক
        out.append(node.val)    # 3) সবার শেষে নিজের value (children-এর পরে)

    visit(root)
    return out


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

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

  • out = [] — সঠিক ক্রমে value জমানোর জায়গা।
  • def visit(node) — ভেতরের helper; out-কে closure দিয়ে ধরে রাখে।
  • if node is None: return — base case; খালি subtree থেকে কিছু যোগ হয় না।
  • visit(node.left) — আগে বাঁ-জগৎ সম্পূর্ণ সারো।
  • visit(node.right) — তারপর ডান-জগৎ সম্পূর্ণ সারো।
  • out.append(node.val) — মূল চাল: value নেওয়া হয় একদম শেষে, দুই child শেষ হওয়ার পর।
  • return out — পুরো postorder sequence।

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

[1,null,2,3] → [3, 2, 1] (dry run-এর সাথে মেলে)। খালি tree → []; একক node → [1]; perfect tree [4,2,6,1,3,5,7] → [1,3,2,5,7,6,4] (root 4 সবার শেষে)। সব assert pass, শেষে print: সব test pass!।

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

সময়

O(n) — প্রতিটা node ঠিক একবার visit আর একবার append হয়।

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

O(n) output list-এর জন্য; recursion stack আলাদাভাবে O(h) (h = height) — concept.md-র table অনুযায়ী balanced-এ O(log n), chain-এ O(n)।

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

  • value নেওয়ার লাইন ভুল জায়গায় বসিয়ে অজান্তে preorder/inorder বানিয়ে ফেলা।
  • left আর right call উল্টে দেওয়া → ক্রম উল্টে যায়।
  • base case বাদ দিয়ে None.left ছোঁয়া → AttributeError।

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

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

ভিত্তি: Inorder traversal (#2)-র sandwich আর traversal-patterns.md-র DFS trio। inorder বুঝলে postorder শুধু value-নেওয়ার লাইনটা নিচে নামানোর ব্যাপার। আর concept.md-র recursion ভিত্তি তো আছেই।

পরের অনুশীলন

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

DFS visit-order (children-before-parent): একটাই recursion কঙ্কাল (left / right / value), value একদম শেষে নিলে postorder। এটাই সেই order যেখানে child-দের উত্তর parent-কে খাওয়ানো যায় — tree DP-র মেরুদণ্ড।

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

ভবিষ্যতের আমাকে: "postorder = Left, Right, তারপর নিজে — value সবার শেষে।" যখনই কোনো problem বলবে "আগে child-দের সারো, তারপর node-এর কাজ করো" (delete, height, sum), postorder-এর কথা মনে পড়বে। তিন traversal একসাথে মনে রাখার চাবি: শুধু value-নেওয়ার লাইনটা কোথায় বসছে।

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