Find all the pairs with given sum in a BST | Set 2 | A binary tree node ; Function to append a node to the BST ; If the tree is empty , return a new node ; Otherwise , recur down the tree ; Function to find the target pairs ; LeftList which stores the left side values ; RightList which stores the right side values ; curr_left pointer is used for left side execution and curr_right pointer is used for right side execution ; Storing the left side values into LeftList till leaf node not found ; Storing the right side values into RightList till leaf node not found ; Last node of LeftList ; Last node of RightList ; To prevent repetition like 2 , 6 and 6 , 2 ; Delete the last value of LeftList and make the execution to the right side ; Delete the last value of RightList and make the execution to the left side ; ( left value + right value ) = target then print the left value and right value Delete the last value of left and right list and make the left execution to right side and right side execution to left side ; Driver code
class Node : NEW_LINE INDENT def __init__ ( self , key ) : NEW_LINE INDENT self . data = key NEW_LINE self . left = None NEW_LINE self . right = None NEW_LINE DEDENT DEDENT def AddNode ( root , data ) : NEW_LINE INDENT if ( root == None ) : NEW_LINE INDENT root = Node ( data ) NEW_LINE return root NEW_LINE DEDENT if ( root . data < data ) : NEW_LINE INDENT root . right = AddNode ( root . right , data ) NEW_LINE DEDENT elif ( root . data > data ) : NEW_LINE INDENT root . left = AddNode ( root . left , data ) NEW_LINE DEDENT return root NEW_LINE DEDENT def TargetPair ( node , tar ) : NEW_LINE INDENT LeftList = [ ] NEW_LINE RightList = [ ] NEW_LINE curr_left = node NEW_LINE curr_right = node NEW_LINE while ( curr_left != None or curr_right != None or len ( LeftList ) > 0 and len ( RightList ) > 0 ) : NEW_LINE INDENT while ( curr_left != None ) : NEW_LINE INDENT LeftList . append ( curr_left ) NEW_LINE curr_left = curr_left . left NEW_LINE DEDENT while ( curr_right != None ) : NEW_LINE INDENT RightList . append ( curr_right ) NEW_LINE curr_right = curr_right . right NEW_LINE DEDENT LeftNode = LeftList [ - 1 ] NEW_LINE RightNode = RightList [ - 1 ] NEW_LINE leftVal = LeftNode . data NEW_LINE rightVal = RightNode . data NEW_LINE if ( leftVal >= rightVal ) : NEW_LINE INDENT break NEW_LINE DEDENT if ( leftVal + rightVal < tar ) : NEW_LINE INDENT del LeftList [ - 1 ] NEW_LINE curr_left = LeftNode . right NEW_LINE DEDENT elif ( leftVal + rightVal > tar ) : NEW_LINE INDENT del RightList [ - 1 ] NEW_LINE curr_right = RightNode . left NEW_LINE DEDENT else : NEW_LINE INDENT print ( LeftNode . data , RightNode . data ) NEW_LINE del RightList [ - 1 ] NEW_LINE del LeftList [ - 1 ] NEW_LINE curr_left = LeftNode . right NEW_LINE curr_right = RightNode . left NEW_LINE DEDENT DEDENT DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT root = None NEW_LINE root = AddNode ( root , 2 ) NEW_LINE root = AddNode ( root , 6 ) NEW_LINE root = AddNode ( root , 5 ) NEW_LINE root = AddNode ( root , 3 ) NEW_LINE root = AddNode ( root , 4 ) NEW_LINE root = AddNode ( root , 1 ) NEW_LINE root = AddNode ( root , 7 ) NEW_LINE sum = 8 NEW_LINE TargetPair ( root , sum ) NEW_LINE DEDENT