LeetCode is a popular platform for practicing coding problems that cover a wide range of topics and difficulty levels. One such problem is the “Path Sum” problem. In this blog post, we’ll delve into solving the LeetCode Path Sum problem using Java. We’ll start with an explanation of the problem statement, followed by a step-by-step Java solution with examples.
Problem Statement
The “Path Sum” problem is a classic binary tree problem that asks us to determine whether there exists a root-to-leaf path in a binary tree where the sum of node values along the path equals a given target sum.
In other words, given a binary tree and a target sum, we need to find if there is any path from the root to a leaf such that the sum of the values along this path equals the target sum.
Here’s the formal problem statement:
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.
Example
Let’s consider a simple binary tree:
5
/ \
4 8
/ / \
11 13 4
/ \ \
7 2 1If we are given the target sum of 22, there exists a path from the root (5) to a leaf (2) with a sum of 22:
Path: 5 -> 4 -> 11 -> 2
Sum: 5 + 4 + 11 + 2 = 22So, the expected output for this case should be true.
Approach and Algorithm
To solve this problem, we can use a recursive depth-first search (DFS) approach. We’ll start from the root node and traverse the tree, keeping track of the current sum along the path. At each node, we subtract the node’s value from the target sum and continue the search in a depth-first manner until we reach a leaf node. If, at any point, we find a leaf node where the current sum equals the target sum, we return true, indicating that a valid path exists. Otherwise, we return false once we’ve explored all possible paths.
Here’s a step-by-step algorithm for solving the problem:
- Start with the root node of the binary tree and the given target sum.
- Check if the current node is
null. If it is, returnfalsebecause we cannot continue the path. - Subtract the current node’s value from the target sum to update the remaining target sum.
- Check if the current node is a leaf node (i.e., it has no left or right children). If it is, check if the remaining target sum equals the value of the leaf node. If it does, return
true, indicating a valid path. - If the current node is not a leaf node, recursively call the function on its left and right children with the updated remaining target sum.
- If either of the recursive calls returns
true, returntruefrom the current call, indicating that a valid path exists in the subtree. - If both recursive calls return
false, returnfalsefrom the current call, indicating that no valid path exists in the subtree.
Now that we have a clear algorithm in mind, let’s implement it in Java.
Java Solution
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode() {}
TreeNode(int val) { this.val = val; }
TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}
public class PathSumSolution {
public boolean hasPathSum(TreeNode root, int sum) {
// Base case: If the root is null, return false.
if (root == null) {
return false;
}
// Subtract the current node's value from the remaining sum.
sum -= root.val;
// If the current node is a leaf node and the remaining sum is 0, return true.
if (root.left == null && root.right == null && sum == 0) {
return true;
}
// Recursively check the left and right subtrees.
boolean leftPath = hasPathSum(root.left, sum);
boolean rightPath = hasPathSum(root.right, sum);
// Return true if a valid path is found in either subtree.
return leftPath || rightPath;
}
}Now, let’s break down the Java solution step by step:
- We define a
TreeNodeclass to represent nodes in the binary tree. This class includes the node’s value, left child, and right child. - We create a class called
PathSumSolutionthat contains thehasPathSummethod, which is responsible for solving the problem. - Inside the
hasPathSummethod, we first handle the base case. If the current node isnull, we returnfalsebecause we cannot continue the path. - We subtract the current node’s value from the remaining
sum. - Next, we check if the current node is a leaf node (both left and right children are
null) and if the remainingsumis 0. If both conditions are met, we returntrue, indicating that a valid path has been found. - If the current node is not a leaf node, we recursively call the
hasPathSummethod on its left and right children, passing the updated remainingsum. - We use two boolean variables,
leftPathandrightPath, to store the results of the recursive calls on the left and right subtrees. - Finally, we return
trueif eitherleftPathorrightPathistrue, indicating that a valid path was found in either subtree. Otherwise, we returnfalse.
Example Usage
Let’s test our hasPathSum method with some example binary trees and target sums.
Example 1
Consider the binary tree from the earlier example:
5
/ \
4 8
/ / \
11 13 4
/ \ \
7 2 1If we want to find a path with a sum of 22, we can use the following code:
public static void main(String[] args) {
// Create the binary tree
TreeNode root = new TreeNode(5);
root.left = new TreeNode(4);
root.right = new TreeNode(8);
root.left.left = new TreeNode(11);
root.left.left.left = new TreeNode(7);
root.left.left.right = new TreeNode(2);
root.right.left = new TreeNode(13);
root.right.right = new TreeNode(4);
root.right.right.right = new TreeNode(1);
// Target sum
int sum = 22;
// Create an instance of PathSumSolution
PathSumSolution solution = new PathSumSolution();
// Check if there exists a path with the given sum
boolean result = solution.hasPathSum
(root, sum);
// Print the result
System.out.println("Path with sum " + sum + " exists: " + result);
}When we run this code, it will output:
Path with sum 22 exists: trueAs expected, the program correctly identifies that there is a path from the root to a leaf with a sum of 22.
Example 2
Let’s consider another example with a different binary tree:
1
/ \
2 3
/ \
4 5Suppose we want to find a path with a sum of 8:
public static void main(String[] args) {
// Create the binary tree
TreeNode root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);
// Target sum
int sum = 8;
// Create an instance of PathSumSolution
PathSumSolution solution = new PathSumSolution();
// Check if there exists a path with the given sum
boolean result = solution.hasPathSum(root, sum);
// Print the result
System.out.println("Path with sum " + sum + " exists: " + result);
}When we run this code, it will output:
Path with sum 8 exists: trueAgain, the program correctly identifies that there is a path from the root to a leaf with a sum of 8.
Example 3
Let’s consider one more example with a negative target sum. Suppose we have the following binary tree:
1
/ \
2 3
/ \
4 5And we want to find a path with a sum of -1:
public static void main(String[] args) {
// Create the binary tree
TreeNode root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);
// Target sum
int sum = -1;
// Create an instance of PathSumSolution
PathSumSolution solution = new PathSumSolution();
// Check if there exists a path with the given sum
boolean result = solution.hasPathSum(root, sum);
// Print the result
System.out.println("Path with sum " + sum + " exists: " + result);
}When we run this code, it will output:
Path with sum -1 exists: falseThe program correctly identifies that there is no path from the root to a leaf with a sum of -1.
Complexity Analysis
Let’s briefly discuss the time and space complexity of our Java solution.
Time Complexity
The time complexity of our solution is O(n), where n is the number of nodes in the binary tree. This is because we visit each node once in a depth-first manner, and for each node, we perform constant-time operations (subtracting the node’s value, checking if it’s a leaf node, and making recursive calls on its children).
Space Complexity
The space complexity of our solution is O(h), where h is the height of the binary tree. In the worst case, when the binary tree is skewed (all nodes are in a single branch), the space complexity is O(n), as we need to maintain a call stack for each node. However, in a balanced binary tree, the space complexity is O(log(n)), where log(n) is the height of the tree.
Conclusion
In this blog post, we explored the LeetCode Path Sum problem and provided a detailed Java solution using a depth-first search (DFS) approach. We walked through the problem statement, explained the algorithm step by step, and demonstrated its usage with example binary trees and target sums. Our solution efficiently handles binary trees of various shapes and sizes, making it a versatile tool for solving path sum problems in Java.
The ability to solve binary tree problems like this one is essential for mastering data structures and algorithms in programming. We hope this blog post has helped you understand the problem and provided you with a clear, well-commented Java solution. Practice this problem on LeetCode and explore more tree-related challenges to strengthen your programming skills. Happy coding!
Read More –
09. Palindrome Number LeetCode Solution in Java – Check if a Number is a Palindrome or Not – https://kamleshsingad.com/what-is-palindrome-number-leetcode-solution-in-java-check/
Reverse Integer LeetCode Question: How to Reverse an Integer in Java – https://kamleshsingad.com/how-to-reverse-an-integer-in-java-solving-the-leetcode-question/
Maximum Depth of Binary Tree and LeetCode Problem #104 | Algorithm Interview Prep – https://kamleshsingad.com/maximum-depth-of-binary-tree-and-leetcode-problem-104/
