Print All Paths From Root In a Binary Tree Whose Sum is Equal to a Given Number

by

Objective: – Given a binary tree and X, write an algorithm to Print all the paths starting from root so that sum of all the nodes in path equals to a given number.
Example:

Print All Paths From Root In a Binary Tree Whose Sum is Equal to a Given Number

Approach:

  • Create a global variable as String = path.
  • Do the preorder
  • if root is greater than Sum required, return.
  • If not then, add root to the path and update the required sum (sum=sum-root.data).
  • if sum required =0, means we have found the path, print it.
  • See the code for better understanding.

Code:


public class ExistPathSum {
String path;
public void hasPath(Node root, int sum, String path){
if(root!=null){
if(root.data>sum){ // if root is greater than Sum required, return
return;
}else{
path+=" " + root.data; //add root to path
sum=sum–root.data; // update the required sum
if(sum==0){ //if sum required =0, means we have found the path
System.out.println(path);
}
hasPath(root.left, sum, path);
hasPath(root.right, sum, path);
}
}
}
public static void main(String[] args) {
Node root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.left.left = new Node(7);
root.left.right = new Node(5);
root.right.left = new Node(6);
root.right.right = new Node(7);
ExistPathSum i = new ExistPathSum();
i.hasPath(root, 10, "");
}
}
class Node {
int data;
Node left, right;
public Node(int data) {
this.data = data;
}
}

view raw

ExistPathSum.java

hosted with ❤ by GitHub


Output:

1 2 7
1 3 6

Related Posts: