Leetcode 653 - Two Sum IV - Input is a BST

Note:

  • Use inorder to get a sorted array then use double pointers.

Question:

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

Example:

img

1
2
Input: root = [5,3,6,2,4,null,7], k = 9
Output: true

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @param {number} k
* @return {boolean}
*/
var findTarget = function (root, k) {
let traversal = [];
dfs(root);
let left = 0, right = traversal.length - 1;
while (left < right) {
const sum = traversal[left] + traversal[right];
if (sum === k) return true;
if (sum > k) {
right--;
} else {
left++;
}
}
return false;

function dfs(node) {
if (!node) return;
dfs(node.left);
traversal.push(node.val);
dfs(node.right);
}
};