Pair Sum in BST.

The idea is that if the sum of any two elements say, ‘A’ and ‘B’ is equal to the given value ‘K’, and we already know that ‘A’ is present in the given tree then we only need to check whether element ‘B’ = ‘K’ - ‘A’  exists in the tree or not. We can check this by using the property of the binary search tree.

Approach :

• Using depth-first search (DFS), we traverse the given BST.
• For each node, we calculate the value ‘Q’  i.e ‘K’ - current node’s value.
• Now, using the property of BST, we search this value in the given tree.
  • If the value of the current node is less than ‘Q’, we will search in the right subtree recursively.
  • If the value of the current node is more than ‘Q’, we will search in the left subtree recursively.
  • If the value of the current node equals ‘Q’, we will return “true” to the function.
  • If the value is not found for any node, we will return “false” to the function.

In this approach, we use the property of the inorder traversal of BST. The inorder traversal of a BST always traverses the nodes of BST in the increasing order of their values.

Thus, we do the inorder traversal of the given tree and we store all the values of the nodes in an array. This will give us an array in increasing order. Now we can use the two-pointer technique on this sorted list for determining if two elements exist in the list which sums up to the target value ‘K’.

Approach :

• First create an array say, ‘NUMS’.
• Create a recursive function, say ‘inorder ( ROOT, NUMS)’ passing ‘ROOT’ and ‘NUMS’ in its arguments.
• Now call the recursive function ‘inorder ( ROOT, NUMS)’, to store the inorder traversal of a given tree in the array, ‘NUMS’
• Use the two-pointer technique in the array, ‘NUMS’.
• Set iterator pointer ‘i’  at the start, and iterator pointer ‘j’  at the end of the array ‘NUMS’
• If the sum of the values at index ‘i’ and  index ‘j’ is greater than the target ‘K’, decrement ‘j’ by 1.
• If the sum of the values at index ‘i’ and index ‘j’ is less than the target ‘K’, increment ‘i’ by 1.
• If the sum of the values at index ‘i’ and index ‘j’ is equal to the target ‘K’, then  return “true” to the function.
• At last, we return “false” to the function, if we didn't find any two elements with sum = ‘K’.

Description of ‘inorder’ function

This function will take two parameters :

• ‘ROOT’ that is the root of the given BST.
• ‘NUMS’ array which we have defined above.

void inorder(ROOT, NUMS):

• Until all the nodes are traversed
• Recursively traverse the left subtree.
• Add the current node’s value to the ‘NUMS’.
• Recursively traverse the right subtree.

Instead of searching a second value for every node of the given BST, we can optimise our search by using a set to keep track of elements. 

• We will traverse the tree in a depth-first-search manner.
• For every node, we check if there is a value present in the set which is equal to the difference of given target ‘K’ and the node’s value.
• If so, we can say that there are two nodes whose values of the sum are equal to target ‘K’. So, we return “true” to the function.
• Else, we will insert the value in the set.

Approach :

• Create an empty unordered set, say ‘HASHSET’.
• We create a recursive function that traverses each node in the given tree to check the pair sum:
  • If ‘ROOT’ is NULL then return “false”.
  • If the ‘HASHSET’ contains the ‘K’ - ROOT’s DATA then return “true”.
  • Else add ROOT’s DATA into ‘HASHSET’.
  • If any of the subtrees either left or right return “true” then return “true” to the function.
  • Else return “false” to the function.

In this approach, we will maintain a ‘FRONT’ and a ‘BACK’ iterator pointers that will iterate the BST in the order of in-order and reverse in-order traversal respectively. 

Approach : 
 

• We maintain two stacks, one for storing the leftmost value of the BST, say ‘START’, and another for storing the rightmost value of BST, say ‘END’.
• Now, using the two-pointer technique, we check if the sum of values at the top of stack ‘START’ and ‘END’ is equal to the given target ‘K’.
  • If they are equal to the target ‘K’, then return “true” to the function.
  • If the sum is less than the target ‘K’, we make the ‘FRONT’ iterator point to the next element using the first stack ‘START’.
  • Else if the sum is greater than the target ‘K’, we make the ‘BACK’ iterator point to the previous element using the second stack ‘END’.
  • At last, if we find no such two elements having sum equal to target ‘K’, then we will return “false” to the function.