ইন-অর্ডার ট্রাভার্সাল দিয়ে বাইনারি ট্রিতে সর্বোচ্চ মান খুঁজে বের করার পাইথন প্রোগ্রাম

বাইনারি সার্চ ট্রি (BST) প্রোপার্টি ব্যবহার না করে, সাধারণ বাইনারি ট্রিতে ইন-অর্ডার ট্রাভার্সাল দিয়ে সর্বোচ্চ মান খুঁজে বের করা হয়।

উদাহরণ

class BinaryTreeNode:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None
    
    def insert_left(self, node):
        self.left = node
    
    def insert_right(self, node):
        self.right = node
    
    def find(self, key):
        if self.key == key:
            return self
        for child in (self.left, self.right):
            if child:
                found = child.find(key)
                if found:
                    return found
        return None
    
    def find_max_inorder(self):
        """ইন-অর্ডার ট্রাভার্সাল দিয়ে ম্যাক্স বের করে"""
        max_val = [float('-inf')]
        self._inorder_max_helper(max_val)
        return max_val[0]
    
    def _inorder_max_helper(self, max_val):
        if self.left:
            self.left._inorder_max_helper(max_val)
        if self.key > max_val[0]:
            max_val[0] = self.key
        if self.right:
            self.right._inorder_max_helper(max_val)

# ইন্টারেক্টিভ ডেমো
root = None
while True:
    cmd = input("কমান্ড (insert/largest/quit): ").split()
    if not cmd: continue
    if cmd[0] == 'insert':
        data = int(cmd[1])
        node = BinaryTreeNode(data)
        if cmd[2] == 'at':
            root = node
        elif cmd[2] == 'left':
            parent = root.find(int(cmd[4])) if root else None
            if parent: parent.insert_left(node)
        elif cmd[2] == 'right':
            parent = root.find(int(cmd[4])) if root else None
            if parent: parent.insert_right(node)
    elif cmd[0] == 'largest':
        if root:
            print("সর্বোচ্চ মান:", root.find_max_inorder())
    elif cmd[0] == 'quit':
        break

আউটপুট

কমান্ড (insert/largest/quit): insert 8 at root
কমান্ড (insert/largest/quit): insert 9 left of 8
কমান্ড (insert/largest/quit): insert 4 right of 8
কমান্ড (insert/largest/quit): largest
সর্বোচ্চ মান: 9
কমান্ড (insert/largest/quit): quit

ব্যাখ্যা

• ইন-অর্ডার ট্রাভার্সাল (লেফট -> রুট -> রাইট) সব নোড ভিজিট করে।

• হেল্পার ফাংশন মিউটেবল লিস্ট max_val দিয়ে ম্যাক্স ট্র্যাক করে।

• BST হলে শুধু রাইটমোস্ট নোডই ম্যাক্স (O(h) টাইম)۔

• সাধারণ ট্রিতে O(n) টাইম লাগে।