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)$


Comment