Leetcode 112. Path Sum Java Solution


3 min read


LeetCode - The World's Leading Online Programming Learning Platform

Problem Solving Approach

  • The objective of this problem is to check whether there is a path in the given binary tree from the root to a leaf node whose sum equals the given targetSum.

  • Therefore, this code recursively explores paths in the given binary tree and checks if the path sum matches the targetSum.


  1. Recursion:

    • The hasPathSum function is called recursively.

    • This function subtracts the value of the current node from targetSum and uses the result as the new targetSum.

  2. Base Case:

    • At the start of the recursive call, it checks if the current node is null to determine if it has reached the end of the tree.

    • If it's null, the current path is not valid, so it returns false.

  3. Leaf Node Check:

    • It checks if the current node is a leaf node, meaning it has no children.

    • If the current node is a leaf node, it checks if targetSum is equal to 0.

    • If targetSum is 0, it means that the current path's sum matches the targetSum, so it returns true.

  4. Recursive Calls for Left and Right Subtrees:

    • If the current node is not a leaf node, it makes recursive calls to the left and right subtrees using the modified targetSum value.
  5. Return Result:

    • If either the left or right subtree returns true, it means there exists a path in the current path that satisfies the targetSum, so it returns true.

    • Otherwise, it returns false.

Recursive Function Implementation Table

  • Goal: https://leetcode.com/problems/path-sum/

  • Base Case (Termination Conditions):

      if root == null
      return false
      if left == null && right == null <- after subtracting root.val from sum
      return sum == 0
  • Is the previous step's result needed?: Yes

  • Problem Splitting (Divide the Problem):

      sum -= root.val
  • Combining Results:

      boolean left
      boolean right
      return left || right
  • Recursive Calls and Changes Before Moving to the Next Step (Recursive Call):

      sum -= root.val


Time Complexity: O(n), Space Complexity: O(h)

class Solution {

     * Checks if there is a path from the root to a leaf node in the given binary tree
     * with a sum equal to the target sum.
     * @param root      The root node of the binary tree.
     * @param targetSum The target sum to be achieved.
     * @return Returns `true` if a path exists, `false` otherwise.
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if (root == null) {
            return false;

        // Subtract the value of the current node from the target sum.
        targetSum -= root.val;

        // Check if the current node is a leaf node and if the target sum is 0.
        if (root.left == null && root.right == null) {
            return targetSum == 0;

        // Recursively check the left and right subtrees.
        Boolean rightNode = hasPathSum(root.right, targetSum);
        Boolean leftNode = hasPathSum(root.left, targetSum);

        // Return `true` if there is a valid path in either the left or right subtree.
        return rightNode || leftNode;

Time Complexity

  • The time complexity of this code is O(n) because it visits all nodes in the tree exactly once, where n is the number of nodes in the tree.

Space Complexity

  • Due to the recursive function calls, a call stack is built up, but it only requires space up to the height of the tree, so the space complexity is O(h), where h is the height of the tree.

Did you find this article valuable?

Support Han by becoming a sponsor. Any amount is appreciated!