Two Sum IV




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

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

@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: seen.add(root.val) 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: s.add(node.val) if node.left: q.put(node.left) if node.right: q.put(node.right) return False