Teaching Kids Programming – Two Sum in Binary Search Tree via Inorder and Two Pointer Algorithm

Teaching Kids Programming: Videos on Data Structures and Algorithms

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

Two Sum Algorithm in Binary Search Tree via Inorder and Two Pointer Algorithm

We can perform a inorder (LNR) on a binary search tree (BST) to get a sorted list. This requires O(N) time and space. Then we can perform a Two Pointer Algorithm (O(N) time) to find out if there are two numbers that sum up to target. The overall time is O(N) and the space complexity is O(N).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

# 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: Optional[TreeNode], k: int) -> bool:
        data = []
        def dfs(root):
            if not root:
                return
            dfs(root.left)
            data.append(root.val)
            dfs(root.right)
        dfs(root)
        i, j = 0, len(data) - 1
        while i < j:
            t = data[i] + data[j]
            if t == k:
                return True
            if t > k:
                j -= 1
            else:
                i += 1
        return False            

# 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: Optional[TreeNode], k: int) -> bool:
        data = []
        def dfs(root):
            if not root:
                return
            dfs(root.left)
            data.append(root.val)
            dfs(root.right)
        dfs(root)
        i, j = 0, len(data) - 1
        while i < j:
            t = data[i] + data[j]
            if t == k:
                return True
            if t > k:
                j -= 1
            else:
                i += 1
        return False            

Two Sum Variation Problems

• Teaching Kids Programming - Two Sum in Binary Search Tree via Inorder and Two Pointer Algorithm
• Teaching Kids Programming - Count Pairs Whose Sum is Less than Target (Two Pointer Algorithm)
• Teaching Kids Programming - Sum of Two Numbers Less Than Target using Two Pointer Algorithm
• Teaching Kids Programming - Two Pointer Algorithm to Solve Four Sum Problem
• Teaching Kids Programming - Recursive Algorithm to Find the Sum of Two Numbers in BSTs
• Two Pointer Algorithm to Count the Sum of Three Numbers Less than Target
• Recursive and Two Pointer Algorithms to Determine Four Sum
• Algorithms to Check Sum of Two Numbers in Binary Search Trees
• Teaching Kids Programming - 3 Different Approaches to Solve Two-Sum Problem
• How to Design a Two-Sum Data Structure?
• How to Find the Closest Sum of Three in an Array using Two Pointer Algorithm? (3Sum Closest)
• Teaching Kids Programming - Three Sum Algorithm
• Teaching Kids Programming – Two Sum Algorithm when Input Array is Sorted
• Teaching Kids Programming – Two Sum Algorithm
• Two Pointer Algorithm to Find Maximum Two Sum Less Than K
• The Two Sum Algorithm using HashMap in C++/Java

–EOF (The Ultimate Computing & Technology Blog) —