Find a pair with given sum in a Balanced BST

Problem:
Find a pair with given sum in a Balanced BST
Given a Balanced Binary Search Tree and a target sum, write a function that returns true if there is a pair with sum equals to target sum, otherwise return false. Expected time complexity is O(n) and only O(Logn) extra space can be used. Any modification to Binary Search
Tree is not allowed. Note that height of a Balanced BST is always O(Logn).

Solution:
– In Question its mentioned that we can’t alter BST otherwise we can easily sove this by {@link BalancedBSTZeroSumFinder}
– But here we use two traversal one InOrder traversal and another reverse InOrder traversal
– Both traversals are non-recursive by using stack

Latest Source Code:
Github: BinarySearchTreeSumPairFinder.java


Output:

    15       
  / \   
 /   \  
 10   20   
/ \ / \ 
8 12 16 25 
                
Pair exists for 30 ? true
Pair exists for 32 ? true
Pair exists for 23 ? true
Pair exists for 41 ? true
Pair exists for 100 ? false

Author: Hrishikesh Mishra