পাইথনে বাইনারি ট্রির দিয়ে गये ভার্টিকাল লেভেল সর্টেড কিনা চেক করা

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

ইনপুট: l=-1, ট্রি চিত্রে দেওয়া আছে → আউটপুট True (লেভেল -1-এ উপাদান 3,7 যা সর্টেড)।

সমাধানের ধাপসমূহ (BFS + লেভেল ট্র্যাকিং)

• যদি root is None: return True
• previous_value = -inf, current_level=0
• কিউ (deque) ব্যবহার করে BFS: (root, 0) এনকিউ
• while কিউ নন-এম্পটি:
  • current_node, current_level = ডিকিউ
  • যদি current_level == level:
    • যদি previous_value <= current_node.val: previous_value = current_node.val
    • অন্যথায়: return False
  • বাম চাইল্ড: (left, current_level-1) এনকিউ
  • ডান চাইল্ড: (right, current_level+1) এনকিউ
• return True

উদাহরণ

from collections import deque
from sys import maxsize
INT_MIN = -maxsize
class TreeNode:
    def __init__(self, key):
        self.val = key
        self.left = None
        self.right = None
def are_elements_sorted(root, level):
    if root is None: return True
    previous_value = INT_MIN
    current_level = 0
    current_node = TreeNode(0)
    q = deque()
    q.append((root, 0))
    while q:
        current_node = q[0][0]
        current_level = q[0][1]
        q.popleft()
        if current_level == level:
            if previous_value <= current_node.val:
                previous_value = current_node.val
            else:
                return False
        if current_node.left:
            q.append((current_node.left, current_level - 1))
        if current_node.right:
            q.append((current_node.right, current_level + 1))
    return True
root = TreeNode(2)
root.left = TreeNode(3)
root.right = TreeNode(6)
root.left.left = TreeNode(8)
root.left.right = TreeNode(5)
root.left.right.left = TreeNode(7)
level = -1
print(are_elements_sorted(root, level))

ইনপুট

root = TreeNode(2)
root.left = TreeNode(3)
root.right = TreeNode(6)
root.left.left = TreeNode(8)
root.left.right = TreeNode(5)
root.left.right.left = TreeNode(7)
level = -1

আউটপুট

True