পাইথনে বাইনারি ট্রি-র একই লেভেলের লিফ নোডের ডেটা যোগফলের গুণফল

একটি বাইনারি ট্রি দেওয়া আছে। প্রতিটি লেভেলের লিফ নোড (leaf node)-গুলোর ডেটা যোগফল বের করুন। যেসব লেভেলে লিফ নেই, সেগুলো বাদ দিন। সব লেভেলের লিফ যোগফলের গুণফল (multiplication) ফেরত দিন।

উদাহরণ

ট্রি: 8 / \ 8 6 / \ \ 9 7 10 / \ / \ 2 12 5 11

লেভেল ৩: লিফ = ৯ (যোগফল ৯)

লেভেল ৪: লিফ = ২, ১২, ৫, ১১ (যোগফল ৩০)

আউটপুট: ৯ × ৩০ = ২৭০

সমাধানের পদ্ধতি

লেভেল অর্ডার ট্রাভার্সাল (Level Order Traversal / BFS) ব্যবহার করা হয়।
প্রতিটি লেভেলে লিফ নোড আছে কিনা চেক করা হয়।
লিফ থাকলে তাদের ডেটা যোগফল নেওয়া হয় এবং গ্লোবাল গুণফলে গুণ করা হয়।
কিউ (queue) ব্যবহার করে লেভেল বাই লেভেল প্রসেস করা হয়।

পাইথন কোড


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

def isLeaf(root):
    return root.left is None and root.right is None

def find_res(root):
    if not root:
        return 0
    res = 1
    que = [root]
    
    while True:
        no_of_nodes = len(que)
        if no_of_nodes == 0:
            break
        sum_level = 0
        found_leaf = False
        while no_of_nodes > 0:
            curr_node = que[0]
            if isLeaf(curr_node):
                found_leaf = True
                sum_level += curr_node.data
            que.pop(0)
            if curr_node.left:
                que.append(curr_node.left)
            if curr_node.right:
                que.append(curr_node.right)
            no_of_nodes -= 1
        if found_leaf:
            res *= sum_level
    return res

# Tree construction
root = TreeNode(8)
root.left = TreeNode(8)
root.right = TreeNode(6)
root.left.right = TreeNode(7)
root.left.left = TreeNode(9)
root.left.right.left = TreeNode(2)
root.left.right.right = TreeNode(12)
root.right.right = TreeNode(10)
root.right.right.left = TreeNode(5)
root.right.right.right = TreeNode(11)

print(find_res(root))

ইনপুট

ট্রি গঠন: লেভেল ওয়াইজ নোড ভ্যালু দিয়ে