653_Two Sum IV - Input is a BST

Given a Binary Search Tree and a target number, return true if there exist two elements in the BST such that their sum is equal to the given target.

Example 1:

Input:

    5
   / \
  3   6
 / \   \
2   4   7

Target = 9


Output:
 True

Example 2:

Input:

    5
   / \
  3   6
 / \   \
2   4   7

Target = 28


Output:
 False

Solution

Inorder traverse the BST, the result will be a sorted array. Then use the same strategy as in two sum - sorted array (using two pointers).

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def findTarget(self, root, k):
        """
        :type root: TreeNode
        :type k: int
        :rtype: bool
        """
        def traverse(root, ret):
            if root == None:
                return ret
            traverse(root.left, ret)
            ret.append(root.val)
            traverse(root.right, ret)

        ret = []
        traverse(root, ret)
        left = 0
        right = len(ret) - 1
        while left < right:
            if ret[left] + ret[right] == k:
                return True
            elif ret[left] + ret[right] < k:
                left += 1
            else:
                right -= 1
        return False