# 653. Two Sum IV - Input is a BST
#### Difficulty: Easy
link: https://leetcode.com/problems/two-sum-iv-input-is-a-bst/

### 1. Sorted Array + Two Pointer
#### $O(n)$ runtime, $O(n)$ space

最直觀想到的作法，先 inorder 跑一遍 BST，將元素依小至大的順序存進一個 list，那這個問題就被化簡為 [Two Sum II - Input array is sorted](https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/)，再搭配 two pointer 的作法，時間和空間複雜度都會是$O(n)$。

##### python

class Solution:
    def findTarget(self, root: TreeNode, k: int) -> bool:
        self.sorted_array = []
        self.inorder(root)
        
        i, j = 0, len(self.sorted_array)-1
        while i < j:
            two_sum = self.sorted_array[i] + self.sorted_array[j]
            if two_sum == k:
                return True
            elif two_sum > k:
                j -= 1
            else:
                i += 1
        
        return False
        
    def inorder(self, node):
        if node is None:
            return
        self.inorder(node.left)
        self.sorted_array.append(node.val)
        self.inorder(node.right)

<font color="#00AB5F ">Accepted</font>
Runtime: **92 ms**, faster than **34.56%** of Python3 online submissions for Two Sum IV - Input is a BST.
Memory Usage: **19.3 MB**, less than **28.76%** of Python3 online submissions for Two Sum IV - Input is a BST.

### 2. Hash Table
#### $O(n)$ runtime, $O(n)$ or $O(log\ n)$ space

在前一題 [Two Sum II - Input array is sorted](https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/) 的 two pointer 作法優點是 $O(1)$ 的空間複雜度，然而這題化簡用的 list 卻需要 $O(n)$ 的空間複雜度，那其實也能用 [Two Sum](https://leetcode.com/problems/two-sum) 的 hash table 作法，一旦找到答案就 return，會比前一個作法全部都找一遍還快些。

這裡用 BFS 來 traverse BST。另外，如果題目有保證 BST 是 balanced，那麼 DFS 的做法可以到 $O(log\ n)$ 空間複雜度，因為 stack 裡面最多存放 BST height 個 node。

##### python

class Solution:
    def findTarget(self, root: TreeNode, k: int) -> bool:
        queue, hashtable = [root], set()
        while queue:
            node = queue.pop()
            if k - node.val in hashtable: 
                return True
            hashtable.add(node.val)
            if node.left: 
                queue.append(node.left)
            if node.right: 
                queue.append(node.right)
                
        return False

<font color="#00AB5F ">Accepted</font>
Runtime: **80 ms**, faster than **67.18%** of Python3 online submissions for Two Sum IV - Input is a BST.
Memory Usage: **16.6 MB**, less than **71.99%** of Python3 online submissions for Two Sum IV - Input is a BST.

###### tags: `leetcode`