Remove all nodes which don 't lie in any path with sum>= k | Class representing binary tree node ; for print traversal ; class to truncate binary tree recursive method to truncate binary tree ; base case ; recur for left and right subtree ; if node is a leaf node whose data is smaller than the sum we delete the leaf . An important thing to note is a non - leaf node can become leaf when its children are deleted . ; utility method to check if node is leaf ; Driver class to test above function
class Node { int data ; Node left ; Node right ; public Node ( int data ) { this . data = data ; left = null ; right = null ; } } public void print ( Node root ) { if ( root == null ) return ; print ( root . left ) ; System . out . print ( root . data + " ▁ " ) ; print ( root . right ) ; } } class BinaryTree { Node root ; public Node prune ( Node root , int sum ) { if ( root == null ) return null ; root . left = prune ( root . left , sum - root . data ) ; root . right = prune ( root . right , sum - root . data ) ; if ( isLeaf ( root ) ) { if ( sum > root . data ) root = null ; } return root ; } public boolean isLeaf ( Node root ) { if ( root == null ) return false ; if ( root . left == null && root . right == null ) return true ; return false ; } public class GFG { public static void main ( String args [ ] ) { BinaryTree tree = new BinaryTree ( ) ; tree . root = new Node ( 1 ) ; tree . root . left = new Node ( 2 ) ; tree . root . right = new Node ( 3 ) ; tree . root . left . left = new Node ( 4 ) ; tree . root . left . right = new Node ( 5 ) ; tree . root . right . left = new Node ( 6 ) ; tree . root . right . right = new Node ( 7 ) ; tree . root . left . left . left = new Node ( 8 ) ; tree . root . left . left . right = new Node ( 9 ) ; tree . root . left . right . left = new Node ( 12 ) ; tree . root . right . right . left = new Node ( 10 ) ; tree . root . right . right . left . right = new Node ( 11 ) ; tree . root . left . left . right . left = new Node ( 13 ) ; tree . root . left . left . right . right = new Node ( 14 ) ; tree . root . left . left . right . right . left = new Node ( 15 ) ; System . out . println ( " Tree ▁ before ▁ truncation " ) ; tree . print ( tree . root ) ; tree . prune ( tree . root , 45 ) ; System . out . println ( " Tree after truncation "); tree . print ( tree . root ) ; } }