Two Sum in a BST

The tests write a tree as a level-order list (row by row, left to right) with None for a missing child: [3, 9, 20, None, None, 15, 7] is a root 3 with children 9 and 20, where 20 has children 15 and 7. All trees in this topic that are called BSTs have different values.

Return True if there are two different nodes whose values add up to k.

For [5, 3, 6, 2, 4, None, 7] and k = 9 the answer is True (3 + 6); for k = 28 it is False.

Examples

Example 1

Input:

find_target(root, 9)  # root = [5, 3, 6, 2, 4, None, 7]

Output:

True

Example 2

Input:

find_target(root, 28)  # root = [5, 3, 6, 2, 4, None, 7]

Output:

False

Constraints

• 0 <= number of nodes <= 100000
• The tree is a BST, not deeper than 800 levels.
• -10**9 <= k <= 2 * 10**9