2728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788
# This class defines a node in a Binary Search Tree
class TreeNode:
    # Constructor initializes value and children
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

# This class contains the brute force solution
class Solution:
    # Function checks if pair with target sum exists
    def findTarget(self, root, k):
        # List stores inorder traversal values
        inorder = []
        # Fill list using helper
        self.inorderTraversal(root, inorder)

        # Two pointers for searching
        left = 0
        right = len(inorder) - 1

        # Loop until pointers meet
        while left < right:
            # Calculate sum of current pair
            total = inorder[left] + inorder[right]

            # If sum equals k, return True
            if total == k:
                return True
            # If sum smaller, move left pointer
            elif total < k:
                left += 1
            # If sum larger, move right pointer
            else:
                right -= 1

        # If no pair found, return False
        return False

    # Helper function to do inorder traversal
    def inorderTraversal(self, root, inorder):
        # If node is None, stop recursion
        if not root:
            return
        # Visit left subtree
        self.inorderTraversal(root.left, inorder)
        # Add current node value
        inorder.append(root.val)
        # Visit right subtree
        self.inorderTraversal(root.right, inorder)

# Function prints inorder traversal
def printInOrder(root):
    if not root:
        return
    printInOrder(root.left)
    print(root.val, end=" ")
    printInOrder(root.right)

# Driver code
if __name__ == "__main__":
    # Create sample BST
    root = TreeNode(7)
    root.left = TreeNode(3)
    root.right = TreeNode(15)
    root.right.left = TreeNode(9)
    root.right.right = TreeNode(20)

    # Print inorder traversal
    print("Tree Initialized: ", end="")
    printInOrder(root)
    print()

    # Create solution object
    solution = Solution()

    # Define target sum
    target = 22

    # Check if pair exists
    exists = solution.findTarget(root, target)

    # Print result
    if exists:
        print(f"Pair with sum {target} exists.")
    else:
        print(f"Pair with sum {target} does not exist.")
12345678910111213141516171819202122232425262728293031323334353637383940414243<