দুটি বাইনারি সার্চ ট্রি (BST) এবং একটি টার্গেট সম (sum) দেওয়া আছে। দুটি BST থেকে এক-একটি উপাদান নিয়ে যেসব পেয়ার (pair) বने যেন তাদের যোগফল টার্গেট সমের সমান হয়, সেগুলো খুঁজে বের করতে হবে।
উদাহরণ
ইনপুট: Sum = 12
BST ১: ৯, ১১, ৪, ৭, ২, ৬, ১৫, ১৪
BST ২: ৬, ১৯, ৩, ২, ৪, ৫
আউটপুট: [(6, 6), (7, 5), (9, 3)]
সমাধানের পদ্ধতি
- দুই BST-র ইন-অর্ডার ট্রাভার্সাল (In-order traversal) করুন → সাজানো অ্যারে পাওয়া যাবে।
- দুটি সাজানো অ্যারে আছে: trav1 (ascending), trav2 (ascending)।
- টু-পয়েন্টার (Two-pointer) টেকনিক: trav1-র শুরু (left) এবং trav2-র শেষ (right) থেকে শুরু করুন।
- যোগফল == Sum হলে পেয়ার সংরক্ষণ করুন, left++, right--।
- যোগফল < Sum হলে left++। যোগফল > Sum হলে right--।
পাইথন কোড
class ListNode:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
def insert(root, key):
if root is None:
return ListNode(key)
if root.data > key:
root.left = insert(root.left, key)
else:
root.right = insert(root.right, key)
return root
def storeInorder(ptr, traversal):
if ptr is None:
return
storeInorder(ptr.left, traversal)
traversal.append(ptr.data)
storeInorder(ptr.right, traversal)
def solve(trav1, trav2, Sum):
left = 0
right = len(trav2) - 1
res = []
while left < len(trav1) and right >= 0:
s = trav1[left] + trav2[right]
if s == Sum:
res.append((trav1[left], trav2[right]))
left += 1
right -= 1
elif s < Sum:
left += 1
else:
right -= 1
return res
def get_pair_sum(root1, root2, Sum):
trav1 = []
trav2 = []
storeInorder(root1, trav1)
storeInorder(root2, trav2)
return solve(trav1, trav2, Sum)
root1 = None
for element in [9, 11, 4, 7, 2, 6, 15, 14]:
root1 = insert(root1, element)
root2 = None
for element in [6, 19, 3, 2, 4, 5]:
root2 = insert(root2, element)
Sum = 12
print(get_pair_sum(root1, root2, Sum))
ইনপুট
[9,11,4,7,2,6,15,14], [6,19,3,2,4,5], 12
আউটপুট
[(6, 6), (7, 5), (9, 3)]
