LeetCode Path Sum Problem Solution In Java

The following article is a solution that aims to solve mostly the LeetCode problem number 122 Path Sum.

Problem

Given a binary tree, check whether it is possible to find a path from the root to the leaf that will be equal to the target sum.

For example, in this tree, there exists a path from the root to the leaf with value 22:

      5
     / \
    4   8
   /   / \
  11  13  4
 / \       \
7   2       1

There is a path of sum 22 if we connect ThreeNodes 5 -> 4 -> 11 -> 2.

Constrains

Definitions: A root is generally noting start of the tree. It can be interchangeably used as a start node for a branch of arbitrary length. A leaf is a node with no children. A branch is a node connecting one parent node and one or two child nodes.

• The number of nodes in the tree is in the range [0, 5000].
• Value of TreeNode can have range in -1000 <= Node.val <= 1000
• Target sum of tree path can be in -1000 <= targetSum <= 1000

In trees, we aim for the recursive solution. For the worst-case scenario, the tree will be one long uninterrupted chain of TreeNodes with a length of 5000. In the case of a recursive solution, it will lead to 5000 frames on the stack.

Values or target sum in this problem does not matter. They are just integers numbers that we can easily represent in modern programming languages, and we do not have any other limitations on hardware.

LeetCode Path Sum problem solution in Java

For TreeNode we will use predefined class which is provided by LeetCode platform.

/**
 * Definition for a binary tree node.
 * 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;
 *     }
 * }
 */

And implementation of the Path Sum solution in Java is as follows:

class Solution {
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if (root == null) {
            return false;
        }
        return pathfinder(root, 0, targetSum);
    }

    private boolean pathfinder(TreeNode root, int currentSum, int targetSum) {

        currentSum = currentSum + root.val

        boolean pathFound = targetSum == currentSum;

        // Left is not null, Right are not null
        if (root.left != null && root.right != null) {
            boolean leftPath = pathfinder(root.left, currentSum, targetSum);
            boolean rightPath = pathfinder(root.right, currentSum, targetSum);
            return leftPath || rightPath;
        }

        // Left is null, Right is not null
        if (root.left == null && root.right != null) {
            return pathfinder(root.right, currentSum, targetSum);
        }

        // Left is not null, Right is null
        if (root.left != null && root.right == null) {
            return pathfinder(root.left, currentSum, targetSum);
        }

        // Left is null, Right is not null
        // if (root.left == null && root.right == null) {
        return pathFound;
    };
}

We will create helping function pathfinder(TreeNode root, int currentSum, int targetSum) which will help us to push down the recursion additional value of current sum.

Inside the helping function pathfinder we will make our decision based on the state of TreeNode children. If both children are nulls, we know we came to the end of the path, and we can evaluate if the route to TreeNode leaf is valid. Otherwise, we take every other case and handle it separately. In this way, we handle all children's state cases and control the boolean output of the recursive helper method.

And here is a simplified version of the code above:

class Solution {

    public boolean hasPathSum(TreeNode root, int targetSum) {
        if (root == null) {
            return false;
        }
        return pathfinder(root, 0, targetSum);
    }

    private boolean pathfinder(TreeNode root, int currentSum, int targetSum) {

        currentSum += root.val;
        boolean pathFound = targetSum == currentSum;

        if (root.left != null && root.right != null) {
            return pathfinder(root.left, currentSum, targetSum) || pathfinder(root.right, currentSum, targetSum);
        }

        if (root.left == null && root.right != null) {
            return pathfinder(root.right, currentSum, targetSum);
        }

        if (root.left != null && root.right == null) {
            return pathfinder(root.left, currentSum, targetSum);
        }

        return pathFound;
    }

}

Note to remember: Create a helper function that eliminates all existing cases of root children state.

LeetCode Path Sum problem solution in Java with one-liner

You might encounter a simplified version of this solution in the form of a "one-liner". However, this solution is tough to read at first sight, and it is improbable you would write it on the first try. But it might come to you if you cut the solution into smaller pieces, into more understandable chunks of code.

class Solution {

    public boolean hasPathSum(TreeNode root, int targetSum) {
        if (root == null) {
            return false;
        } else if (root.left == null && root.right == null && sum - root.val == 0) {
            return true;
        } else {
            return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val)
        }
    }

}

If we get to the bottom of the tree and the root element is null, we do not find the path. We get to the null root in case of invalid paths from the root to the leaf.

However, if we are at a higher level of the null root in its predecessor and it is a valid path from the tree root to its leaf, we check the left and right node for null, and we check that path is the same target sum we desired. We do this by discounting the target sum with the root's value.

The last case of the recursive algorithm stands in all the other nodes in branches. When the left or right child is not null, we recursively discount the node (root) value from targetSum and hope on the next Stackframe for the best, what is, in our case, finding the path from the root to the leaf.

The last case of the recursive algorithm stands for all the other nodes in tree branches. When the left or right child is not null, we recursively discount TreeNode value from the target sum and hope on the next Stackframe for the best, in our case, finding the path from the root to leaf.

Conclusion

This article showed you two approaches to solving LeetCode problem number 112 regarding path sum. First, start slowly with small test cases of small trees and figure out all the states of TreeNode children. Then, beginning with the "from a small to a big" approach should help you to build an easily recursive solution.

Thanks for reading. Like us? Refer us to your friends and help us grow.

Have you found a similar question on other platforms? Let us know in the comment to adjust the description, and your contribution will help others be better at solving this problem.