Reference: LeetCode
Difficulty: Easy

Problem

Given a Binary Search Tree and a target number, return true if there exist two elements in the BST such that their sum is equal to the given target.

Example: 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
Input: 
    5
   / \
  3   6
 / \   \
2   4   7
Target = 9
Output: True

Input: 
    5
   / \
  3   6
 / \   \
2   4   7
Target = 28
Output: False

Analysis

Hash Set

Using any traversal is fine.

Note: Duplicates are allowed.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public boolean findTarget(TreeNode root, int k) {
  Set<Integer> set = new HashSet<>();
  return findTargetHelper(root, k, set);
}

private boolean findTargetHelper(TreeNode root, int k, Set<Integer> set) {
  if (root == null) {
    return false;
  }
  if (set.contains(k - root.val)) {
    return true;
  }
  set.add(root.val);
  // traversal
  return findTargetHelper(root.left, k, set) || findTargetHelper(root.right, k, set);
}

Time: $O(N)$
Space: $O(N)$

Inorder + Two Pointers

Basically, we convert the BST tree to a sorted list and then apply the two-pointer method.

Time: $O(N)$
Space: $O(N)$