# Java O(1) space O(log n) time 21ms solution runtime beats 100%

• Based on BST search

class Solution {
public boolean findTarget(TreeNode root, int k) {
TreeNode aNode = root, bNode = root;
while (aNode.left != null) aNode = aNode.left;
while (bNode.right != null) bNode = bNode.right;
while (aNode != null && bNode != null && aNode != bNode) {
int a = aNode.val, b = bNode.val;
int sum = a + b;
if (sum == k)
return true;
else if (sum < k) {
// find smallest bigger than k-b
int complement = k - b;
if (complement >= b)
return false;
aNode = null;
TreeNode x = root;
while (x != null) {
if (x.val == complement)
return true;
else if (x.val < complement)
x = x.right;
else if (x.val > complement) {
aNode = x;
x = x.left;
}
}
} else {
// find biggest smaller than k-a
int complement = k - a;
if (complement <= a)
return false;
bNode = null;
TreeNode x = root;
while (x != null) {
if (x.val == complement)
return true;
else if (x.val > complement)
x = x.left;
else {
bNode = x;
x = x.right;
}
}
}
}
return false;
}
}

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.