পাইথনে ডিরেকশন লিস্ট ব্যবহার করে বাইনারি ট্রি ট্রভার্সাল

একটি বাইনারি ট্রি এবং মুভ লিস্ট ["R", "L", "U"] দেওয়া থাকলে (R=ডান, L=বাম, U=প্যারেন্ট/আপ), রুট থেকে শুরু করে ট্রভার্সালের শেষে কোন নোডে পৌঁছালো তা বের করতে হবে।

উদাহরণ: ট্রি রুট=২, ডান=৪, ৪-এর বাম=৩, ডান=৫। মুভ: ["R","R","U","L"] → আউটপুট 3।

স্ট্যাক-ভিত্তিক সমাধান

past লিস্ট হিসেবে স্ট্যাক ব্যবহার করে প্যারেন্ট ট্র্যাক রাখা হয়।

• প্রতিটি মুভের আগে করেন্ট নোড স্ট্যাকে পুশ।
• L → বাম চাইল্ডে যান।
• R → ডান চাইল্ডে যান।
• U → স্ট্যাক থেকে পপ (খালি পপ), তারপর আবার পপ করে প্যারেন্ট নোডে যান।

পাইথন কোড

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

class Solution:
    def solve(self, root, moves):
        past = []
        for move in moves:
            past.append(root)
            if move == "L":
                root = root.left
            elif move == "R":
                root = root.right
            else:  # "U"
                past.pop()      # করেন্ট নোড বাদ দিন
                root = past.pop()  # প্যারেন্ট নোডে যান
        return root.val

# টেস্ট
ob = Solution()
root = TreeNode(2, None, TreeNode(4, TreeNode(3), TreeNode(5)))
print(ob.solve(root, ["R","R","U","L"]))  # 3

টাইম কমপ্লেক্সিটি: O(m) (m = মুভের সংখ্যা), স্পেস: O(h) (h = ট্রির উচ্চতা)।