Binary Tree Root to Leaf Path Sum Equal to a Given Number.
Given a binary tree and a sum, Determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.
If path is found then return true else return false.
Note: What is leaf node? Any node whose left and right children is null is known as leaf node.
For example –
In this Binary tree, there exist a path from root-to-leaf node whose sum is equal to the given sum (which is 16).
Now, suppose if the given value of sum is 12. Then in this case we simply return false. As the root-to-leaf node path does not exist in a Binary tree whose sum is equal to 12.
There are multiple approaches we can use to solve this problem. We can either use iterative or recursive approach to solve this problem. In this tutorial, i am going to discuss only recursive solution.
Also, i have added the video tutorial at the end of this post.
Path Sum
Path Sum (Binary Tree Root to Leaf Path Sum Equal to a Given Number) – Java Code
To find the valid path, we have to traverse this binary tree recursively. We first traverse the left half of the binary tree. If we found the path then we return true. Else, we traverse right half of the binary tree.
If we found the path in any half of the tree we return true else we return false.
The time complexity of this approach is O(n).
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 |
//Root to leaf path sum - Java Code public class PathSum { /* We recursively check if tree has root-to-leaf path, such that adding up all the values along the path equals the given sum. */ public static boolean hasPathSum(TreeNode root, int sum, int target) { //If root is null if (root == null) { return false; } //Add root value to sum variable sum = sum + root.data; /* If sum is equal to target and we have found the path till leaf node */ if (sum == target && root.left == null && root.right == null) { return true; } // Recursively call left and right child return ( hasPathSum(root.left, sum, target) || hasPathSum(root.right, sum, target) ); } public static void main(String[] args) { TreeNode root = createBinaryTree(); boolean result = hasPathSum(root, 0, 16); System.out.println(result); } public static class TreeNode { int data; TreeNode left; TreeNode right; TreeNode(int data) { this.data = data; } } public static TreeNode createBinaryTree() { TreeNode rootNode = new TreeNode(7); rootNode.left = new TreeNode(6); rootNode.right = new TreeNode(5); rootNode.left.left = new TreeNode(4); rootNode.left.right = new TreeNode(3); rootNode.right.left = new TreeNode(2); rootNode.right.right = new TreeNode(1); return rootNode; } } |
In this video tutorial, I have explained the recursive implementation of a solution.
