পাইথনে বাইনারি ট্রি-তে BST-এর সর্বোচ্চ যোগফলের মান বের করার প্রোগ্রাম

একটি বাইনারি ট্রি দেওয়া আছে। সেটির সাবট্রি-গুলোর মধ্যে বাইনারি সার্চ ট্রি (BST) আছে কিনা তা বের করতে হবে এবং সবচেয়ে বড় BST-এর নোডগুলোর যোগফল বের করতে হবে। যোগফল বের করতে BST-র প্রতিটি নোডের মান যোগ করা হয়। আউটপুট হিসেবে যোগফলের মান রিটার্ন করতে হবে।

ইনপুট ট্রি:

আউটপুট হবে ১২।

দেওয়া বাইনারি ট্রি-তে BST:

নোডগুলোর যোগফল = ১২।

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

• c := 0, m := null, value := 0
• recurse() ফাংশন সংজ্ঞায়িত করুন। এটি node গ্রহণ করবে:
  • যদি node null নয় হয়:
    • left_val := recurse(node.left)
    • right_val := recurse(node.right)
    • count := negative infinity
    • যদি (node.left == null বা node.left.val <= node.val) এবং (node.right == null বা node.val <= node.right.val) হয়:
      • count := left_val + right_val + 1
    • যদি count > c হয়:
      • c := count, m := node
    • count ফেরত দিন
  • 0 ফেরত দিন
• calculate_sum() ফাংশন সংজ্ঞায়িত করুন। এটি root গ্রহণ করবে:
  • যদি root != null হয়:
    • calculate_sum(root.left)
    • value := value + root.val
    • calculate_sum(root.right)
• recurse(root)
• calculate_sum(m)
• value ফেরত দিন

উদাহরণ

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

def insert(temp, data):
    que = []
    que.append(temp)
    while len(que):
        temp = que[0]
        que.pop(0)
        if not temp.left:
            if data is not None:
                temp.left = TreeNode(data)
            else:
                temp.left = TreeNode(0)
            break
        else:
            que.append(temp.left)
        if not temp.right:
            if data is not None:
                temp.right = TreeNode(data)
            else:
                temp.right = TreeNode(0)
            break
        else:
            que.append(temp.right)

def make_tree(elements):
    tree = TreeNode(elements[0])
    for element in elements[1:]:
        insert(tree, element)
    return tree

def solve(root):
    c, m, value = 0, None, 0
    def recurse(node):
        nonlocal c, m
        if node:
            left_val = recurse(node.left)
            right_val = recurse(node.right)
            count = -float("inf")
            if (node.left is None or node.left.val <= node.val) and (node.right is None or node.val <= node.right.val):
                count = left_val + right_val + 1
            if count > c:
                c = count
                m = node
            return count
        return 0
    def calculate_sum(root):
        nonlocal value
        if root is not None:
            calculate_sum(root.left)
            value += root.val
            calculate_sum(root.right)
    recurse(root)
    calculate_sum(m)
    return value

tree = make_tree([1, 4, 6, 3, 5])
print(solve(tree))

ইনপুট

tree = make_tree([1, 4, 6, 3, 5])
print(solve(tree))

আউটপুট

12