# Java Simple AC with Time O(n) Space O(log n) in Average

• There are few possible solutions:

#### (1) Use hash set to keep those visited value for fast lookup.

-- It can be applied to any kinds of tree. Time/Space: n/n

#### (2) Dump values to array list in-order and search by the way just like in 2sum.

-- Time/Space: n/n

#### (3) Use the stack and search just like 2sum without dumping all the value out in the beginning.

-- Time/Space: n/logn in average

If I have to choose one from them, I would prefer the third one because it takes advantage of the property of BST and is with lower space complexity in average. Its code is shown below.

``````    public boolean findTarget(TreeNode root, int k) {
if(root == null) return false;
Stack<TreeNode> l_stack = new Stack<>();
Stack<TreeNode> r_stack = new Stack<>();
while(l_stack.peek() != r_stack.peek()){
int n = l_stack.peek().val + r_stack.peek().val;
if(n == k){
return true;
}else if(n > k){
stackNext(r_stack, false);
}else{
stackNext(l_stack, true);
}
}
return false;
}

private void stackAdd(Stack<TreeNode> stack, TreeNode node, boolean isLeft){
while(node != null){
stack.push(node);
node = (isLeft) ? node.left : node.right;
}
}

private void stackNext(Stack<TreeNode> stack, boolean isLeft){
TreeNode node = stack.pop();
if(isLeft){
}else{
}
}
``````

• Very concise solution!

• Brilliant solution, here is the python version

``````  def __add_left_nodes (self, stack, node):
while node:
stack.append(node)
node = node.left

while node:
stack.append(node)
node = node.right

# O(n) time, O(logn) space
def findTarget(self, root, k):
if root is None:
return False

l, r = [], []

# the root is pusted to the bottom of the stack
while l[-1] is not r[-1]:
n = l[-1].val + r[-1].val
if n == k:
return True
elif n > k:
node = r.pop()
# Add children smaller than node but larger than node.left
if node.left: