Binary Tree Path Sum III LeetCode (All K Sum Paths in Binary Tree)

Problem: Given the root of a binary tree and an integer targetSum, return the number of paths where the sum of the values along the path equals targetSum.

The path does not need to start or end at the root or a leaf, but it must go downwards (i.e., traveling only from parent nodes to child nodes).

 Example 1:

Input: root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8
Output: 3
Explanation: The paths that sum to 8 are shown.

Example 2:

Input: root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
Output: 3

 Constraints:

• The number of nodes in the tree is in the range [0, 1000].
• -109 <= Node.val <= 109
• -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:

	/**
	You are given a binary tree in which each node contains an integer value.
	Find the number of paths that sum to a given value.
	The path does not need to start or end at the root or a leaf, but it must go downwards (traveling only from parent nodes to child nodes).
	The tree has no more than 1,000 nodes and the values are in the range -1,000,000 to 1,000,000.
	Example:
	root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8
	10
	/ \
	5 -3
	/ \ \
	3 2 11
	/ \ \
	3 -2 1
	Return 3. The paths that sum to 8 are:
	1. 5 -> 3
	2. 5 -> 2 -> 1
	3. -3 -> 11
	*/
	import java.util.*;
	public class BinaryTreePathSumStartEndAnywhere{
	public static void print(int[] nums, int start, int end){
	for(int i=start;i<=end; i++){
	System.out.print(nums[i]+" ");
	}
	System.out.println();
	}
	public static void findSum(TreeNode node, int sum, List<Integer> path, int level, List<List<Integer>> paths){
	if(node==null){
	return;
	}
	//insert current node to the path
	path.add(node.val);
	//now check if we found a sum
	int cursum = 0;
	List<Integer> pathitems = new ArrayList<Integer>();
	for(int i = level; i>=0; i--){
	cursum+=path.get(i);
	pathitems.add(path.get(i));
	if(cursum==sum){
	//print(path, i, level);
	paths.add(pathitems);
	}
	}
	//now call the method recursively on child nodes
	findSum(node.left, sum, path, level+1, paths);
	findSum(node.right, sum, path, level+1, paths);
	}
	public static int findDepth(TreeNode root){
	if(root==null){
	return 0;
	}
	return 1 + Math.max(findDepth(root.left), findDepth(root.right));
	}
	//return number of paths that give the sum
	public static int pathSum(TreeNode root, int sum){
	int depth = findDepth(root);
	//int[] path = new int[depth];
	List<Integer> path = new ArrayList<Integer>();
	List<List<Integer>> paths = new ArrayList<List<Integer>>();
	findSum(root, sum, path, 0, paths);
	return paths.size();
	}
	public static void main(String args[]){
	TreeNode ten = new TreeNode(10);
	TreeNode five = new TreeNode(5);
	TreeNode minthree = new TreeNode(-3);
	TreeNode three = new TreeNode(3);
	TreeNode two = new TreeNode(2);
	TreeNode eleven = new TreeNode(11);
	TreeNode three2 = new TreeNode(3);
	TreeNode min2 = new TreeNode(-2);
	TreeNode one = new TreeNode(1);
	ten.left = five;
	ten.right = minthree;
	five.left = three;
	five.right = two;
	minthree.right = eleven;
	three.left = three2;
	three.right = min2;
	two.right = one;
	int sum = 8;
	System.out.println(pathSum(ten, sum));
	}
	}

view raw BinaryTreePathSumStartEndAnywhere.java hosted with ❤ by GitHub

	/**
	BinaryTree path sum from any node to any other node
	*/
	public class BinaryTreePathSumAyNode{
	/**
	-we check if there is a path downard the given tree that sum to the given value
	-the path can start from any node (not necessarily root node) and can end anywhere (not necessarily leaf node)
	-we save the path in an array list and keep on updating the sum so far and the sum we need to obtain
	-if we reach the leaf node and did not get the sum, we
	*/
	public static void findAllPathSum(TreeNode root, int sum, int[] path, int level){
	if(root ==null)
	return;
	//add the current node to the path
	path[level] = root.val;
	//now check if this node would act as the end node for the path with the given sum
	int val = 0;
	for(int i= level; i>=0;i--){
	val+=path[i];
	if(val==sum){
	printPath(path, i, level);
	}
	}
	//recursively extend the path to the child nodes
	findAllPathSum(root.left, sum, path, level+1);
	findAllPathSum(root.right, sum, path, level+1);
	}
	public static int findLevel(TreeNode root){
	if(root==null)
	return 0;
	return 1+Math.max(findLevel(root.left), findLevel(root.right));
	}
	public static void printPath(int[] path, int start, int end){
	for(int i=start;i<=end; i++){
	System.out.print(path[i]+" ");
	}
	System.out.println();
	}
	public static void findSum(TreeNode root, int sum){
	int level = findLevel(root);
	int[] path = new int[level];
	findAllPathSum(root, sum, path, 0);
	}
	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;
	findSum(root, sum);
	}
	}

view raw BinaryTreePathSumAnyNode.java hosted with ❤ by GitHub