পাইথনে ট্রির বামপাশের গভীরতম নোড খুঁজে বের করার প্রোগ্রাম

ধরা যাক একটি বাইনারি ট্রি আছে, আমাদের সবচেয়ে গভীর নোডের মান খুঁজে বের করতে হবে। যদি একাধিক গভীরতম নোড থাকে, তবে বামপাশের নোডটি ফেরত দিন।

উদাহরণ ট্রি হলে আউটপুট 4, কারণ 4 এবং 7 দুটোই গভীরতম কিন্তু 4 বামপাশে।

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

• queue := [root]
• left_max := root.val
• যখন queue খালি নয়:
• level_size := len(queue)
• i = 0 থেকে level_size-1 পর্যন্ত:
• temp := queue.pop(0)
• যদি i == 0 হয়, left_max := temp.val
• temp.left এবং temp.right queue-এ অ্যাপেন্ড করুন।
• left_max ফেরত দিন।

উদাহরণ কোড

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

class Solution:
    def solve(self, root):
        queue = [root]
        left_max = root.val
        while len(queue) > 0:
            level_size = len(queue)
            for i in range(level_size):
                temp = queue.pop(0)
                if i == 0:
                    left_max = temp.val
                if temp.left:
                    queue.append(temp.left)
                if temp.right:
                    queue.append(temp.right)
        return left_max

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)

আউটপুট

4