LeetCode 653. Two Sum IV – Input is a BST

Description

https://leetcode.com/problems/two-sum-iv-input-is-a-bst/

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

Example 1:

Input: root = [5,3,6,2,4,null,7], k = 9
Output: true

Example 2:

Input: root = [5,3,6,2,4,null,7], k = 28
Output: false

Example 3:

Input: root = [2,1,3], k = 4
Output: true

Example 4:

Input: root = [2,1,3], k = 1
Output: false

Example 5:

Input: root = [2,1,3], k = 3
Output: true

Constraints:

  • The number of nodes in the tree is in the range [1, 104].
  • -104 <= Node.val <= 104
  • root is guaranteed to be a valid binary search tree.
  • -105 <= k <= 105

Explanation

Inorder traverse the binaray search tree to build a list of node values in ascending order. Then use two pointers technique to find whether there are two elements adding up together equal to k.

Python Solution

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def findTarget(self, root: TreeNode, k: int) -> bool:   
        
        values = []
        self.inorder_traverse(root, values)

        left = 0
        right = len(values) - 1
        
        while left < right:
            if values[left] + values[right] < k:
                left += 1
            elif values[left] + values[right] > k:
                right -= 1
            else:
                return True
                    
        return False

        
    def inorder_traverse(self, root, results):
        if not root:
            return
        
        self.inorder_traverse(root.left, results)
        results.append(root.val)
        self.inorder_traverse(root.right, results)
            
        
        
  • Time Complexity: O(N).
  • Space Complexity: O(N).

Leave a Reply

Your email address will not be published.