Problem:
Find if there is a triplet in a Balanced BST that adds to zero
Given a Balanced Binary Search Tree (BST), write a function isTripletPresent() that returns true if there is a triplet in given BST with sum equals to 0, otherwise returns false. Expected time complexity is O(n^2) and only O(Logn) extra space can be used. You can modify given Binary Search Tree. Note that height of a Balanced BST is always O(Logn)

Solution:
– Here it mentioned that we can modify the BST so, we create DLL from it {@link BinarySearchTreeToDoublyLinkedList}
– After that, we traverse DLL and check sum only for negative number
– For each negative number, we traverse DLL from head and tail in this way
– – First sum head and tail node data if they equal to provided node return true
– – If its less than provided node then move head pointer to next node
– – If its greater than, then move tail pointer to previous node
– – Repeat this process till head != tail

Latest Source Code:
Github: BalancedBSTZeroSumFinder.java

Output:

       6               
      / \       
     /   \      
    /     \     
   /       \    
   -13       14       
    \     / \   
     \   /   \  
     -8 13   15   
        /       
       7       
                                
Is Triplet Present? : true