Remove all nodes which don 't lie in any path with sum>= k | Java program to implement the above approach ; A utility function to get maximum of two integers ; A Binary Tree Node ; A utility function to create a new Binary Tree node with given data ; print the tree in LVR ( Inorder traversal ) way . ; Main function which truncates the binary tree . ; Base Case ; Initialize left and right sums as sum from root to this node ( including this node ) ; Recursively prune left and right subtrees ; Get the maximum of left and right sums ; If maximum is smaller than k , then this node must be deleted ; A wrapper over pruneUtil ( ) ; Driver Code ; k is 45
import java . util . * ; class GFG { static int max ( int l , int r ) { return ( l > r ? l : r ) ; } static class Node { int data ; Node left , right ; } ; static class INT { int v ; INT ( int a ) { v = a ; } } static Node newNode ( int data ) { Node node = new Node ( ) ; node . data = data ; node . left = node . right = null ; return node ; } static void print ( Node root ) { if ( root != null ) { print ( root . left ) ; System . out . print ( root . data + " ▁ " ) ; print ( root . right ) ; } } static Node pruneUtil ( Node root , int k , INT sum ) { if ( root == null ) return null ; INT lsum = new INT ( sum . v + ( root . data ) ) ; INT rsum = new INT ( lsum . v ) ; root . left = pruneUtil ( root . left , k , lsum ) ; root . right = pruneUtil ( root . right , k , rsum ) ; sum . v = max ( lsum . v , rsum . v ) ; if ( sum . v < k ) { root = null ; } return root ; } static Node prune ( Node root , int k ) { INT sum = new INT ( 0 ) ; return pruneUtil ( root , k , sum ) ; } public static void main ( String args [ ] ) { int k = 45 ; Node root = newNode ( 1 ) ; root . left = newNode ( 2 ) ; root . right = newNode ( 3 ) ; root . left . left = newNode ( 4 ) ; root . left . right = newNode ( 5 ) ; root . right . left = newNode ( 6 ) ; root . right . right = newNode ( 7 ) ; root . left . left . left = newNode ( 8 ) ; root . left . left . right = newNode ( 9 ) ; root . left . right . left = newNode ( 12 ) ; root . right . right . left = newNode ( 10 ) ; root . right . right . left . right = newNode ( 11 ) ; root . left . left . right . left = newNode ( 13 ) ; root . left . left . right . right = newNode ( 14 ) ; root . left . left . right . right . left = newNode ( 15 ) ; System . out . println ( "Tree before truncationNEW_LINE");  print ( root ) ; root = prune ( root , k ) ; System . out . println ( " Tree after truncation ");  print ( root ) ; } }