पायथन में जांचें कि BST के प्रत्येक आंतरिक नोड का ठीक एक बच्चा है या नहीं

मान लीजिए हमारे पास एक बाइनरी सर्च ट्री (BST) का प्रीऑर्डर ट्रैवर्सल है। हमें जांचना है कि क्या प्रत्येक आंतरिक नोड का केवल एक बच्चा है या नहीं।

उदाहरण के लिए, यदि preorder = [22, 12, 13, 15, 14] है, तो आउटपुट True होगा।

हल करने का तरीका

एक कुशल दृष्टिकोण: चूंकि एक नोड के सभी वंशज या तो छोटे होते हैं या बड़े, हम निम्न चरणों का पालन कर सकते हैं:

1. नोड का अगला प्रीऑर्डर उत्तराधिकारी प्राप्त करें
2. नोड का अंतिम प्रीऑर्डर उत्तराधिकारी प्राप्त करें
3. अब जब दोनों उत्तराधिकारी वर्तमान नोड से कम या अधिक हों तो जांच जारी रखें अन्यथा False लौटाएं

एल्गोरिदम:

1. next := 0, last := 0
2. प्रीऑर्डर के प्रत्येक तत्व के लिए:
   • next := preorder[i] - preorder[i+1]
   • last := preorder[i] - preorder का अंतिम मान
   • यदि next × last < 0, तो False लौटाएं
3. True लौटाएं

उदाहरण

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

preorder = [22, 12, 13, 15, 14]
print(solve(preorder))

इनपुट

[22, 12, 13, 15, 14]

आउटपुट

True