Question

Recall the 2-sum problem which took an array of N integers and determined the number of pairs that summed to 0. Now consider a 2-sum BST problem. Let B be a binary search tree with N integers as unique keys. Using only data structures and algorithms that have been discussed in this class, describe an algorithm that will return the number of pairs in B that add to 0. Analyze the space and runtime of your algorithm.

Answer 1

We are given a BST(binary search tree) and we have to find the number of pairs in this BST with zero sum. Following is a approach to solve this:

Step 1: Create a hash table to store the minus of the node's value. This table is used to lookup for pairs with zero sum.

Step 2: Traverse the BST in any order(pre/post/in). Check if the node's value is present in the hash table. If yes, increment the count by 1.

Step 3: If the node's value is present in the hash, do not add it's value to the hash table to avoid the duplicate counting.

The time complexity of this approach is O(n) because we visit every node once.

The space complexity is also O(n) because we are creating a hash table. In the worst case, number elements in hash table would be equal to the number of nodes in the tree.

Following is the python code for this approach:

# Python program to count the number of pairs
# in a binary tree whose sum is
# equal to zero

count = 0 #gloal variable count

# Node class for creating a node in the binary tree
# with value, left and right attributes
class Node(object):
def __init__(self, value, left = None, right = None):
self.value = value
self.left = left
self.right = right
  

  
# This hash table stores the minus of the
# node's value
# used to lookup for pairs with zero sum
hash_table = set()
  

  
# this function is to count number of pairs with zero sum
# Does a pre-order traversal of the tree.However, the tree
# can be traversed in any order
def count_pairs(root):
global count
if root:
if root.value in hash_table:
count = count + 1
else:
hash_table.add(-root.value)
  
count_pairs(root.left)
count_pairs(root.right)
  
# This is the Main function and entry point of program
# acts as Driver function
# Creates a binary search tree and call the function
# to get the count and finally prints the count value
if __name__ == '__main__':
root = Node(5)
  
root.left = Node(3)
root.right = Node(7)
  
root.left.left = Node(-3)
root.left.right = Node(4)
  
root.right.left = Node(6)
root.right.right = Node(8)
  
count_pairs(root)
  
print(count)

The BST in the above program has 7 nodes with values -3, 3, 4, 5, 6, 7, 8.

So, it has only one pair (-3, 3) with zero sum.