653. Two Sum IV - Input is a BST

Two Sum IV - Input is a BST - LeetCode

Use any type of traversal, and store visited nodes in a dictionary.

For each visited node, check that the corresponding value to reach target is in dict (target - node.val). If value is in dict then terminate traversal and return True. If value not found in dict then add current value to dict.

Code using Inorder Traversal

# 653. Two Sum IV - Input is a BST

def findTarget(root, K):

    # Use dict to store visited nodes
    dict = {}

    # Inorder traversal
    def inorder(node):
        if node:

            # Check if corresponding value to reach target is present in dict, if not, then add value to dict
            if K - node.val in dict:
                return True
            else:
                dict[node.val] = True

            # If corresponding value found in dict, temrinate recursion early and return True
            if inorder(node.left) or inorder(node.right):
                return True
            else:
                return False

    return inorder(root)