004 — Binary Tree Postorder Traversal¶

Source¶

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 নেওয়ার লাইনটা একদম শেষে

1. Problem in simple words¶

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

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

1
 \
  2
 /
3        ← postorder = [3, 2, 1]

2. Which basic idea does this inherit from?¶

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

3. What is the hidden math or logic?¶

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

4. Which data structure is needed?¶

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

5. Why this data structure fits¶

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

6. Real-life analogy¶

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

7. Visual explanation¶

তীরগুলো 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 সবার শেষে)

8. Example input and output¶

Input : root = [1,null,2,3]
Output: [3, 2, 1]

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

9. Brute force thinking¶

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

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

10. Why brute force is slow¶

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

11. Key observation¶

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

12. Optimized intuition¶

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

13. Thinking tweak¶

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

14. Step-by-step dry run¶

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

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

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

16. Line-by-line code explanation¶

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।

17. Output walkthrough¶

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

18. Time complexity¶

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

19. Space complexity¶

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

20. Common mistakes¶

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

21. Which basic problem this inherits from¶

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

22. Similar harder problems¶

Binary Tree Maximum Path Sum (postorder-এ child-দের contribution জমিয়ে node-এ সিদ্ধান্ত) — https://leetcode.com/problems/binary-tree-maximum-path-sum/ (এই tracker-এর #23)
Diameter of Binary Tree (postorder height + পাশে diameter update) — https://leetcode.com/problems/diameter-of-binary-tree/ (#18)
Balanced Binary Tree (postorder-এ height ফেরত দিয়ে balanced যাচাই) — https://leetcode.com/problems/balanced-binary-tree/ (#10)

23. Pattern learned¶

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

24. Final summary¶

ভবিষ্যতের আমাকে: "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।