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