Three numbers in a BST that adds upto zero | A BST node has key , and left and right pointers ; A function to convert given BST to Doubly Linked List . left pointer is used as previous pointer and right pointer is used as next pointer . The function sets * head to povar to first and * tail to povar to last node of converted DLL ; Base case ; First convert the left subtree ; Then change left of current root as last node of left subtree ; If tail is not null , then set right of tail as root , else current node is head ; Update tail ; Finally , convert right subtree ; This function returns true if there is pair in DLL with sum equal to given sum . The algorithm is similar to hasArrayTwoCandidates ( ) tinyurl . com / dy6palr in method 1 of http : ; The main function that returns true if there is a 0 sum triplet in BST otherwise returns false ; Check if the given BST is empty ; Convert given BST to doubly linked list . head and tail store the pointers to first and last nodes in DLLL ; Now iterate through every node and find if there is a pair with sum equal to - 1 * heaf . key where head is current node ; If there is a pair with sum equal to - 1 * head . key , then return true else move forward ; If we reach here , then there was no 0 sum triplet ; A utility function to create a new BST node with key as given num ; A utility function to insert a given key to BST ; Driver code
class node { constructor ( val ) { this . key = val ; this . left = null ; this . right = null ; } } var head ; var tail ; function convertBSTtoDLL ( root ) { if ( root == null ) return ; if ( root . left != null ) convertBSTtoDLL ( root . left ) ; root . left = tail ; if ( tail != null ) ( tail ) . right = root ; else head = root ; tail = root ; if ( root . right != null ) convertBSTtoDLL ( root . right ) ; } function isPresentInDLL ( head , tail , sum ) { while ( head != tail ) { var curr = head . key + tail . key ; if ( curr == sum ) return true ; else if ( curr > sum ) tail = tail . left ; else head = head . right ; } return false ; } function isTripletPresent ( root ) { if ( root == null ) return false ; head = null ; tail = null ; convertBSTtoDLL ( root ) ; while ( ( head . right != tail ) && ( head . key < 0 ) ) { if ( isPresentInDLL ( head . right , tail , - 1 * head . key ) ) return true ; else head = head . right ; } return false ; } function newNode ( num ) { var temp = new node ( ) ; temp . key = num ; temp . left = temp . right = null ; return temp ; } function insert ( root , key ) { if ( root == null ) return newNode ( key ) ; if ( root . key > key ) root . left = insert ( root . left , key ) ; else root . right = insert ( root . right , key ) ; return root ; } var root = null ; root = insert ( root , 6 ) ; root = insert ( root , - 13 ) ; root = insert ( root , 14 ) ; root = insert ( root , - 8 ) ; root = insert ( root , 15 ) ; root = insert ( root , 13 ) ; root = insert ( root , 7 ) ; if ( isTripletPresent ( root ) ) document . write ( " " ) ; else document . write ( " " ) ;