পাইথনে বাইনারি ট্রির ইন-অর্ডার ট্রাভার্সাল (ইটারেটিভ) প্রোগ্রাম

ধরা যাক একটি বাইনারি ট্রি আছে, আমাদের ইন-অর্ডার ট্রাভার্সাল (বাম সাবট্রি → রুট → ডান সাবট্রি) একটি তালিকা হিসেবে ফেরত দিতে হবে। ইটারেটিভ পদ্ধতিতে সমাধান করতে হবে।

উদাহরণ ট্রি হলে আউটপুট [12, 13, 4, 16, 7, 14, 22]।

সমাধানের ধাপসমূহ

• inorder := [], stack := []
• সত্য হলে লুপ:
• যদি root null নয়: stack-এ root পুশ করুন, root := root.left
• অন্যথায় যদি stack খালি নয়: root := stack.pop(), inorder-এ root.val অ্যাপেন্ড করুন, root := root.right
• অন্যথায়: ব্রেক করুন।
• inorder ফেরত দিন।

উদাহরণ কোড

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

class Solution:
    def solve(self, root):
        inorder = []
        stack = []
        while True:
            if root:
                stack.append(root)
                root = root.left
            elif stack:
                root = stack.pop()
                inorder.append(root.val)
                root = root.right
            else:
                break
        return inorder

ob = Solution()
root = TreeNode(13)
root.left = TreeNode(12)
root.right = TreeNode(14)
root.right.left = TreeNode(16)
root.right.right = TreeNode(22)
root.right.left.left = TreeNode(4)
root.right.left.right = TreeNode(7)
print(ob.solve(root))

ইনপুট

root = TreeNode(13) root.left = TreeNode(12) root.right = TreeNode(14) root.right.left = TreeNode(16) root.right.right = TreeNode(22) root.right.left.left = TreeNode(4) root.right.left.right = TreeNode(7)

আউটপুট

[12, 13, 4, 16, 7, 14, 22]