# Two Sum IV

• Approach #2 : Space complexity should be O(n). The size of the set+queue can grow upto n in the worst case.

• You didn't use the info Binary Search Tree at all.

• @zestypanda I've updated the article. Thanks for the valuable feedback.

• @aayushgarg You're right. Thanks for pointing out.

• @vinod23 whats your take on converting the BST to doubly linked list and then find the two sum.

• This post is deleted!

• @kool This cannot be done in O(n) time and O(logN) space. What if height of my BST is N?

• Can be good, if the desired optimization (time vs space) was put on challenge description, because a in-place search on this tree can be made at time O(N * log(N)) and space O(1).

• @vinod32 My first solution has better bounds than the listed ones. https://leetcode.com/submissions/detail/125833106/ It's similar to approach #3, but only uses O(Depth) space which is log2(N) when the tree is balanced. You do not need to put all tree elements in the list. Just traverse the tree itself.

• ``````  def __findTargetDetail(self, root, k, seen):
if root is None:
return False

complement = k - root.val
if complement in seen:
return True
else:

return self.__findTargetDetail(root.left, k, seen) or self.__findTargetDetail(root.right, k, seen)

# O(n) time, O(n) space
def findTarget(self, root, k):
seen = set()
return self.__findTargetDetail(root, k, seen)
``````

• ``````  def __binarySearch(self, root, k):
if root is None:
return

if root.val == k:
return root
elif root.val > k:
return self.__binarySearch(root.left, k)
else:
return self.__binarySearch(root.right, k)

def __findTargetBST(self, node, root, k):
if node is None:
return False

complement = k - node.val
comp_node = self.__binarySearch(root, complement)
if comp_node is not None and node is not comp_node:
return True

return self.__findTargetBST(node.left, root, k) or self.__findTargetBST(node.right, root, k)

# O(nlogn) time, O(h) space
def findTarget(self, root, k):
return self.__findTargetBST(root, root, k)
``````

• ``````  # O(n) time, O(n) space, use BFS
def findTarget(self, root, k):
if root is None:
return False

s = set()
q = Queue.Queue()
q.put(root)
while not q.empty():
node = q.get()
complement = k - node.val
if complement in s:
return True
else:
if node.left:
q.put(node.left)
if node.right:
q.put(node.right)
return False
``````

• /**

• Definition for a binary tree node.

• struct TreeNode {

• ``````int val;
``````
• ``````TreeNode *left;
``````
• ``````TreeNode *right;
``````
• ``````TreeNode(int x) : val(x), left(NULL), right(NULL) {}
``````
• };
/
class Solution {
public:
bool findTarget(TreeNode
root, int k) {
if (root == NULL) {
return false;
}
vector<int> v;
inorder(root, v);

`````` int low = 0;
int high = v.size() - 1;
while (low < high) {
if (v[low] + v[high] == k) {
return true;
} else if (v[low] + v[high] < k) {
low++;
} else {
high--;
}
}

return false;
``````

}

private:
void inorder(TreeNode* root, vector<int>& v) {
if (root != NULL) {
inorder(root->left, v);
v.push_back(root->val);
inorder(root->right, v);
}
}
};

• @RF Could you tell me how you reply the code in a readable format?

• ``````public boolean findTarget(TreeNode root, int k) {

java.util.Map<Integer, Object> m = new java.util.HashMap<>();
flat(root, m);

for (java.util.Map.Entry<Integer, Object> e : m.entrySet()) {
int complement = k - e.getKey();
if (complement != e.getKey()  // avoid like 6 - 3 = 3 issue;
&& m.containsKey(complement)) {
return  true;
}
}

return false;

}

/**
* recursively get values from the tree and put into map.
*/
public void flat(TreeNode node, java.util.Map<Integer,Object> m) {
m.put(node.val, null);
if(node.left != null) flat(node.left, m);
if(node.right != null) flat(node.right, m);
}
``````

}

• You can also achieve O(h) space if you use a BST Iterator for the min and max node of the tree. Runtime will still be O(n)

• If allowed to modify the tree, convert the BST to a sorted DoublyLinkedList and then find the pair like you would in a in-order List. The would not use any additional space except for the call stack which will be `O(log n)`.

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