Click here to see the full article post
Approach #2 : Space complexity should be O(n). The size of the set+queue can grow upto n in the worst case.
@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.
@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.
@Ark-kun 404 Page Not Found. What happened?
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
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.