fork download
copy 
  1. /**
  2.  * Remove the nodes in the binary tree for that the sum of all values from root to leaf is less than K.
  3.  * @author PRATEEK
  4.  */
  5.  class PruneSumPath {
  6.  
  7. 	public static boolean prunePath(Node root, int givenSum , int currSum)
  8. 	{
  9. 		if(root==null)	{
  10. 			if(givenSum==currSum)
  11. 				return true;
  12. 			else 	
  13. 				return false;
  14. 		}
  15.  
  16. 		boolean leftFlag = prunePath(root.left , givenSum , currSum+root.data);
  17.  
  18. 		boolean rightFlag = prunePath(root.right , givenSum , currSum+root.data);
  19.  
  20. 		if(!leftFlag)
  21. 			root.left=null;
  22. 		if(!rightFlag)
  23. 			root.right=null;
  24.  
  25. 		if(leftFlag || rightFlag )
  26. 			return true;
  27.  
  28. 		return false;
  29. 	}
  30.  
  31. 	public static void inorder(Node root) {
  32. 		if (root != null) {
  33. 			inorder(root.left);
  34. 			System.out.print(root.data + "\t");
  35. 			inorder(root.right);
  36. 		}
  37. 	}
  38.  
  39. 	public static void main(String[] args) {
  40. 		Node root = new Node(1);
  41. 		root.left = new Node(2);
  42. 		root.left.left = new Node(4);
  43. 		root.left.left.left = new Node(8);
  44. 		root.left.right = new Node(5);
  45. 		root.left.right.left = new Node(8);
  46. 		root.left.right.left.right = new Node(9);
  47. 		root.left.right.left.right.left = new Node(10);
  48.  
  49. 		root.right = new Node(3);
  50. 		root.right.left = new Node(6);
  51. 		root.right.left.right = new Node(5);
  52. 		root.right.right = new Node(7);
  53.  
  54. 		System.out.println("Before");
  55. 		PruneSumPath.inorder(root);
  56. 		PruneSumPath.prunePath(root, 15, 0);
  57. 		System.out.println("\nAfter");
  58. 		PruneSumPath.inorder(root);
  59. 	}
  60. }
  61.  
  62.  class Node  {
  63. 	public Node left;
  64. 	public int data;
  65. 	public Node right;
  66.  
  67. 	public Node(int val)
  68. 	{  this.data=val;	}
  69.  
  70. 	@Override
  71. 	public String toString(){
  72. 		return this.data + "";
  73. 	}
  74. }
  75.  
Success #stdin #stdout 0.07s 380224KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Before
8	4	2	8	10	9	5	1	6	5	3	7	
After
8	4	2	1	6	5	3
https://ideone.com/3zz4qe
Prune Sum Path
language:
Java (HotSpot 12)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!