# Concise Java Solution O(n) time, O(h) space, using two stacks.

• If the given data structure is a sorted array, we could easily come up with the two-pointer solution. When it comes to a BST, similar idea could be used to solve the problem. In this case, we can use a stack to find next smaller value and another stack to find next large value(similar to BST iterator, but we only implement next()). Let the code explains:

``````public class Solution {
public boolean findTarget(TreeNode root, int k) {
Stack<TreeNode> small = new Stack<>();
Stack<TreeNode> large = new Stack<>();

initialStack(small, true, root);
initialStack(large, false, root);

TreeNode nextSmall = getNext(large, false);
TreeNode nextLarge = getNext(small, true);

while (nextSmall != null && nextLarge != null && nextSmall != nextLarge) {
int sum = nextSmall.val + nextLarge.val;

if (sum == k) {
return (true);
} else if (sum < k) {
nextLarge = getNext(small, true);
} else {
nextSmall = getNext(large, false);
}
}

return (false);
}

void initialStack(Stack<TreeNode> stack, boolean small, TreeNode root) {
while (root != null) {
stack.push(root);
root = small ? root.left : root.right;
}
}

TreeNode getNext(Stack<TreeNode> stack, boolean small) {
if (stack.isEmpty()) {
return (null);
}

TreeNode res = stack.pop();
TreeNode node = small ? res.right : res.left;

while (node != null) {
stack.push(node);
node = small ? node.left : node.right;
}

return (res);
}
}
``````

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