পাইথনে BST-এর প্রি-অর্ডার ট্রাভার্সাল থেকে প্রতিটি ইন্টারন্যাল নোডের একচাইল্ড আছে কিনা যাচাই

একটি BST-এর প্রি-অর্ডার ট্রাভার্সাল দেওয়া আছে। যাচাই করতে হবে যে প্রতিটি ইন্টারন্যাল নোডের কি শুধু একটি চাইল্ড আছে।

উদাহরণ

ইনপুট: preorder = [22, 12, 13, 15, 14]

আউটপুট: True

অ্যালগরিদম

1. প্রতিটি নোডের জন্য পরবর্তী প্রি-অর্ডার সাকসেসর (next) এবং শেষ সাকসেসর (last) বের করুন।
2. যদি next * last < 0 হয় (অর্থাৎ একটা বড় একটা ছোট), তবে False।

উদাহরণ কোড

def solve(preorder):
    next_val = 0
    last_val = 0
    for i in range(len(preorder)-1):
        next_val = preorder[i] - preorder[i+1]
        last_val = preorder[i] - preorder[-1]
        if next_val * last_val < 0:
            return False
    return True

preorder = [22, 12, 13, 15, 14]
print(solve(preorder))  # Output: True

ইনপুট

[22, 12, 13, 15, 14]

আউটপুট

True