Find pairs with given sum such that pair elements lie in different BSTs | A utility function to create a new BST node with key as given num ; Constructor to create a new node ; A utility function to insert a given key to BST ; store storeInorder traversal in auxiliary array ; Function to find pair for given sum in different bst vect1 [ ] -- > stores storeInorder traversal of first bst vect2 [ ] -- > stores storeInorder traversal of second bst ; Initialize two indexes to two different corners of two lists . ; find pair by moving two corners . ; If we found a pair ; If sum is more , move to higher value in first lists . ; If sum is less , move to lower value in second lists . ; Prints all pairs with given " sum " such that one element of pair is in tree with root1 and other node is in tree with root2 . ; Store inorder traversals of two BSTs in two lists . ; Now the problem reduces to finding a pair with given sum such that one element is in vect1 and other is in vect2 . ; Driver Code ; first BST ; second BST
class newNode : NEW_LINE INDENT def __init__ ( self , data ) : NEW_LINE INDENT self . data = data NEW_LINE self . left = None NEW_LINE self . right = None NEW_LINE DEDENT DEDENT def insert ( root , key ) : NEW_LINE INDENT if root == None : NEW_LINE INDENT return newNode ( key ) NEW_LINE DEDENT if root . data > key : NEW_LINE INDENT root . left = insert ( root . left , key ) NEW_LINE DEDENT else : NEW_LINE INDENT root . right = insert ( root . right , key ) NEW_LINE DEDENT return root NEW_LINE DEDENT def storeInorder ( ptr , vect ) : NEW_LINE INDENT if ptr == None : NEW_LINE INDENT return NEW_LINE DEDENT storeInorder ( ptr . left , vect ) NEW_LINE vect . append ( ptr . data ) NEW_LINE storeInorder ( ptr . right , vect ) NEW_LINE DEDENT def pairSumUtil ( vect1 , vect2 , Sum ) : NEW_LINE INDENT left = 0 NEW_LINE right = len ( vect2 ) - 1 NEW_LINE while left < len ( vect1 ) and right >= 0 : NEW_LINE INDENT if vect1 [ left ] + vect2 [ right ] == Sum : NEW_LINE INDENT print ( " ( " , vect1 [ left ] , " , " , vect2 [ right ] , " ) , " , end = " ▁ " ) NEW_LINE left += 1 NEW_LINE right -= 1 NEW_LINE DEDENT elif vect1 [ left ] + vect2 [ right ] < Sum : NEW_LINE INDENT left += 1 NEW_LINE DEDENT else : NEW_LINE INDENT right -= 1 NEW_LINE DEDENT DEDENT DEDENT def pairSum ( root1 , root2 , Sum ) : NEW_LINE INDENT vect1 = [ ] NEW_LINE vect2 = [ ] NEW_LINE storeInorder ( root1 , vect1 ) NEW_LINE storeInorder ( root2 , vect2 ) NEW_LINE pairSumUtil ( vect1 , vect2 , Sum ) NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT root1 = None NEW_LINE root1 = insert ( root1 , 8 ) NEW_LINE root1 = insert ( root1 , 10 ) NEW_LINE root1 = insert ( root1 , 3 ) NEW_LINE root1 = insert ( root1 , 6 ) NEW_LINE root1 = insert ( root1 , 1 ) NEW_LINE root1 = insert ( root1 , 5 ) NEW_LINE root1 = insert ( root1 , 7 ) NEW_LINE root1 = insert ( root1 , 14 ) NEW_LINE root1 = insert ( root1 , 13 ) NEW_LINE root2 = None NEW_LINE root2 = insert ( root2 , 5 ) NEW_LINE root2 = insert ( root2 , 18 ) NEW_LINE root2 = insert ( root2 , 2 ) NEW_LINE root2 = insert ( root2 , 1 ) NEW_LINE root2 = insert ( root2 , 3 ) NEW_LINE root2 = insert ( root2 , 4 ) NEW_LINE Sum = 10 NEW_LINE pairSum ( root1 , root2 , Sum ) NEW_LINE DEDENT