Binary Tree — hierarchy-র সবচেয়ে সরল রূপ

মূল চ্যালেঞ্জ recursion-ছাড়া post-order: two-stack trick — modified pre-order (node→right→left) চালিয়ে ফল উল্টে দিন।

from collections import deque

class Node:
    __slots__ = ('value', 'left', 'right')

    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

class BinaryTree:
    def __init__(self):
        self.root = None

    def insert_level_order(self, values):
        if not values:
            return
        self.root = Node(values[0])
        q, i = deque([self.root]), 1
        while q and i \< len(values):
            node = q.popleft()
            if i \< len(values):
                node.left = Node(values[i]); i += 1
                q.append(node.left)
            if i \< len(values):
                node.right = Node(values[i]); i += 1
                q.append(node.right)

    def preorder(self):
        out, stack = [], [self.root] if self.root else []
        while stack:
            n = stack.pop()
            out.append(n.value)
            if n.right: stack.append(n.right)   # ডান আগে push —
            if n.left:  stack.append(n.left)    # তাই বাঁ আগে pop
        return out

    def inorder(self):
        out, stack, cur = [], [], self.root
        while cur or stack:
            while cur:                  # বাঁয়ের দেয়াল ধরে নামো
                stack.append(cur)
                cur = cur.left
            cur = stack.pop()
            out.append(cur.value)       # node-এর কাজ
            cur = cur.right             # এবার ডান subtree
        return out

    def postorder(self):
        if not self.root:
            return []
        s1, s2 = [self.root], []
        while s1:
            n = s1.pop()
            s2.append(n)
            if n.left:  s1.append(n.left)
            if n.right: s1.append(n.right)
        return [n.value for n in reversed(s2)]

    def levelorder(self):
        out, q = [], deque([self.root] if self.root else [])
        while q:
            n = q.popleft()
            out.append(n.value)
            if n.left:  q.append(n.left)
            if n.right: q.append(n.right)
        return out

    def draw(self):
        lines = []
        def rec(n, depth):               # শুধু printer-এ recursion মাফ
            if not n: return
            rec(n.right, depth + 1)
            lines.append('    ' * depth + str(n.value))
            rec(n.left, depth + 1)
        rec(self.root, 0)
        return '\n'.join(lines)

if __name__ == '__main__':
    t = BinaryTree()
    t.insert_level_order(['A', 'B', 'C', 'D', 'E', 'F', 'G'])
    print(t.draw(), end='\n\n')

    # recursion-এর সাথে মিলিয়ে দেখা — দুই পথ, এক উত্তর
    assert t.preorder()  == ['A', 'B', 'D', 'E', 'C', 'F', 'G']
    assert t.inorder()   == ['D', 'B', 'E', 'A', 'F', 'C', 'G']
    assert t.postorder() == ['D', 'E', 'B', 'F', 'G', 'C', 'A']
    print('pre :', t.preorder())
    print('in  :', t.inorder())
    print('post:', t.postorder())
    print('lvl :', t.levelorder())
    print('সব assert পাস — iterative == recursive ✓')

প্রত্যাশিত output:

        G
    C
        F
A
        E
    B
        D

pre : ['A', 'B', 'D', 'E', 'C', 'F', 'G']
in  : ['D', 'B', 'E', 'A', 'F', 'C', 'G']
post: ['D', 'E', 'B', 'F', 'G', 'C', 'A']
lvl : ['A', 'B', 'C', 'D', 'E', 'F', 'G']
সব assert পাস — iterative == recursive ✓

(ছবিটা ৯০° ঘুরানো — head বাঁয়ে হেলান দিলেই চেনা tree।)

নিজে বাড়ান: size()/height() iterative; nested-text serialize/ deserialize; ৫০০০-node chain-এ recursive inorder-এর RecursionError vs আপনার iterative ভার্সন।