Path Sum — Coding Interview Question

In this “Path Sum” series of posts, we will see variations of Leetcode problems which involve Binary Tree

Problem Statement

Given the root of a binary tree and an integer targetSum, return true if the tree has a root-to-leaf path such that adding up all the values along the path equals targetSum. A leaf is a node with no children.

Solution

This problem asks us to determine if there exists a root-to-leaf path in a binary tree where the sum of the node values along the path equals a given target sum.

To solve this problem, we’ll use a recursive approach known as depth-first search (DFS). The idea is to traverse the tree from the root node to each leaf node, subtracting the node values from the target sum at each step. If we reach a leaf node and the remaining target sum (after considering leaf node value) is zero, we’ve found a valid path.

Get Tech Sauce’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

We can take following approach to solve this problem:

1. Define the base case
   - If the current node is null, return false.
   - If the current node is a leaf node (i.e., it has no children), check if the remaining target sum is equal to the value of the leaf node. If so, return true.
2. Recursively check the left and right subtrees
   - Calculate the remaining target sum by subtracting the value of the current node from the original target sum.
   - Recursively call the hasPathSum function on the left and right children of the current node.
   - If either of the recursive calls returns true, it means a valid path exists in the respective subtree, so we write return statement accordingly.

public boolean hasPathSum(TreeNode root, int targetSum) {
    
    if (root == null) { // Base case, when you run out of nodes 
        return false;
    }
    
    // When you are at leaf, if the value equals target sum at that node, return true
    if (root.left == null && root.right == null && root.val == targetSum) {
        return true;
    }
    
    // Calculate the remaining target sum by subtracting the value of the current node
    int remainingSum = targetSum - root.val;
    
    // Recursively check the left and right subtrees
    boolean leftResult = hasPathSum(root.left, remainingSum);
    boolean rightResult = hasPathSum(root.right, remainingSum);
    
    // If either of the recursive calls returns true, a valid path exists
    return leftResult || rightResult;
}

We can optimize the above code by eliminating unnecessary recursive calls. In the optimized version below, if a valid path is found in either subtree, we immediately return true, avoiding unnecessary recursive calls on the other subtree.

public boolean hasPathSum(TreeNode root, int targetSum) {
    // Base case
    if (root == null) {
        return false;
    }
    
    // Base case: if the current node is a leaf node and its value equals the remaining target sum, return true
    if (root.left == null && root.right == null && root.val == targetSum) {
        return true;
    }
    
    // Calculate the remaining target sum by subtracting the value of the current node
    int remainingSum = targetSum - root.val;
    
    // Recursively check the left subtree, return true if a valid path is found
    if (hasPathSum(root.left, remainingSum)) {
        return true;
    }
    
    // Recursively check the right subtree, return true if a valid path is found
    if (hasPathSum(root.right, remainingSum)) {
        return true;
    }
    
    // If none of the above conditions are met, return false
    return false;
}

We can also solve the “Path Sum” problem using an iterative approach instead of recursion. We can use a stack data structure to keep track of the nodes to be processed. Here is the Java code:

public boolean hasPathSum(TreeNode root, int targetSum) {
    if (root == null) {
        return false;
    }
    
    Stack<TreeNode> nodeStack = new Stack<>();
    Stack<Integer> sumStack = new Stack<>();
    nodeStack.push(root);
    sumStack.push(targetSum - root.val);
    
    while (!nodeStack.isEmpty()) {
        TreeNode node = nodeStack.pop();
        int currentSum = sumStack.pop();
        
        if (node.left == null && node.right == null && currentSum == 0) {
            return true;
        }
        
        if (node.left != null) {
            nodeStack.push(node.left);
            sumStack.push(currentSum - node.left.val);
        }
        
        if (node.right != null) {
            nodeStack.push(node.right);
            sumStack.push(currentSum - node.right.val);
        }
    }
    
    return false;
}

In terms of efficiency, the recursive solution and the iterative solution have similar time and space complexity. Both solutions visit each node once, so the time complexity is O(N), where N is the number of nodes in the tree.

The space complexity for both the solutions is also O(N). Note that the recursion uses implicit call Stack and it would require N recursive calls on the call stack in the worst case.