পাইথনে বাইনারি ট্রি কমপ্লিট কিনা যাচাই করার প্রোগ্রাম

মনে করুন একটি বাইনারি ট্রি আছে। এটি কমপ্লিট বাইনারি ট্রি কিনা যাচাই করতে হবে। কমপ্লিট বাইনারি ট্রিতে সব লেভেল নোড দিয়ে পূরিত থাকে শেষ লেভেল বাদে, এবং শেষ লেভেলের নোডগুলো যতটা সম্ভব বাম পাশে থাকে।

ইনপুট ট্রির ছবি দেওয়া আছে, আউটপুট True।

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

• q := ডबल এন্ডেড কিউ, রুট যোগ করুন
• flag := False
• যখন q খালি নয়,
  • temp := q.popleft()
  • যদি temp null হয়, flag = True
  • অন্যথায় যদি flag True হয় এবং temp নন-নাল হয়, False ফেরত দিন
  • অন্যথায়, temp.left এবং temp.right q-এ যোগ করুন
• True ফেরত দিন

উদাহরণ

from collections import deque
class TreeNode:
    def __init__(self, data, left = None, right = None):
        self.data = data
        self.left = left
        self.right = right

class Solution:
    def solve(self, root):
        q = deque()
        q.append(root)
        flag = False
        while q:
            temp = q.popleft()
            if not temp:
                flag = True
            elif flag and temp:
                return False
            else:
                q.append(temp.left)
                q.append(temp.right)
        return True

ob = Solution()
root = TreeNode(9)
root.left = TreeNode(7)
root.right = TreeNode(10)
root.left.left = TreeNode(6)
root.left.right = TreeNode(8)
print(ob.solve(root))

ইনপুট

root = TreeNode(9) root.left = TreeNode(7) root.right = TreeNode(10) root.left.left = TreeNode(6) root.left.right = TreeNode(8)

আউটপুট

True