L.C. 653 -Two Sum IV - Input is a BST.py

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:     
    def findTarget(self, root: Optional[TreeNode], k: int) -> bool:
        '''
        print(root.val)
        #print(root.left.left.left.val)
        if root.left.left.left==None:
            print("The end")
        print(root.right.val)
        '''
        def findPair(root, target, set):
            
            if root != None:
                print(root.val)
            # base case
            if root is None:
                return False

            # return true if pair is found in the left subtree; otherwise, continue
            # processing the node
            if findPair(root.right, target, set):
                return True

            # if a pair is formed with the current node, print the pair and return true
            if target - root.val in set:
                
                print("Pair found", (target - root.val, root.val))
                return True

            # insert the current node's value into the set
            else:
                set.add(root.val)

            # search in the right subtree
            return findPair(root.left, target, set)
        s = set()

        if not findPair(root, k, s):
            #print(root.val)
            print("Pair does not exist")
            return False
        else:
            #print(root.val)
            return True
# 1. https://www.techiedelight.com/find-pair-with-given-sum-bst/
# 2. https://leetcode.com/problems/two-sum-iv-input-is-a-bst/discuss/1420743/Python-Solution-using-iterators-explained