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