Teaching Kids Programming – Recursive Algorithm to Find the Sum of Two Numbers in BSTs

Teaching Kids Programming: Videos on Data Structures and Algorithms

You are given two binary search trees a and b and an integer target. Return whether there’s a number in a and a number in b such that their sum equals to target.

Sum of Two Numbers in BSTs

We can do this recursively. If one of the Binary Search Tree is None, the result is false (we have no two values to pick). Otherwise, we compare the sum of current nodes at two Binary Search Tree and the target. If the sum is less than the target, then either one of the BST need to go to the right sub tree. On the other hand, we need to go to one of the subtrees.

1
2
3
4
5
6
7
8
9
10
11
12
13
14

# class Tree:
#     def __init__(self, val, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def solve(self, a, b, target):
        if a is None or b is None:
            return False
        if a.val + b.val == target:
            return True
        if target < a.val + b.val:
            return self.solve(a.left, b, target) or self.solve(a, b.left, target)
        return self.solve(a.right, b, target) or self.solve(a, b.right, target)

# class Tree:
#     def __init__(self, val, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def solve(self, a, b, target):
        if a is None or b is None:
            return False
        if a.val + b.val == target:
            return True
        if target < a.val + b.val:
            return self.solve(a.left, b, target) or self.solve(a, b.left, target)
        return self.solve(a.right, b, target) or self.solve(a, b.right, target)

The time complexity is O(N*M) where N and M are the number of nodes in two Binary Search Tree respectively. Consider two BSTs degenerate to singly lists like the following:

0
 \
  1
   \
    2
     \
      3

If the target is 10000. Then we have to basically iterate all pairs which is O(N^2).

The space complexity is also O(N+M) because the height of a Binary Search Tree could be O(N) in the worst case.

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) —