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)