Find if there is a pair in root to a leaf path with sum equals to root 's data | Java program to find if there is a pair in any root to leaf path with sum equals to root 's key. ; A binary tree node has data , pointer to left child and a pointer to right child ; utility that allocates a new node with the given data and null left and right pointers . ; Function to print root to leaf path which satisfies the condition ; Base condition ; Check if current node makes a pair with any of the existing elements in set . ; Insert current node in set ; If result returned by either left or right child is true , return true . ; Remove current node from hash table ; A wrapper over printPathUtil ( ) ; create an empty hash table ; Recursively check in left and right subtrees . ; Driver code
import java . util . * ; class GFG { static class Node { int data ; Node left , right ; } ; static Node newnode ( int data ) { Node node = new Node ( ) ; node . data = data ; node . left = node . right = null ; return ( node ) ; } static boolean printPathUtil ( Node node , HashSet < Integer > s , int root_data ) { if ( node == null ) return false ; int rem = root_data - node . data ; if ( s . contains ( rem ) ) return true ; s . add ( node . data ) ; boolean res = printPathUtil ( node . left , s , root_data ) || printPathUtil ( node . right , s , root_data ) ; s . remove ( node . data ) ; return res ; } static boolean isPathSum ( Node root ) { HashSet < Integer > s = new HashSet < Integer > ( ) ; return printPathUtil ( root . left , s , root . data ) || printPathUtil ( root . right , s , root . data ) ; } public static void main ( String [ ] args ) { Node root = newnode ( 8 ) ; root . left = newnode ( 5 ) ; root . right = newnode ( 4 ) ; root . left . left = newnode ( 9 ) ; root . left . right = newnode ( 7 ) ; root . left . right . left = newnode ( 1 ) ; root . left . right . right = newnode ( 12 ) ; root . left . right . right . right = newnode ( 2 ) ; root . right . right = newnode ( 11 ) ; root . right . right . left = newnode ( 3 ) ; System . out . print ( isPathSum ( root ) == true ? " Yes " : " No " ) ; } }