Binary Tree Path Sum Root Node LeetCode

Problem: Given the root of a binary tree and an integer targetSum, return true if the tree has a root-to-leaf path such that adding up all the values along the path equals targetSum.

A leaf is a node with no children.

 Example 1:

Input: root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
Output: true
Explanation: The root-to-leaf path with the target sum is shown.

Example 2:

Input: root = [1,2,3], targetSum = 5
Output: false
Explanation: There two root-to-leaf paths in the tree:
(1 --> 2): The sum is 3.
(1 --> 3): The sum is 4.
There is no root-to-leaf path with sum = 5.

Example 3:

Input: root = [], targetSum = 0
Output: false
Explanation: Since the tree is empty, there are no root-to-leaf paths.

 Constraints:

• The number of nodes in the tree is in the range [0, 5000].
• -1000 <= Node.val <= 1000
• -1000 <= targetSum <= 1000

This problem is popular in LeetCode and GeeksForGeeks. A collection of hundreds of interview questions and solutions are available in our blog at Interview Question

Solution:

	import java.util.List;
	import java.util.ArrayList;
	import java.util.Arrays;
	public class BinaryTreePathSumRootNode{
	/**
	Method1: check if there is any path from root node - we only care if there is a path, we don't need to collect all such paths and we don't need to have the path ending on leaf node
	-we assume that the root node should be included in the path, so the path starts from root and can end anywhere such that
	the sum of given value is obtained by adding all the nodes on the path
	*/
	public static boolean pathSumFromRootToAnyNode(TreeNode root, int sum){
	//base case
	if(root ==null){
	return false;
	}else if(root!=null && root.val ==sum){
	return true;
	}
	boolean isLeftSum = false;
	if(root.left!=null)
	isLeftSum = pathSumFromRootToAnyNode(root.left, sum - root.val);
	//only check on right child if we did not find the path with sum in the left child
	return isLeftSum?true:pathSumFromRootToAnyNode(root.right, sum-root.val);
	}
	/**
	check if there is a path of given sum from root node to any leaf node
	*/
	public static boolean hasPathSumRootToLeaf(TreeNode root, int sum) {
	//base case
	if(root ==null){
	return false;
	}
	//if the current node is leaf and the value till this node reaches sum
	if(root.left==null && root.right==null && sum-root.val==0)
	return true;
	else{
	boolean leftSum = hasPathSumRootToLeaf(root.left, sum-root.val);
	return leftSum==true?true:hasPathSumRootToLeaf(root.right, sum-root.val);
	}
	}
	public static void pathSumHelper2(TreeNode root, int sum, List<List<Integer>> result, List<Integer> currentResult) {
	if (root == null)
	return;
	currentResult.add(new Integer(root.val));
	if (root.left == null && root.right == null && sum == root.val) {
	result.add(new ArrayList(currentResult));
	currentResult.remove(currentResult.size() - 1);//don't forget to remove the last integer
	return;
	} else {
	pathSumHelper2(root.left, sum - root.val, result, currentResult);
	pathSumHelper2(root.right, sum - root.val, result, currentResult);
	}
	currentResult.remove(currentResult.size() - 1);
	}
	/**
	store the running path in pathSumList
	*/
	public static void pathSumHelper1(TreeNode root, int sum, List<List<Integer>> pathsList, List<Integer> curPath){
	if(root==null){
	return;
	}
	//now add the current node to the curPath
	curPath.add(new Integer(root.val));
	System.out.println("cur path is:"+Arrays.toString(curPath.toArray()));
	//now check if we reach the leaf node and get the sum
	if(root.left==null && root.right==null && root.val==sum){
	//we found a path with the given sum so we store it in our result
	pathsList.add(new ArrayList(curPath));
	System.out.println("removing node inside:"+curPath.get(curPath.size()-1));
	//remove the leaf node that formed a sum, so that we can still consider the path till its parent node and proceed with its sibling node
	curPath.remove(curPath.size()-1);
	return;
	}else{
	pathSumHelper1(root.left, sum - root.val, pathsList, curPath);
	pathSumHelper1(root.right, sum - root.val, pathsList, curPath);
	}
	//remove the last node that are leaf node but their path did not form a sum
	System.out.println("removing node outside:"+curPath.get(curPath.size()-1));
	curPath.remove(curPath.size()-1);
	}
	/**
	find all paths from root to leaf nodes that have the given sum
	-we need to store all the paths from root to leaf that give the sum
	*/
	public static List<List<Integer>> allRootLeafPathWithSum(TreeNode root, int sum) {
	List<List<Integer>> pathsList = new ArrayList<List<Integer>>();
	List<Integer> curPath = new ArrayList<Integer>();
	pathSumHelper1(root, sum, pathsList, curPath);
	return pathsList;
	}
	public static void main(String args[]){
	//create a tree
	TreeNode root = new TreeNode(5);
	root.left = new TreeNode(3);
	root.right = new TreeNode(1);
	root.left.left = new TreeNode(4);
	root.left.right = new TreeNode(8);
	root.right.left = new TreeNode(2);
	root.right.right = new TreeNode(6);
	root.right.right.left = new TreeNode(1);
	int sum = 8;
	//System.out.println("pathSumFromRoot for sum "+sum+" is:"+pathSumFromRootToAnyNode(root, sum));
	System.out.println("printing path from root to leaf with sum:"+sum);
	List<List<Integer>> pathsList = allRootLeafPathWithSum(root, sum);
	for(List<Integer> path: pathsList){
	for(Integer val:path){
	System.out.print(val+" ");
	}
	System.out.println();
	}
	}
	}

view raw BinaryTreePathSumRootNode.java hosted with ❤ by GitHub