Find a pair with given sum in a Balanced BST | Java code to find a pair with given sum in a Balanced BST ; A binary tree node ; Root of BST ; Constructor ; Inorder traversal of the tree ; Utility function for inorder traversal of the tree ; This method mainly calls insertRec ( ) ; A recursive function to insert a new key in BST ; If the tree is empty , return a new node ; Otherwise , recur down the tree ; Method that adds values of given BST into ArrayList and hence returns the ArrayList ; Base Case ; method that checks if there is a pair present ; This list a1 is passed as an argument in treeToList method which is later on filled by the values of BST ; a2 list contains all the values of BST returned by treeToList method ; Starting index of a2 ; Ending index of a2 ; Target Found ! ; decrements end ; increments start ; Driver function ; 15 / \ 10 20 / \ / \ 8 12 16 25
import java . util . ArrayList ; class Node { int data ; Node left , right ; Node ( int d ) { data = d ; left = right = null ; } } class BinarySearchTree { Node root ; BinarySearchTree ( ) { root = null ; } void inorder ( ) { inorderUtil ( this . root ) ; } void inorderUtil ( Node node ) { if ( node == null ) return ; inorderUtil ( node . left ) ; System . out . print ( node . data + " ▁ " ) ; inorderUtil ( node . right ) ; } void insert ( int key ) { root = insertRec ( root , key ) ; } Node insertRec ( Node root , int data ) { if ( root == null ) { root = new Node ( data ) ; return root ; } if ( data < root . data ) root . left = insertRec ( root . left , data ) ; else if ( data > root . data ) root . right = insertRec ( root . right , data ) ; return root ; } ArrayList < Integer > treeToList ( Node node , ArrayList < Integer > list ) { if ( node == null ) return list ; treeToList ( node . left , list ) ; list . add ( node . data ) ; treeToList ( node . right , list ) ; return list ; } boolean isPairPresent ( Node node , int target ) { ArrayList < Integer > a1 = new ArrayList < > ( ) ; ArrayList < Integer > a2 = treeToList ( node , a1 ) ; int start = 0 ; int end = a2 . size ( ) - 1 ; while ( start < end ) { if ( a2 . get ( start ) + a2 . get ( end ) == target ) { System . out . println ( " Pair ▁ Found : ▁ " + a2 . get ( start ) + " ▁ + ▁ " + a2 . get ( end ) + " ▁ " + " = ▁ " + target ) ; return true ; } if ( a2 . get ( start ) + a2 . get ( end ) > target ) { end -- ; } if ( a2 . get ( start ) + a2 . get ( end ) < target ) { start ++ ; } } System . out . println ( " No ▁ such ▁ values ▁ are ▁ found ! " ) ; return false ; } public static void main ( String [ ] args ) { BinarySearchTree tree = new BinarySearchTree ( ) ; tree . insert ( 15 ) ; tree . insert ( 10 ) ; tree . insert ( 20 ) ; tree . insert ( 8 ) ; tree . insert ( 12 ) ; tree . insert ( 16 ) ; tree . insert ( 25 ) ; tree . isPairPresent ( tree . root , 33 ) ; } }